因 d1| a 且 d1| b 利用 Corollary 1.1.2 我們知 d1| a - bh = r. 因為 d1| b,d1| r 且 d2 = gcd(b,r) 故由 Proposition 1.2.5 知 d1| d2. 另一方面，因為 d2| b 且 d2| r 故 d2| bh + r = a. 因此可得 d2| d1。
Lemma 1.3.1 告訴我們當 a > b > 0 時，要求 a,b 的最大公因數我們可以先將 a 除以 b 所得餘數若為 r，則 a,b 的最大公因數等於 b 和 r 的最大公因數. 因為 r < b < a，所以當然把計算簡化了，接著我們就來看看輾轉相除法. 由於 gcd(a,b) = gcd(- a,b) 所以我們只要考慮 a,b 都是正整數的情況。
Theorem 1.3.2 (The Euclidean Algorithm) 假設 a,b 且 a > b. 由除法原理我們知存在 h0,r0 使得
因此若令 m = m1 - hn - 1m2 且 n = n1 - hn - 1n2，則 d = ma + nb.
上面的說明看似好像當 r0 0 時對每一個 i {0,1,...,n - 2} 要先將 ri 寫成 ri = mia + nib，最後才可將 d = rn - 1 寫成 ma + nb 的形式，其實這只是論證時的方便，在實際操作時我們其實是將每個 ri 寫成 mi'ri - 2 + ni'ri - 1 的形式慢慢逆推回 d = ma + nb. 請看以下的例子.
要注意這裡找到的 m,n 並不會是唯一滿足 d = ma + nb 的一組解，雖然上面的推演過程好像會只有一組解，不過只能說是用上面的方法會得到一組解，並不能擔保可找到所有的解，比方說若令 m' = m + b,n' = n - a，則 m'a + n'b = (m + b)a + (n - a)b = ma + nb = d. 所以 m',n' 也會是另一組解，所以以後當要探討唯一性時，若沒有充分的理由千萬不能說由前面的推導過程看出是唯一的就斷言是唯一，一般的作法是假設你有兩組解，再利用這兩組解所共同滿足的式子找到兩者之間的關係. 我們看看以下的作法。
Proposition 1.3.5 假設 a,b 且 d = gcd(a,b)。若 x = m0,y = n0 是 d = ax + by 的一組整數解，則對任意 t,x = m0 + bt/d,y = n0 - at/d 皆為 d = ax + by 的一組整數解，而且 d = ax + by 的所有整數解必為 x = m0 + bt/d,y = n0 - at/d 其中 t 這樣的形式。
證 明. 假設 x = m,y = n 是 d = ax + by 的一組解， 由於已假設 x = m0,y = n0 也是一組解，故得 am + bn = am0 + bn0. 也就是說 a(m - m0) = b(n0 - n). 由於 d = gcd(a,b），我們可以假設 a = a'd,b = b'd 其中 a',b' 且 gcd(a',b') = 1 （參見 Corollary 1.2.3）。因此得 a'(m - m0) = b'(n0 - n)。 利用 b'| a'(m - m0),gcd(a',b') = 1 以及 Proposition 1.2.7⑴ 得 b'| m - m0. 也就是說存在 t 使得 m - m0 = b't. 故知 m = m0 + b't = m0 + bt/d. 將 m = m0 + bt/d 代回 am + bn = am0 + bn0 可得 n = n0 - at/d，因此得證 d = ax + by 的整數解都是 x = m0 + bt/d,y = n0 - at/d 其中 t 這樣的形式. 最後我們僅要確認對任意 t,x = m0 + bt/d,y = n0 - at/d 皆為 d = ax + by 的一組整數解， 然而將 x = m0 + bt/d,y = n0 - at/d 代入 ax + by 得 a(m0 + bt/d)+ b(n0 - at/d)= am0 + bn0 = d，故得證本定理。
利用 Proposition 1.3.5 我們就可利用 Example 1.3.4 找到 13 = 481x + 221y 的一組整數解 x = 6,y = - 13 得到 x = 6 + 17t,y = - 13 - 37t 其中 t 是 13 = 481x + 221y 所有的整數解。
package mainimport "fmt"func main() { var x, y int = 18, 12 result := gcd(x,y) fmt.Printf("x, y 的最大公約數是 : %d",result)}func gcd(x,y int) int{ for y != 0 { x, y = y, x%y } return x}
Pascal語言版
var a,b,c:integer;begin readln(a,b); c:=a mod b; while c<>0 do begin a:=b;b:=c;c:=a mod b; end; write(b);end.
C語言版
/*歐幾里德算法：輾轉求余原理： gcd(a,b)=gcd(b,a mod b)當b為0時，兩數的最大公約數即為agetchar()會接受前一個scanf的回車符*/#include<stdio.h>unsigned int Gcd(unsigned int M,unsigned int N){ unsigned int Rem; while(N > 0) { Rem = M % N; M = N; N = Rem; } return M;}int main(void){ int a,b; scanf("%d %d",&a,&b); printf("the greatest common factor of %d and %d is ",a,b); printf("%d\n",Gcd(a,b)); return 0;}
Ruby語言版
#用歐幾里得算法計算最大公約數(排版略）def gcd(x, y)if y == 0return xelsereturn gcd(y, x % y)endend
C++版
#include <algorithm> // std::swap for c++ before c++11#include <utility> // std::swap for c++ since c++11int gcd(int a，int b){ if (a < b) std::swap(a, b); return b == 0 ? a : gcd(b, a % b);}
Java版
int divisor(int m,int n){ if (m % n == 0) { return n; } else { return divisor(n,m % n); }}
JavaScript版
function gcd(a,b){ var t; if(a<b) t=b,b=a,a=t; while(b!=0) t=b,b=a%b,a=t; return a;}
Python版
def gcd(a, b): while a != 0: a, b = b % a, a return b
#include <stdio.h>unsigned int gcdExtended( int a, int b, int *x, int *y);int main(void) { int a, b,GCD; int x, y; a = 1232, b = 573; /* gcdExtended(1232, 573)時, x = 20 and y = –43 1232x + 573y = 1 24640-24639 = 1 或者gcdExtended( 573,1232) 時,x=-43, y=20 573x+1232y = 1 -43*573+1232*20 = -24639+57640 = 1 gcdExtended(9151, 5787) 時 x=2011, y=-3180 */ GCD = gcdExtended(a, b,&x, &y); printf("gcdExtended(%d, %d) = %d, x=%d, y=%d\n", a, b, GCD,x,y); return 0;}// 歐幾里得擴展算法的C語言實現// ax+by=1unsigned int gcdExtended(int a, int b, int *x, int *y){ if (a == 0){ *x = 0; *y = 1; return b; } int x1, y1; int gcd = gcdExtended(b%a, a, &x1, &y1); *x = y1 - (b/a) * x1; *y = x1; return gcd;}
歐幾里得算法