簡介
它是已知最古老的算法, 其可追溯至公元前300年。它首次出現於歐幾里德的《幾何原本》（第VII卷，命題i和ii）中，而在中國則可以追溯至東漢出現的《九章算術》。它並不需要把二數作質因子分解。
算法內容
輾轉相除法是利用以下性質來確定兩個正整數 a 和 b 的最大公約數的：
1. 若 r 是 a ÷ b 的餘數, 則
gcd(a,b) = gcd(b,r)
2. a 和其倍數之最大公約數為 a。
另一種寫法是：
1. a ÷ b，令r為所得餘數（0≤r<b）
若 r = 0，算法結束；b 即為答案。
2. 互換：置 a←b，b←r，並返回第一步。
算法證明
證明：
已知m=qn+p，即m整除n的商為q，餘數為p（其中,m≥n,n>p）。
注意：使用(m,n)表示m和n的最大公約數；(n,p)表示n和p的最大公約數.用m|n表示m為n的因數。
對於任意的m和n的公因數r，都有r|m和r|n。根據等式m=qn+p，可知r|p（因為等式可寫成ra=rbn+p），則r為n和p的公因數。
因此，所有m和n的公因數，都是n與p的公因數。
同理可得，所有n與p的公因數，都是m與n的公因數。
因此，（m，n）=（n，p），即m與n的最大公因數為n與m整除n後的餘數q的最大公因數。
則對於任意兩個整數a，b（其中a>=b），其最大公因數為a整除b後的餘數與b的最大公因數。
得證。
代碼
計算機代碼如下：
其中“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）。
C程式：
輾轉相除法的運算速度為 O(n )，其中 n 為輸入數值的位數。
