基本介紹
- 中文名：擴展歐幾里得
- 外文名：expendgcd
- 別稱：無
- 表達式：a*x+b*y=gcd(a,b)
- 提出者：歐幾里得
- 提出時間：歐幾里得時期
- 套用學科：數學
- 適用領域範圍：工程，數學
- 適用領域範圍：計算機科學
擴展歐幾里德算法是用來在已知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) 即可。
