歐幾里得演算法

對很大的數，靠分解兩個數來求最大公因數會很慢。歐幾里得演算法用一個巧妙的招法完全繞開分解：它不斷把較大的數替換為它被較小數除後所剩的餘數，眼看著數字一路縮小，直到其中一個變為零。

步驟如下。要求 gcd(a, b)（設 a 大於 b），用 a 除以 b 保留餘數 r。然後丟開 a，照同樣辦法求 gcd(b, r)，再重複。每一步餘數都嚴格變小，於是終有某個餘數變為 0 — 而最後一個非零餘數就是最大公因數。其原理依據是 gcd(a, b) 等於 gcd(b, a mod b)。

這個演算法已有兩千多年歷史，至今仍是已知最快的演算法之一。它也是擴展歐幾里得演算法的引擎：後者不僅求出最大公因數，還把它表示成 a 與 b 的整數組合 — 這正是裴蜀等式的內容，也是求解線性丟番圖方程和計算模逆元的關鍵一步。