欧几里德算法扩展

扩展欧几里德算法是用来在已知a, b求解一组p，q使得p * a+q * b = Gcd(a, b) (解一定存在，根据数论中的相关定理)。扩展欧几里德常用在求解模线性方程及方程组中。下面是一个使用C++的实现：

int exGcd(int a, int b, int &x, int &y)

{

if(b == 0)

{

x = 1;

y = 0;

return a;

}

int r = exGcd(b, a % b, x, y);

int t = x;

x = y;

y = t - a / b * y;

return r;

}

把这个实现和Gcd的递归实现相比，发现多了下面的x,y赋值过程，这就是扩展欧几里德算法的精髓。

可以这样思考:

对于a'' = b, b'' = a % b 而言，我们求得 x, y使得 a''x + b''y = Gcd(a'', b'')

由于b'' = a % b = a - a / b * b (注：这里的/是程序设计语言中的除法)

那么可以得到:

a''x + b''y = Gcd(a'', b'') ===>

bx + (a - a / b * b)y = Gcd(a'', b'') = Gcd(a, b) ===>

ay +b(x - a / b*y) = Gcd(a, b)

因此对于a和b而言，他们的相对应的p，q分别是 y和(x-a/b*y)

补充：关于使用扩展欧几里德算法解决不定方程的办法

对于不定整数方程pa+qb=c，若 c mod Gcd(p, q)=0,则该方程存在整数解，否则不存在整数解。

上面已经列出找一个整数解的方法，在找到p * a+q * b = Gcd(p, q)的一组解p0,q0后，p * a+q * b = Gcd(p, q)的其他整数解满足：

p = p0 + b/Gcd(p, q) * t

q = q0 - a/Gcd(p, q) * t(其中t为任意整数)

至于pa+qb=c的整数解，只需将p * a+q * b = Gcd(p, q)的每个解乘上 c/Gcd(p, q) 即可。