数论学习（2）——欧几里得与扩展欧几里得

欧几里得及扩展欧几里得算法与思想都是数论里面基础的基础，许多其他的定理或算法以其为基础或将其作为重要组成部分，是学数论者绕不过去的基本知识。

什么是欧几里得算法？
欧几里得算法，又叫辗转相除法，是一种求最大公约数的算法，简记为gcd(a,b)。
该算法利用了性质gcd(a,b)=gcd(b,a%b)，这里可以看出递归关系，从a,b开始递归下去，直到b位置上的数为0，此时a位置上的数即为a,b的最大公约数。而在求gcd(a,b,c,…..,n)时，可以先求出gcd(a,b),再求出gcd(gcd(a,b),c),这样以此类推，最终可求出结果。而最大公约数与最小公倍数有如下关系：gcd(a,b)*lcm(a,b)=ab,故也可求出a,b的最小公倍数。
代码如下：

int Gcd(int a, int b)//求最大公约数
{
    return b == 0 ? a : Gcd(b, a%b);
}

int Lcm(int a, int b)//求最小公倍数
{
    return a*b / Gcd(a, b);
}

那么什么又是扩展欧几里得算法？
根据裴蜀定理：若存在整数对u,v使ua+vb=d成立，则d为gcd(a,b)的倍数，反之亦成立，那么当d=gcd(a,b)时，扩展欧几里得算法（简记为exgcd）可求出ax+by=gcd(a,b)的一组解x1,y1,而x1则对于所有不定方程ax+by=n有解时都是其中的一个解，故该算法又可用于求解不定方程；因为不定方程ax+by=m等价于同余方程ax ≡ b (mod m)，故该算法又可求解求模计算的逆元。

Ps：ax ≡ b (mod m) <==> ax % m = b <==> ax + by = m，即线性方程等价于线性同余方程

基本思想：（这里照搬百度百科）
设 ax1+by1=gcd(a,b);
bx2+(a mod b)y2=gcd(b,a mod b);
根据朴素的欧几里德原理有 gcd(a,b)=gcd(b,a mod b);
则：ax1+by1=bx2+(a mod b)y2;
即：ax1+by1=bx2+(a-(a/b)*b)y2=ay2+bx2-(a/b)*by2;
根据恒等定理得：x1=y2; y1=x2-(a/b)*y2;
这样我们就得到了求解 x1,y1 的方法：x1，y1 的值基于 x2，y2.
上面的思想是以递归定义的，因为 gcd 不断的递归求解一定会有个时候 b=0，所以递归可以结束。

对于方程ax+by=gcd(a,b),由exgcd得出了一组解x0,y0,则其余解可表示为：
x = x0 + b/gcd(a, b) * t
y = y0 - a/gcd(a, b) * t(其中t为任意整数)
对于方程ax+by=m，由exgcd得出了一组解x1,y1,则其余解可表示为：
x = x1 + kb
y = y1 - kb(其中k为任意整数)

代码如下：

int exgcd(int a, int b, int &x, int &y)
{
    if(b==0)
    {
        x = 1, y = 0;
        return a;
    }
    else
    {
        int r=exgcd(b, a%b, y, x);
        y -= a/b*x;
        return r;
    }
}

求解任意线性不定方程ax + by = c的代码如下：

bool linear_equation(int a, int b, int c, int &x, int &y)
{
    int d = exgcd(a, b, x, y);
    if(c % d)
        return false;
    int k = c/d;
    x *= k; y *= k;    //求得的只是其中一组解
    return true;
}

先写到这里吧。。