最大公因數

维库，知识与思想的自由文库

最大公因數（greatest common divisor，簡寫為gcd；或highest common factor，簡寫為hcf)，指某几個整數共有因數中最大的一個。

兩個整數的最大公因數主要有兩種尋找方法：

• 兩數各分解質因數，然後取出同樣有的項乘起來
• 輾轉相除法（擴展版）

和最小公倍數（lcm）的關係：gcd(a, b)×lcm(a, b) = ab

兩個整數的最大公因數可用於計算兩數的最小公倍數，或分數化簡成最簡分數。

兩個整數的最大公因數和最小公倍數中存在分配律：

• gcd(a, lcm(b, c)) = lcm(gcd(a, b), gcd(a, c))
• lcm(a, gcd(b, c)) = gcd(lcm(a, b), lcm(a, c))

在座標裏，將點(0, 0)和(a, b)連起來，通過整數座標的點的數目（除了(0, 0)一點之外）就是gcd(a, b)。