歐幾里德算法擴展

擴展歐幾里德算法是用來在已知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) 即可。