点击"计算GCD"查看详细计算步骤

最大公因数定义：一组整数中共有的最大正整数因数，记作GCD(a,b)或gcd(a,b)。

特殊值：

• GCD(a, 0) = |a| (a的绝对值)
• GCD(a, a) = |a|
• GCD(a, b) = GCD(b, a) (交换律)
• GCD(a, b, c) = GCD(GCD(a, b), c)

互质数：如果GCD(a, b) = 1，则a和b互质。

计算方法：

1. 欧几里得算法：辗转相除法，基于GCD(a,b) = GCD(b, a mod b)
2. 质因数分解法：分解每个数为质因数，取公共质因数的最小指数乘积
3. 更相减损法：基于GCD(a,b) = GCD(a-b, b)，当a和b都是偶数时，先除以2

应用领域：

• 分数约分
• 解决线性丢番图方程
• 密码学（RSA算法）
• 计算机科学算法

最小公倍数(LCM)与最大公因数(GCD)的关系：

扩展欧几里得算法可以找到整数x和y，使得：