扩展欧几里得

扩展欧几里得

扩展欧几里德算法是用来在已知a, b求解一组x，y，使它们满足贝祖等式： ax+by = gcd(a, b) =d（解一定存在，根据数论中的相关定理）。扩展欧几里德常用在求解模线性方程及方程组中。

Code

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

对于方程ax + by = gcd(a, b)；我们设解为x1, y1

我们令a = b, b = a % b;

得到方程bx + a % by = gcd(b， a % b);

由欧几里得算法可以得到gcd(a, b) = gcd(b, a % b);

代入可得：bx + a % b y = gcd(a, b)

设此方程解为x2, y2；

在计算机中我们知道： a % b = a - (a / b) * b;

代入方程化解得：

ay2 + b(x2 - (a / b) y2) = gcd(a, b);

与ax1 + by1 = gcd(a, b) 联立，我们很容易得：

x1 = y2, y1 = x2 - ( a / b ) y2 ;

y2为后来的第四维值，要把它赋给x1（原来第三维值）

才有了extgcd( , , y, )

而extgcd( , , , x)这里把后来的第三维值（x2）赋给了原来的第四维值（y1）

现在x2 y2 没有了，取而代之的是 y1, x1

但根据y1 = x2 - (a / b)y2 判断原来的y1还应该加一步此操作

但执行完extgcd( , , y, x)后x2赋给了y1后消失了，y2赋给了x1后消失了

所以只能借用y1 替换 x2， 用 y2 替换 x1 ， 得

y1 = y1 - (a / b)x1

即 y = y - (a / b) x