最大公約數(shù)
拼音：zuì dà gōng yuē shù
英語：greatest common divisor
最大公約數(shù)（greatest common divisor,簡寫為gcd；或highest common factor,簡寫為hcf),指某幾個整數(shù)共有因子中最大的一個.
例如,12和30的公約數(shù)有：1、2、3、6,其中6就是12和30的最大公約數(shù).
兩個整數(shù)的最大公約數(shù)主要有兩種尋找方法：
* 兩數(shù)各分解質(zhì)因子,然后取出同樣有的項(xiàng)乘起來
* 輾轉(zhuǎn)相除法（擴(kuò)展版）
和最小公倍數(shù)（lcm）的關(guān)系：gcd(a, b)×lcm(a, b) = ab
兩個整數(shù)的最大公因子可用于計(jì)算兩數(shù)的最小公倍數(shù),或分?jǐn)?shù)化簡成最簡分?jǐn)?shù).
兩個整數(shù)的最大公因子和最小公倍數(shù)中存在分配律：
* gcd(a, lcm(b, c)) = lcm(gcd(a, b), gcd(a, c))
* lcm(a, gcd(b, c)) = gcd(lcm(a, b), lcm(a, c))
在坐標(biāo)里,將點(diǎn)(0, 0)和(a, b)連起來,通過整數(shù)坐標(biāo)的點(diǎn)的數(shù)目（除了(0, 0)一點(diǎn)之外）就是gcd(a, b).
后面太復(fù)雜不用看啦```3和5的最大公約數(shù)是1