最大公因数(英语:highest common factor,hcf)也称最大公约数(英语:greatest common divisor,gcd)是数学词汇,指能够整除多个非零整数的最大正整数。例如8和12的最大公因数为4。
整数序列的最大公因数可以记为或。
最大公因数的值至少为1,例如;最大则为该组整数中绝对值最小的绝对值,例如和。
求两个整数最大公因数主要的方法:
- 列举法:分别列出两整数的所有因数,并找出最大的公因数。
- 质因数分解:分别列出两数的质因数分解式,并计算共同项的乘积。
- 短除法:两数除以其共同质因数,直到两数互质时,所有除数的乘积即为最大公因数。
两个整数的最大公因数和最小公倍数(lcm)的关系为:
两个整数的最大公因数可用于计算两数的最小公倍数,或分数化简成最简分数。
两个整数的最大公因数和最小公倍数中存在分配律:
在直角坐标中,两顶点为的线段会通过个格子点。