最大公約數(shù)（greatest common divisor,簡寫為gcd；或highest common factor,簡寫為hcf),指某幾個(gè)整數(shù)共有因子中最大的一個(gè).
例如,12和30的公約數(shù)有：1、2、3、6,其中6就是12和30的最大公約數(shù).
兩個(gè)整數(shù)的最大公約數(shù)主要有兩種尋找方法：
* 兩數(shù)各分解質(zhì)因子,然后取出同樣有的項(xiàng)乘起來
* 輾轉(zhuǎn)相除法（擴(kuò)展版）
和最小公倍數(shù)（lcm）的關(guān)系：gcd(a,b)×lcm(a,b) = ab
兩個(gè)整數(shù)的最大公因子可用于計(jì)算兩數(shù)的最小公倍數(shù),或分?jǐn)?shù)化簡成最簡分?jǐn)?shù).
兩個(gè)整數(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).
幾個(gè)數(shù)公有的倍數(shù)叫做這幾個(gè)數(shù)的公倍數(shù),其中最小的一個(gè)叫做這幾個(gè)數(shù)的最小公倍數(shù).
最小公倍數(shù)的表示：
數(shù)學(xué)上常用方括號(hào)表示.如[12,18,20]即12、18和20的最小公倍數(shù).
最小公倍數(shù)的求法：
求幾個(gè)自然數(shù)的最小公倍數(shù),有兩種方法：
（1）分解質(zhì)因數(shù)法.先把這幾個(gè)數(shù)分解質(zhì)因數(shù),再把它們一切公有的質(zhì)因數(shù)和其中幾個(gè)數(shù)公有的質(zhì)因數(shù)以及每個(gè)數(shù)的獨(dú)有的質(zhì)因數(shù)全部連乘起來,所得的積就是它們的最小公倍數(shù).
例如,求[12,18,20],因?yàn)?2=22×3,18=2×32,20=22×5,其中三個(gè)數(shù)的公有的質(zhì)因數(shù)為2,兩個(gè)數(shù)的公有質(zhì)因數(shù)為2與3,每個(gè)數(shù)獨(dú)有的質(zhì)因數(shù)為5與3,所以,[12,18,20]=2^2×3^2×5=180.（可用短除法計(jì)算）
（2）公式法.由于兩個(gè)數(shù)的乘積等于這兩個(gè)數(shù)的最大公約數(shù)與最小公倍數(shù)的積.即（a,b）×[a,b]=a×b.所以,求兩個(gè)數(shù)的最小公倍數(shù),就可以先求出它們的最大公約數(shù),然后用上述公式求出它們的最小公倍數(shù).
例如,求[18,20],即得[18,20]=18×20÷（18,20）=18×20÷2=180.求幾個(gè)自然數(shù)的最小公倍數(shù),可以先求出其中兩個(gè)數(shù)的最小公倍數(shù),再求這個(gè)最小公倍數(shù)與第三個(gè)數(shù)的最小公倍數(shù),依次求下去,直到最后一個(gè)為止.最后所得的那個(gè)最小公倍數(shù),就是所求的幾個(gè)數(shù)的最小公倍數(shù).