證明
設兩數為a、b(b
[編輯] 算法
輾轉相除法是利用以下性質來確定兩個正整數 a 和 b 的最大公因子的：
1. 若 r 是 a ÷ b 的餘數, 則
gcd(a,b) = gcd(b,r)
2. a 和其倍數之最大公因子為 a。
另一種寫法是
1. a ÷ b，令r為所得餘數（0≤r
若 r = 0，算法結束；b 即為答案。
2. 互換：置 a←b，b←r，並返回第一步。
[編輯] 虛擬碼
這個算法可以用遞歸寫成如下:
function gcd(a, b) {
if b<>0
return gcd(b, a mod b);
else
return a;
}
或純使用循環
function gcd(a, b) {
define r as integer;
while b ≠ 0 {
r := a mod b;
a := b;
b := r;
}
return a;
}
pascal代碼（遞歸）
求兩數的最大公約數
function gcd(a,b:integer):integer;
begin
if b=0 then gcd:=a
else gcd:=gcd (b,a mod b);
end ;
其中“a mod b”是指取 a ÷ b 的餘數。
例如，123456 和 7890 的最大公因子是 6, 這可由下列步驟看出：
a b a mod b
123456 7890 5106
7890 5106 2784
5106 2784 2322
2784 2322 462
2322 462 12
462 12 6
12 6 0
只要可計算餘數都可用輾轉相除法來求最大公因子。這包括多項式、復整數及所有歐幾里德定義域（Euclidean domain）。
輾轉相除法的運算速度為 O(n2)，其中 n 為輸入數值的位數。
輾轉相除法原理及其詳細證明如下:
“輾轉相除法”又叫做“歐幾里得算法”，是公元前 300 年左右的希臘數學家歐幾里得在他的著作《幾何原本》提出的。利用這個方法，可以較快地求出兩個自然數的最大公因數，即gcd 或叫做HCF 。
最大公約數（greatest common divisor，簡寫為gcd；或highest common factor，簡寫為hcf)
所謂最大公因數，是指幾個數的共有的因數之中最大的一個，例如 8 和 12 的最大公因數是 4，記作gcd(8,12)=4。
整除性定義
在介紹這個方法之前，先說明整除性的一些特點（下文的所有數都是正整數，不再重複），我們可以這樣給出整除性的定義：
對於二個自然數a和b，若存在正整數q，使a=bq，則a能被b整除，b為a的因子，a為b的倍數。
如果a能被c整除，並且b也能被c整除，則c為a、b的公因數（公有因數）。
由此我們可以得出以下推論：
推論1、如果a能被b整除（a=qb），若k為正整數，則ka也能被b整除（ka=kqb）
推論2、如果a能被c整除（a=hc），b也能被c整除（b=tc），則(a±b)也能被c整除
因為：將二式相加：a+b=hc+tc=(h+t)c 同理二式相減：a－b=hc－tc=(h－t)c
所以：(a±b)也能被c整除
推論3、如果a能被b整除（a=qb），b也能被a整除（b=ta），則a=b
因為：a=qbb=taa=qta qt=1 因為q、t均為正整數，所以t=q=1
所以：a=b
輾轉相除法是用來計算兩個數的最大公因數，在數值很大時尤其有用，而且套用在電腦程式上也十分簡單。其理論如下:
如果 q 和 r 是 m 除以 n 的商及餘數，即 m=nq+r，則 gcd(m,n)=gcd(n,r)。
證明是這樣的: 設 a=gcd(m,n)，b=gcd(n,r)
a=gcd(m,n)
m能被a整除，並且n也能被a整除，則由推論1得：qn也能被a整除
由推論2得：m-qn也能被a整除
而m-qn=r，即r也能被a整除，所以a=b
或
b=gcd(n,r)
n能被b整除，並且r也能被b整除，則由推論1得：qn也能被b整除
由推論2得：qn+r也能被b整除
而m=qn+r，即m也能被b整除，所以a=b
例如計算 gcd(546, 429)
gcd(546, 429) 546=1*429+117
=gcd(429, 117) 429=3*117+78
=gcd(117, 78) 117=1*78+39
=gcd(78, 39) 78=2*39
=39
