最大公约数与最小公倍数计算器

使用欧几里得算法逐步计算最大公约数（GCD）和最小公倍数（LCM），支持两个及多个数字。

什么是最大公约数与最小公倍数计算器？

最大公约数(GCD)和最小公倍数(LCM)是初等数论中两个最重要的概念，其应用从中学的分数约分到保障互联网安全的加密算法，范围广泛。

欧几里得算法由欧几里得在公元前300年左右描述，是数学中最古老且最高效的算法之一。它在 O(log(min(a,b))) 步内计算 GCD，对于非常大的数字也能快速终止。该算法反复应用恒等式：GCD(a, b) = GCD(b, a mod b)，直到余数为零。

此计算器逐步展示两个数的完整欧几里得算法，并利用推广公式 GCD(a, b, c) = GCD(GCD(a, b), c) 计算多个数的 GCD 和 LCM。

欧几里得算法：

GCD(a, b) = GCD(b, a mod b) 直到 b = 0

从 GCD 求 LCM：

LCM(a, b) = |a × b| / GCD(a, b)

对于多个数：

GCD(a, b, c) = GCD(GCD(a, b), c)

LCM(a, b, c) = LCM(LCM(a, b), c)

求 GCD(48, 18)：48 = 2×18 + 12 → 18 = 1×12 + 6 → 12 = 2×6 + 0。GCD = 6。LCM = |48×18|/6 = 864/6 = 144。验证：144/48 = 3 ✓，144/18 = 8 ✓。

什么是最大公约数(GCD)？如何计算？

最大公约数(GCD)是能同时整除 a 和 b 的最大正整数。欧几里得算法高效地计算它：反复将 (a, b) 替换为 (b, a mod b)，直到 b = 0。最后一个非零值就是 GCD。

什么是最小公倍数(LCM)？它有什么用途？

最小公倍数(LCM)是能同时被 a 和 b 整除的最小正整数。它用于异分母分数加法、调度问题和音乐理论。

GCD 和 LCM 之间有什么关系？

GCD(a, b) × LCM(a, b) = |a × b|。知道 GCD 后，LCM 就是 |a × b| / GCD(a, b)。这比列举倍数更高效。

互质(Co-prime)是什么意思？

两个数互质（既约）意味着它们的 GCD 为 1 —— 它们没有共同的质因数。互质性在模算术、密码学和中国剩余定理中都是基础性的。