扩展欧几里得算法

一、扩展欧几里得算法是欧几里得算法（又叫辗转相除法）的扩展。定理：设a、b不全为0，必存在整数x、y，使得：a*x + b*y = gcd(a , b) 。

二、证明
根据欧几里得算法：∀ab ∈ N, 且 b ≠ 0，gcd(a, b)=gcd(b, a%b)。
int gcd(int a,int b){
    if(b==0) return a;
    else return gcd(b,a%b);
}
在欧几里得算法的最后一步中，
在b=0的情况下，a*x+0*y=gcd(a,0)，在这种情况下，可以取x=1,y=0,为可行解。
在b≠0的情况下，假设存在一对整数 x’, y’ 满足递归的等式。
则有：b*x’+(a%b)*y’=gcd(b,a%b);
→ b*x’+(a-a/b*b)*y’=gcd(a,b)
→ a*y’+b*(x’-a/b*y’)=gcd(a,b)
令：x=y’, y=(x’-a/b*y’)，可得 a*x + b*y = gcd(a , b) 。

int exgcd(int a,int b,int &x,int &y){//扩展欧几里得算法计算x，y
    if(b==0){
        x=1;y=0;
        return a;
    }
    int d=exgcd(b,a%b,x,y);
    int t=x;
    x=y; y=t-(a/b)*y;
    return d;
}

三、计算所有解
假设：a*x+b*y=d，已经计算出满足条件的 x1和y1。则取：
x=x1+k*b/d;
y=y1-k*a/d;
可得满足条件的所有解。

四、线性同余方程
设有线性同余方程：a*x≡b(mod m),求满足条件的解。
由同余的性质可知：a*x-b是m的倍数，假设a*x-b是m的-y倍，则有 a*x-b≡m*-y。
即：a*x+m*y=b。