一、欧几里得算法

我们前面学过求最大公约数的算法：欧几里得算法（又叫辗转相除法） ，一般缩写是gcd，在C++中经常写成如下形式：

int gcd(int a,int b)

 { 
     if(a%b==0)
         return b;
     else
         return gcd(b,a%b);
 }

原理就是代码中比较核心的 gcd(b，a%b)，这个定理用文字描述就是:

用a除以b（这里是a>b,当然，在程序编程中，求两个数的最大公约数，可以不限a和b的大小，a<b也就是多一次循环）得到结果q和余数r，再用除数b除以余数r 再得到一个余数，再用除数除以余数，…如此循环，直到余数为0，那么此时的除数就是最大公因数。

想要证明gcd(a,b) = gcd(b,a%b)，需要简单了解下面两个引理：

• 若d是a和b的公约数，那么d也是b和c的公约数（c为a%b）

• 若d是b和c的公约数（c为a%b），那么d也是a和b的公约数

这两个引理的是什么意思呢，拿第一个来说；

假设一个数d是a的因子，也就是a=m*d，同时也是b的因子，b=n*d，那么a%b = a-w*b =  (m-w*n)*d；

由此可得，a的因子集合、b的因子集合和c的因子集合是相同的；

然后利用上述定理当余数为0的时候，除数就是最大公约数；

二、扩展欧几里得算法

    从字面上看，扩展欧几里得算法就是把欧几里得算法进行了扩展，不仅能求a和b的最大公约数，还其他功能，比如:

• 求ax+by=m的任意一组解，最小整数解。

• 求模逆元（模反元素）

为了了解学习上面的公式，需要先了解一个裴属定理

【裴属定理】:

对于任意正整数a,b，必有非零整数x,y，使得  ax+by= d。其中，d=gcd(a,b)。

显然有 ax` + by` = k * d ，即 x` =k * x  ,  y`= k* y 。

简言之：ax+by能够取到a和b的最大公约数的整数倍。

简单推论：

如果 a,b互质，即gcd(a,b)=1,则ax+by可以取到任意正整数。

知道了上面的定理，我们求ax+by=m就可以判断是否有解，如果有解，那么m一定是gcd的若干倍。

那么，参考的代码模板如下：

C语言版：

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

C++版：

// 求x, y，使得ax + by = gcd(a, b)
int exgcd(int a, int b, int &x, int &y)
{
    if (!b)
    {
        x = 1; y = 0;
        return a;   //到达递归边界开始向上一层返回
    }
    int d = exgcd(b, a % b, x, y);
    int temp=y;    
    y=x-(a/b)*y;
    x=temp;
    return d;
}

上面的这段代码的解释是：

首先，当递归到达边界时，余数b==0，除数a就是最大公约数，此时可以得出方程的一组解：

x=1, y=0   //   a*1+b*0= gcd(a,b)

注意在递归中永远都是先得到上一层的结果状态。

假设栈中当前层得到的解是x1,y1, 那么我们递归后带入下一层:

b*x1 + (a%b)*y1 = gcd(a,b)
 ->  b*x1 + (a- (a/b)*b ) *y1 =gcd(a,b)
 ->  a*y1 + b*(x1- (a/b) *y1) =gcd(a,b)

显然，由上一层的解x1,y1，可以推出下一层x，y的状态

x=y1
y=x1-（a/b）*y1

通解形式：

• x=x0+b/gcd(a,b) * n  (相当于x每次可以增减：b/gcd的整数倍) 

• y=y0+a/gcd(a,b) * n  (相当于y每次可以增减：a/gcd的整数倍)    《注意：x求出来后，y通常由x代入方程求得》

最小正整数解：

• x=(x+b/gcd*n)%(b/gcd) = x%(b/gcd)     （b/gcd(a,b)应取正）

• 若x<=0，则x+=b/gcd

应用：

• 解不定方程

• 求逆元

• 求解线性同余方程