最大公约数和最小公倍数
计算多个数的最大公约数和最小公倍数
如何使用最大公约数和最小公倍数
- 1输入两个或多个整数。
- 2运行计算器求最大公约数。
- 3查看最大公约数，以及（如需）欧几里得算法的步骤。
最大公约数
gcd(a,b) = gcd(b, a mod b)，直到余数为 0；最后一个非零余数即最大公约数最大公约数是能无余数整除每个输入的最大整数，用于把分数约到最简。
欧几里得算法不断用余数替换较大数，比逐个试除快得多。
辗转相除法的核心洞察是：gcd(a, b) = gcd(b, a mod b)。也就是说，两个数的最大公约数，等于较小数与余数的最大公约数。反复应用这个关系直到余数为 0，最后的除数就是答案。它的效率极高——即使对几百位的数，计算次数也只是位数的小倍数，这是它历经两千多年仍在使用的原因。
最大公约数的实用场景比想象中多：约分分数（分子分母同除 GCD 直接得到最简形式）、铺砖问题（用最大尺寸的正方形砖铺满矩形地面，砖边长就是长宽的 GCD）、以及密码学（RSA 算法需要计算模逆元，用扩展欧几里得算法）。两个数 GCD 为 1 时称「互质」，这在分数运算和密码学中都有特殊意义。
| 数对 | 计算过程 | GCD | 说明 |
|---|---|---|---|
| 12, 18 | 18 = 12×1 + 6 → 12 = 6×2 + 0 | 6 | 余数为 0 时的除数 |
| 48, 18 | 48 = 18×2 + 12 → 18 = 12×1 + 6 → 12 = 6×2 + 0 | 6 | 三步得出 |
| 100, 75 | 100 = 75×1 + 25 → 75 = 25×3 + 0 | 25 | 两步得出 |
| 17, 5 | 17 = 5×3 + 2 → 5 = 2×2 + 1 → 2 = 1×2 + 0 | 1 | 互质 |
用辗转相除法（欧几里得算法）求最大公约数
常见问题
最大公约数有什么用？
约分，以及作为求最小公倍数与模运算的一步。
负数有最大公约数吗？
有，最大公约数取绝对值，符号不影响结果。
若两数无公因数？
则最大公约数为 1，两数称为互质。
为什么叫「辗转相除」？
「辗转」是反复、轮流的意思，形象地描述了算法过程：用大数除以小数，再用上一轮的除数和余数继续相除，一轮轮「辗转」下去直到余数为零。这个方法记载于欧几里得《几何原本》（约公元前 300 年），是人类历史上最早记载的算法之一，比很多后来的数学发现早了一千多年。
三个数的最大公约数怎么求？
利用结合律：gcd(a, b, c) = gcd(gcd(a, b), c)。先求前两个数的 GCD，再用这个结果与第三个数求 GCD，可以推广到任意多个数。例如求 gcd(12, 18, 30)：先算 gcd(12, 18) = 6，再算 gcd(6, 30) = 6，答案是 6。同理，多个数的最小公倍数也可以用 lcm(a, b, c) = lcm(lcm(a, b), c) 递推。