最大公因數(英語:highest common factor,hcf)也稱最大公約數(英語:greatest common divisor,gcd)是數學詞彙,指能够整除多個非零整數的最大正整数。例如8和12的最大公因数为4。
整数序列的最大公因数可以記為或。
最大公因数的值至少為1,例如;最大則為該組整數中絕對值最小的絕對值,例如和。
求兩個整數最大公因數主要的方法:
- 列舉法:分別列出兩整數的所有因數,並找出最大的公因數。
- 質因數分解:分別列出兩數的質因數分解式,並計算共同項的乘積。
- 短除法:兩數除以其共同質因數,直到兩數互質時,所有除數的乘積即為最大公因數。
兩個整數的最大公因數和最小公倍數(lcm)的關係為:
兩個整數的最大公因數可用於計算兩數的最小公倍數,或分數化簡成最簡分數。
兩個整數的最大公因數和最小公倍數中存在分配律:
在直角坐標中,兩頂點為的線段會通過個格子點。