即輾轉相除，乃求兩個正整數之最大公因子的算法。它是已知最古老的算法, 其可追溯至前300年。它首次出現於歐幾里德的《幾何原本》（第VII卷，命題i和ii）中，而在中國則可以追溯至東漢出現的《九章算術》。它並不需要把二數作質因子分解。
證明：
設兩數為a、b(b＜a)，求它們最大公約數(a、b)的步驟如下：用b除a，得a＝bq1＋r1（0≤r1＜b）。若r1=0，則(a，b)＝b；若r1≠0，則再用r1除b，得b＝r1q2＋r2（0≤r2＜r1）。若r2＝0，則(a，b)＝r1，若r2≠0，則繼續用r2除r1，……如此下去，直到能整除為止。其最後一個非零餘數即為(a，b)。
算法
輾轉相除法是利用以下性質來確定兩個正整數 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，並返回第一步。
3.a是個最小的自然數。
