最大公约数最小公倍数
什么是 GCD 和 LCM
最大公约数 (GCD)
最大公约数（Greatest Common Divisor，缩写 GCD），又称最大公因数（HCF），是能同时整除两个或多个整数的最大正整数。例如 gcd(12, 18) = 6，因为 6 是同时整除 12 和 18 的最大整数。
形式化定义：对于整数 a 和 b（不全为零），gcd(a, b) = max{d ∈ Z+ : d | a 且 d | b}。
最小公倍数 (LCM)
最小公倍数（Least Common Multiple，缩写 LCM）是能同时被两个或多个整数整除的最小正整数。例如 lcm(4, 6) = 12，因为 12 是同时能被 4 和 6 整除的最小正整数。
形式化定义：对于正整数 a 和 b，lcm(a, b) = min{m ∈ Z+ : a | m 且 b | m}。
为什么 GCD 和 LCM 如此重要？
GCD 和 LCM 是数论的基础构建模块。从约分分数到 RSA 加密算法，从音乐节拍到行星周期，它们的身影无处不在。欧几里得算法（约公元前 300 年）是人类历史上最古老的仍在使用的非平凡算法，至今仍是计算机科学的核心工具。
欧几里得算法
历史
欧几里得算法出自欧几里得的《几何原本》第七卷命题 1-2，约公元前 300 年。它是人类已知最古老的、至今仍在使用的非平凡算法，比埃拉托斯特尼筛法还早约半个世纪。
算法原理
核心递推关系：
反复将较大数替换为两数相除的余数，直到余数为 0，此时另一个数即为 GCD。
为什么算法正确？
证明：gcd(a, b) = gcd(b, a mod b)
设 d = gcd(a, b)。设 a = bq + r（其中 r = a mod b）。
1. 因为 d | a 且 d | b，所以 d | (a − bq) = r。因此 d 是 b 和 r 的公约数。
2. 反过来，设 d' 是 b 和 r 的任意公约数。则 d' | (bq + r) = a。所以 d' 也是 a 和 b 的公约数，因此 d' ≤ d。
3. 综合 1、2，gcd(a, b) = gcd(b, r) = gcd(b, a mod b)。 ◼
关键洞察：如果 d 同时整除 a 和 b，那么 d 也整除 a − b，因此 d 整除 a mod b。公约数集合在模运算下保持不变。
时间复杂度
O(log(min(a, b)))。这一结论由加布里埃尔·拉梅（Gabriel Lamé）于 1844 年证明，这是计算复杂度理论最早的成果之一。
拉梅定理：欧几里得算法对两个数 a ≥ b > 0 的步数不超过 b 的十进制位数的 5 倍。
为什么？最坏情况出现在连续的斐波那契数对上。因为 Fn ≈ φn/√5（其中 φ = (1+√5)/2），算法步数约为 logφ b ≈ 2.078 × log10 b，上界为 5 × log10 b。
代码实现
Python：
JavaScript：
逐步示例：gcd(252, 198)
扩展欧几里得算法
贝祖定理 (Bézout's Identity)
由法国数学家艾蒂安·贝祖（Étienne Bézout）于 1779 年正式阐述：
贝祖定理
对任意整数 a、b（不全为零），存在整数 x、y 使得 ax + by = gcd(a, b)。系数 x、y 称为贝祖系数。
扩展欧几里得算法不仅计算 gcd(a, b)，还同时找到满足贝祖等式的系数 x 和 y。
为什么扩展欧几里得如此重要？
扩展欧几里得算法是求模逆元的标准方法。如果 gcd(a, m) = 1（即 a 和 m 互质），那么 ax + my = 1，这意味着 ax ≡ 1 (mod m)，即 x 是 a 模 m 的逆元。这是 RSA 加密算法的核心步骤。
算法
JavaScript：
逐步示例：求 252x + 198y = gcd(252, 198) 的解
用 GCD 求 LCM
公式
lcm(a, b) = |a × b| / gcd(a, b)
为什么这个公式成立？
基于质因数分解的直觉：
设 a = p1a1 × p2a2 × ... 和 b = p1b1 × p2b2 × ...
GCD 取每个质因子的最小幂次：gcd(a,b) = ∏ pimin(ai, bi)
LCM 取每个质因子的最大幂次：lcm(a,b) = ∏ pimax(ai, bi)
因为对任意两个数 min(x,y) + max(x,y) = x + y，所以：
gcd(a,b) × lcm(a,b) = ∏ pimin(ai,bi) + max(ai,bi) = ∏ piai + bi = a × b ◼
为什么通过 GCD 来计算 LCM？
直接计算 a × b 可能导致整数溢出。但如果先除以 gcd，即 lcm = (a / gcd) × b，中间值更小，不易溢出。例如对于 32 位整数，a = 2×109，b = 3×109，a × b 会溢出，但 a / gcd(a,b) 可能很小。
示例
性质与定理
基本性质
| 性质 | 公式 | 说明 |
|---|---|---|
| 交换律 | gcd(a, b) = gcd(b, a) | 顺序无关 |
| 结合律 | gcd(a, gcd(b, c)) = gcd(gcd(a, b), c) | 可扩展到任意个数 |
| 幂等性 | gcd(a, a) = a | 一个数与自身的 GCD 是它本身 |
| 吸收元 | gcd(a, 0) = a | 任何数都整除 0 |
| 单位元 | gcd(a, 1) = 1 | 1 与任何数互质 |
| 乘积关系 | gcd(a,b) × lcm(a,b) = a × b | GCD 和 LCM 的核心联系 |
GCD 与 LCM 同样满足交换律和结合律
为什么 GCD 满足结合律？
gcd(a, gcd(b, c)) 是同时整除 a、b、c 的最大整数。无论先组合 b 和 c 还是先组合 a 和 b，"同时整除三个数的最大整数"这个集合是唯一确定的，不依赖于计算顺序。 ◼
分配律
分配律：gcd(a, lcm(b, c)) = lcm(gcd(a, b), gcd(a, c))
为什么？GCD 和 LCM 对应于质因子指数的 min 和 max 操作。min 和 max 之间满足分配律：min(a, max(b, c)) = max(min(a, b), min(a, c))，这可以通过对 a ≤ b, b < a ≤ c, c < a 三种情况分别验证。
互质的重要性质
若 gcd(a, b) = 1（即 a 和 b 互质），则：
- lcm(a, b) = a × b
- 存在整数 x, y 使得 ax + by = 1（贝祖定理的特例，即模逆元存在）
- 若 a | c 且 b | c，则 ab | c
- 若 a | bc，则 a | c（欧几里得引理）
实际应用
1. 约分分数
将分数 a/b 化为最简分数：分子分母同除以 gcd(a, b)。例如 48/36，gcd(48, 36) = 12，所以 48/36 = 4/3。这是小学数学中最直接的 GCD 应用。
2. 通分——找最小公分母
将分数 a/b 和 c/d 相加，需要找到最小公分母 lcm(b, d)。例如 1/4 + 1/6，lcm(4, 6) = 12，所以 1/4 + 1/6 = 3/12 + 2/12 = 5/12。
3. 周期与调度——LCM 的核心场景
为什么用 LCM？当两个周期性事件分别以周期 a 和 b 重复时，它们下一次同时发生在 lcm(a, b) 时刻。
- 交通信号灯：如果一个路口红灯周期 60 秒，另一个 90 秒，它们每 lcm(60, 90) = 180 秒 = 3 分钟同步一次。
- 行星会合：火星公转 687 天，地球 365 天，会合周期与 LCM 相关。
- 工厂排班：员工 A 每 3 天轮休，员工 B 每 5 天轮休，两人同时休息需 lcm(3, 5) = 15 天。
4. 密码学：RSA 中的模逆元
RSA 公钥加密的核心步骤：
- 选择两个大素数 p 和 q，计算 n = p × q
- 计算 λ(n) = lcm(p−1, q−1)（卡迈克尔函数）
- 选择公钥 e，用扩展欧几里得算法求 d ≡ e−1 (mod λ(n))
没有高效的 GCD/扩展 GCD 算法，现代公钥密码学就不可能实现。参见 质因数分解计算器。
5. 音乐：复合节拍（Polyrhythm）
为什么用 LCM？当一个声部以 3 拍为周期，另一个以 4 拍为周期时（3:4 复合节拍），两个节奏每 lcm(3, 4) = 12 拍重新对齐一次。这就是为什么 3 对 4 的复合节拍听起来每 12 拍循环。非洲鼓乐和印度塔布拉鼓中广泛使用此原理。
6. 瓷砖/镶嵌
用 a × b 的瓷砖铺满矩形地面，最小正方形边长为 lcm(a, b)。例如 3cm × 5cm 的瓷砖需要 15cm × 15cm 的正方形才能完美铺满。
多个数的 GCD 与 LCM
由于 GCD 和 LCM 都满足结合律，可以将它们自然地推广到多个数：
对于 n 个数，只需依次两两计算：
JavaScript：
注意事项
- 计算多个数的 LCM 时，结果可能增长极快（指数级）。例如前 20 个素数的 LCM 已超过 1022。
- 对于大量数字，可以先排序或使用分治策略来优化计算。
- 在编程中，注意中间结果的溢出问题——始终使用 (a / gcd) * b 而非 a * b / gcd。
常见问题
1. GCD 和 HCF 有什么区别？
没有区别。GCD（Greatest Common Divisor，最大公约数）和 HCF（Highest Common Factor，最大公因数）是同一个概念的不同名称。美国数学教材通常使用 GCD，英国教材则偏好 HCF。
2. gcd(0, 0) 是多少？
按约定，gcd(0, 0) = 0。虽然从"最大公约数"的字面定义看，每个整数都整除 0，所以 0 和 0 的公约数集合是全体正整数（没有最大值），但定义 gcd(0, 0) = 0 使得 gcd 在所有非负整数上保持良好的代数性质（例如 gcd(a, 0) = a 恒成立）。
3. 负数的 GCD 怎么算？
gcd 通常定义为正整数结果。gcd(−12, 18) = gcd(12, 18) = 6。在计算中取绝对值即可：gcd(a, b) = gcd(|a|, |b|)。
4. 欧几里得算法比质因数分解快多少？
快得多。欧几里得算法的时间复杂度是 O(log n)，而一般的质因数分解算法（试除法）是 O(√n)。对于 100 位数字，欧几里得算法只需约几百步，而质因数分解在目前的计算能力下几乎不可能完成——这正是 RSA 加密的安全基础。
5. 计算器能处理多大的数？
本页面的计算器使用 JavaScript 原生数字类型，安全整数范围为 ±253−1（约 9 × 1015）。超出此范围的数可能产生精度误差。如需处理更大的数，可使用 Python 的内置 math.gcd()（Python 支持任意精度整数）。