最大公约数与最小公倍数

分步解答

1. 1

   开始

   用辗转相除法求 gcd(252, 105)：做除法、保留余数，重复直到余数为 0。

   $$\gcd(252,\, 105)$$
2. 2

   除法第 1 步

   用 252 除以 105，保留余数 42——它将成为下一个除数。

   $$252 = 2 \cdot 105 + 42$$
3. 3

   除法第 2 步

   用 105 除以 42，保留余数 21——它将成为下一个除数。

   $$105 = 2 \cdot 42 + 21$$
4. 4

   除法第 3 步

   21 恰好整除 42，算法到此结束。

   $$42 = 2 \cdot 21 + 0$$
5. 5

   gcd 就是最后一个非零余数

   余数不断变小直到变为 0；最后的除数 21 就是最大公约数。

   $$\gcd(252,\, 105) = 21$$
6. 6

   从 gcd 到 lcm

   对任意两个数，gcd · lcm = abs(a · b)。用 252 · 105 除以 gcd 21 就得到 lcm。

   $$\operatorname{lcm}(252,\, 105) = \frac{252 \cdot 105}{\gcd(252,\, 105)} = \frac{26460}{21} = 1260$$
7. 7

   结果

   gcd(252, 105) = 21，lcm(252, 105) = 1260