一、欧几里得算法

(1).gcd(a,b)=gcd(b,a%b)

reason:用例子来证明，假设a=38，b=8,则38=4*8+6;此时求a与b的最大公约数，肯定为6与8的最大公约数，因为4*8可以被8整除。

(2)根据上述等式求解 ax+by=gcd(a,b) {gcd(a,b)为a,b的最大公约数}

(3)递推过程

∵ax+by=gcd(a,b);

∴bx+(a%b)y=gcd(b,a%b);

∴ax1+by1=bx2+(a%b)y2;

又∵a%b=(a-(a/b)*b);

∴ax1+by1=ax2+(a-(a/b)*b)y2;

∴ax1+by1=ay2+b(x2-a/b*y2)

得：

{

x1=y2;

y1=x2-a/b*y2;

}

PS:该递推过程一直递推下去的话，会得到b==0,因为a%b==0，绝对存在。当b==0时，x=1，y=0；所以可以根据这一组特解，根据上一组解和这一组解的关系，求出上一组解（x1,y1表示上一组解）

所以实现代码如下：

int x,y;
int exgcd(int a,int b)
{
    if(!b)  //递归终止条件
    {
        x=1,y=0; return a;//a为最大公约数
    }
    int gcd=exgcd(b,a%b);
    int ans;
    ans=x;
    x=y;
    y=ans-(a/b)*y;
    return gcd;
}

二、拓展欧几里得算法

1.求ax+by=c的解

只有当c为gcd(a,b)的倍数时，此方程才有解，否则无解。

特殊情况 ax+by=1

只有当a与b互质的时候才存在解。

2.有解的情况下，求解。

因为此时 c=t*gcd(a,b) //假设c为gcd(a,b)的t倍

a(x/t)+b(y/t)=gcd(a,b); m=x/t,n=y/t;

求解之后应该得到的是m与n的值。

要求解得x的值，所以x=tm,y=tn;

3.有解的情况下，求最优解(最小正整数）。

a{x/t-b/(gcd(a,b)}+b{y/t+a*gcd(a,b)}=gcd(a,b)

同理 m=x/t-b/gcd(a,b) n=y/t+a*gcd(a,b);

可得 x=tm+tb/gcd(a,b) y=tn-atgcd(a,b);

所以求解出 x之后，最优解x1={x%(tb/gcd(a,b))+tb/gcd(a,b)}%(tb/gcd(a,b));

三、同余方程

ax=1(mod n) 意思是 ax%n=1%n;

ax=1+kn; k为倍数

所以只要满足 ax+bn=1的线性解 x,n都满足要求；

然后根据欧几里得算法，ax+bn=1 (a与b互质时 存在解)  或者 ax+bn=c  c=t*gcd(a,b) 存在解。

完结，简单总结一下：

1.欧几里得算法，就是从一个特解出发，向上推到一个可以符合当前a与b的解。

2.计算题目时，可以根据题目给出的信息，列出 ax%n=b%n(同余方程） 然后化成 ax+by=c的形式 求出解。

2019.10.12 补充：