简短的回答
欧几里得算法通过重复除法求出两个数的 GCF：将较大的数除以较小的数，用余数替换较大的数，然后重复直到余数为 0 — 最后一个非零余数就是 GCF。对于 48 和 18：48÷18 留下余数 12，18÷12 留下余数 6，12÷6 留下余数 0，所以 GCF 是 6。 即使对于非常大的数字，这也可以通过几个步骤找到答案，而无需列出每个因子。
要点
- 无论数字有多大，欧几里得算法都能通过少量步骤找到 GCF——无需首先列出每个因子。
- 对于任意两个数字，GCF × LCM 等于这两个数字的乘积——这是一种在获得一个结果后对另一个结果进行健全性检查的快速方法。
- GCF 和 LCM 都通过一次组合两个数字来扩展到三个或更多数字，而不是一次将公式应用于所有数字。
- GCF 和 HCF（最大公因数）命名相同的值 - 区别在于区域术语，而不是数学。
欧几里德算法一步一步
| 步 | 分配 | 余 |
|---|---|---|
| 1 | 48 ÷ 18 = 2 | 12 |
| 2 | 18 ÷ 12 = 1 | 6 |
| 3 | 12 ÷ 6 = 2 | 0 (停止) |
最后一个非零余数 - 6 - 是 GCF。每个步骤都会用共享相同 GCF 的较小数字对替换这对数字，因此算法总是快速收敛，通常所用的步骤比任一数字的大小所建议的要少得多。
GCF-LCM 关系
GCF(a, b) × LCM(a, b) = a × b
一旦知道了两个数字的 GCF，您就可以找到 LCM，而无需单独计算：LCM = (a × b) ÷ GCF。此快捷方式仅适用于两个数字 - 对于三个或更多数字，GCF 和 LCM 都需要通过一次组合两个数字来构建。
工作示例：48 和 18 的 GCF 和 LCM
GCF(48, 18) = 6（来自上面的欧几里得算法）
最小公倍数(48, 18) = (48 × 18) ÷ 6 = 864 ÷ 6 = 144
这两个答案都可以通过质因数分解进行双重检查：48 = 2⁴ × 3 和 18 = 2 × 3²。 GCF 采用每个共享素数的最低幂 (21 × 31 = 6)，而 LCM 则采用每个涉及的素数的最高幂 (2⁴ × 3² = 144) — 与欧几里得和基于公式的结果完全匹配。
要避免的常见错误
- 直接将欧几里得算法应用于三个或更多数字 - 相反，首先找到 GCF(a, b)，然后用 c 找到该结果的 GCF，依此类推。
- 假设 GCF × LCM = a × b 扩展到三个或更多数字——仅保证两个数字相同。
- 混淆应用题实际需要的组——GCF 用于分成相等的组，LCM 用于在重复事件排列时查找。
- Stopping the Euclidean algorithm early because a remainder looks "small enough" — keep dividing until the remainder is exactly 0.