最大公因数与最小公倍数

计算GCF和LCM

一组数字的最大公因数（GCF，也称 GCD）是能整除它们全部的最大数字，而最小公倍数（LCM）是能被它们全部整除的最小数字。 输入两个或更多整数，此计算器将立即求出两者。

方法

GCF 使用欧几里得算法求得 — 这是一种可追溯到 2000 多年前的方法：反复用较大的数除以较小的数，并用余数替换较大的数，直到余数为零。最后一个非零值即为 GCF。

一旦知道了 GCF，两个数字的 LCM 就可以直接得出：

$$\text{LCM}(\vA{a}, \vB{b}) = \frac{\vA{a} \times \vB{b}}{\vC{\text{GCF}(\vA{a}, \vB{b})}}$$

对于两个以上的数字，此计算器会在整个列表中两两应用这两种方法。

举例说明

求 12 和 18 的 GCF 和 LCM：

1. 欧几里得算法：18 ÷ 12 余数为 6；12 ÷ 6 余数为 0。GCF 为 $\vC{6}$。
2. $\text{LCM}(\vA{12}, \vB{18}) = (12 \times 18) \div \vC{6} = 216 \div \vC{6} = 36$。

需要考虑的关键因素

• GCF 为 1 的两个数字被称为”互质数”，这是一个真正有用的分类。 当 GCF 为 1 时，这两个数除了 1 之外没有共同因数——这在密码学和数论等领域中很重要，并且这也意味着它们的 LCM 就是它们的乘积。
• 对于大数，欧几里得算法比逐一列出所有因数快得多。 通过列出每个数字的所有因数并进行比较来求 GCF，对于大数来说是不现实的——无论数字有多大，欧几里得算法都只需几步就能得出答案，这正是它历经 2000 多年仍是标准方法的原因。
• GCF 和 LCM 可以用同样的两两运算方式，干净地推广到两个以上的数字。 将两数公式应用于一个列表——GCF(GCF(a,b), c)，LCM 同理——可以正确地将这两个概念扩展到任意数量的输入，这正是本计算器处理超过两个数字的列表时所采用的方法。
• 这些概念在纯数学之外的排程和资源分配问题中也频繁出现。 除了化简分数外，LCM 还能回答”两个周期性事件下一次何时重合”（如公交班次或闪烁的灯），而 GCF 能回答”这些物品最多能均分成多大的相同组数”（如将物品分成大小相同、没有剩余的若干份）。

常见错误

• 混淆哪个是 GCF，哪个是 LCM。 这两个名称听起来相似，很容易搞混 — GCF 总是两个结果中较小的那个（公因数，因此不能超过最小的输入数字），而 LCM 总是较大的那个（公倍数，因此至少和最大的输入数字一样大）。
• 假设 GCF 必须是被比较的数字之一。 如上所述，GCF 是能整除每个输入数字的最大数字 — 对于 12 和 18，答案是 6，而不是 12 或 18 本身，尽管这两个数字也都能整除至少一个输入数字。
• 对大数手动列出每个因数，而不是使用欧几里得算法。 如上所述，随着数字增大，这会变得缓慢且容易出错 — 此计算器使用的欧几里得算法无论数字大小都只需几步就能得到相同答案。
• 在未先除以 GCF 的情况下，将两个数字相乘来求 LCM。 如上所述，直接相乘只有在两个数字互质（GCF 为 1）时才能得出正确的 LCM — 对于共享公因数的数字，跳过除以 GCF 这一步会得出真实 LCM 的倍数，而不是 LCM 本身。

实用知识

• 将分数化简到最简形式正是一次 GCF 计算 — 分数计算器使用与此计算器直接计算相同的 GCF 来化简分数。
• 为加减分数寻找公分母正是一次 LCM 计算 — 是同一关系的反方向应用。
• 质因数分解计算器和比例计算器都是从不同角度依赖同一个公因数的概念 — 一个将数字分解为质数构成，另一个将比例化简为最简整数形式。