最大公因數

假設你有一塊 12 英尺的木板和一塊 18 英尺的木板，想把兩塊都裁成等長的小段，且要用盡可能長的段長而不留廢料。答案是 6 英尺 — 這就是 12 與 18 的最大公因數，即能同時整除兩者的最大的數。

嚴格地說，兩個整數 a 與 b（不全為零）的最大公因數，記作 gcd(a, b)，是能同時整除二者的最大正整數。一種算法是寫出二者的質因數分解，把它們共有的質數取較小的冪相乘。另一種快得多的算法是輾轉相除法，即反覆做帶餘除法。

一個有用的邊界情形：對任意正數 a，有 gcd(a, 0) = a，因為每個數都整除 0，所以限制因素就是 a 本身。當 gcd(a, b) = 1 時，兩數除 1 外沒有公因數，稱為互質 — 這一條件從約分到模運算無處不在。