GCD 和 LCM 是用于简化分数、求解方程和调度问题的基本数论概念。这里对每个方法都解释得很清楚。
定义
GCD（最大公约数） - 也称为 GCF（最大公约数）或 HCF（最高公约数） - 是两个数字相除而无余数的最大正整数。
LCM（最小公倍数） 是可被两个数字整除的最小正整数。
GCD(a, b) × LCM(a, b) = a × b
这种关系意味着一旦找到一个，就可以计算另一个：
LCM(a, b) = (a × b) ÷ GCD(a, b)
方法一：质因数分解
最适合： 理解、较小的数字、同时处理多个数字。
GCD 的步骤：
- 对每个数字进行质因数分解
- 求公素因数
- 乘以公因数的最低次方
LCM 的步骤：
- 对每个数字进行质因数分解
- 乘以所有质因数的最高次方
示例： 36 和 48 的 GCD 和 LCM
质因数：
- 36 = 2² × 3²
- 48 = 2⁴ × 3
GCD： 公因数为 2 和 3。取最低幂：
- GCD = 2² × 31 = 4 × 3 = 12
LCM： 所有因素。取得最高权力：
- 最小公倍数 = 2⁴ × 3² = 16 × 9 = 144
验证：36 × 48 = 1,728 = 12 × 144 ✓
方法2：欧几里得算法（GCD）
最适合： 较大的数字 - 比因式分解快得多。
关键见解：GCD(a, b) = GCD(b, a mod b)，重复直到余数为 0。
GCD(a, b):
while b ≠ 0:
r = a mod b
a = b
b = r
return a
示例： GCD(252, 105)
| 步 | 一个 | 乙 | r = a mod b |
|---|---|---|---|
| 1 | 252 | 105 | 42 |
| 2 | 105 | 42 | 21 |
| 3 | 42 | 21 | 0 |
GCD = 21（最后一个非零余数）
示例： GCD(1071, 462)
| 步 | 一个 | 乙 | r |
|---|---|---|---|
| 1 | 1071 | 462 | 147 |
| 2 | 462 | 147 | 21 |
| 3 | 147 | 21 | 0 |
GCD = 21
方法三：除法/阶梯法
最适合： 视觉学习者，同时找到 GCD 和 LCM。
重复将两个数除以它们的最小公素因数：
示例： 12 和 18 的 GCD 和 LCM
2 | 12 18
3 | 6 9
| 2 3
GCD = 所用除数的乘积 = 2 × 3 = 6 LCM = 除数的乘积 × 剩余数 = 2 × 3 × 2 × 3 = 36
两个以上数字的 LCM
示例： LCM(4,6,10)
质因数：
- 4 = 2²
- 6 = 2 × 3
- 10 = 2 × 5
取每个素数的最高幂：2² × 3 × 5 = 60
验证：60 ÷ 4 = 15 ✓、60 ÷ 6 = 10 ✓、60 ÷ 10 = 6 ✓
实际应用
化简分数： 将分子和分母除以它们的 GCD。
- 24/36：GCD(24,36) = 12 → 24/36 = 2/3
将不同分母的分数相加： 求分母的最小公倍数。
- 1/4 + 1/6: LCM(4,6) = 12 → 3/12 + 2/12 = 5/12
调度问题：“两辆公交车同时出发。一辆每12分钟一班，另一辆每18分钟一班。他们什么时候再次一起出发？”
- LCM(12, 18) = 36 → 每 36 分钟
切割材料：“一块板是36厘米，另一块是48厘米。您可以从两者上切割出最长的等长块，而不浪费？”
- GCD(36, 48) = 12 厘米
快速心理检查
GCD 始终 ≤ 较小的数字 LCM 始终 ≥ 较大的数字 如果 GCD(a,b) = 1，则数字互质 — LCM(a,b) = a × b
示例： GCD(7, 13) = 1（均为素数，无公因数）→ LCM = 7 × 13 = 91