最大公因数(Greatest Common Divisor,缩写为GCD)是指两个或多个整数共有的最大因数。在两个整数 a 和 b 中,最大公因数通常表示为 gcd(a, b)。
最大公因数有以下性质:
对于任意整数 a 和 b,gcd(a, b) = gcd(b, a)。
对于任意整数 a、b、c,gcd(a, b) = gcd(a, b - a) = gcd(a, b + a)。
当 a 能整除 b 时,gcd(a, b) = a。
若 a 和 b 互质(即它们没有除 1 以外的公因数),则 gcd(a, b) = 1。
求解最大公因数有多种方法,包括:
质因数分解法:将两个数分别进行质因数分解,然后找出共有的质因数,再将这些质因数相乘即得到最大公因数。
辗转相除法:又称欧几里德算法,通过反复使用两个数中较小的数去除较大的数,然后用所得的余数去除较小的数,一直重复这个过程,直到余数为 0。这个过程中除数和余数的变化组成的数列的最后一个非零数就是这两个数的最大公因数。
最大公因数在数论、解方程、化简分数、概率统计等领域都有重要应用。