因 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 所有的整数解。
程式设计
辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的：
⒈ 若 r 是 a ÷ b 的余数，且r不为0， 则
gcd(a,b) = gcd(b,r)
⒉ a 和其倍数之最大公因子为 a。
另一种写法是：
⒈ 令r为a/b所得余数（0≤r<b）
若 r= 0，算法结束；b 即为答案。
⒉ 互换：置 a←b，b←r，并返回第一步。
算法版本
Go语言版本
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;}
欧几里得算法