最大公因子

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

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

* 兩數各分解質因子，然後取出同樣有的項乘起來

* 輾轉相除法（擴展版）

和最小公倍數（lcm）的關係：

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

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

*

*

在座標里，將點和連起來，通過整數座標的點的數目（除了一點之外）就是。