最小公倍数与最大公因数：分解质因数、短除法和辗转相除法

最大公因数（gcd）是能整除所有给定数的最大整数。最小公倍数（lcm）是所有给定数的最小正公倍数。它们出现在分数运算、周期问题和等分问题中。

方法一：分解质因数

把每个数分解成质因数的乘积。

• 最大公因数：取公共质因数，每个取最低次幂，再相乘。
• 最小公倍数：取出现过的全部质因数，每个取最高次幂，再相乘。

例题：12 和 18

1. $12 = 2^2 \cdot 3$，$18 = 2 \cdot 3^2$。
2. $\text{gcd} = 2^1 \cdot 3^1 = 6$。
3. $\text{lcm} = 2^2 \cdot 3^2 = 36$。
4. 验算：$6 \cdot 36 = 216 = 12 \cdot 18$。

方法二：短除法（同时分解）

在同一张表里，按顺序用质数去除所有数，直到全部变成 1。所有除数之积是最小公倍数；能同时整除所有数的那些除数之积是最大公因数。

例题：12、18 和 30

1. $\text{lcm} = 2 \cdot 2 \cdot 3 \cdot 3 \cdot 5 = 180$。
2. $\text{gcd} = 2 \cdot 3 = 6$。

方法三：辗转相除法

数很大时，分解质因数很慢。欧几里得算法利用 $\text{gcd}(a, b) = \text{gcd}(b, r)$，其中 $r$ 是 $a \div b$ 的余数。重复进行，直到余数为零，最后一个除数就是最大公因数。

例题：gcd(84, 36)

1. $84 = 2 \cdot 36 + 12$。
2. $36 = 3 \cdot 12 + 0$。
3. 余数为零：$\text{gcd}(84, 36) = 12$。

捷径：由最大公因数求最小公倍数

对两个正整数：

沿用上例：$\text{lcm}(84, 36) = \dfrac{84 \cdot 36}{12} = 7 \cdot 36 = 252$。

典型应用题

例题：两路公交车 8:00 同时发车，一路每 12 分钟一班，另一路每 18 分钟一班。下一次同时发车是几点？

1. 周期事件再次重合：用最小公倍数。
2. $\text{lcm}(12, 18) = 36$。
3. 下一次同时发车是 8:36。

例题：长 84 厘米和 36 厘米的两根丝带要剪成同样长的小段，每段尽可能长且没有剩余。每段多长？一共几段？

1. 能同时整除两者的最大长度：用最大公因数。
2. $\text{gcd}(84, 36) = 12$ 厘米。
3. 段数：$84 \div 12 + 36 \div 12 = 7 + 3 = 10$。

常见错误

1. 求最大公因数时，把不是所有数共有的质因数也算进去。
2. 对三个或更多的数使用 $\text{lcm} \cdot \text{gcd} = a \cdot b$。
3. 搞错题目要求：求重合时间用最小公倍数，求等分长度用最大公因数。