最大公約数と最小公倍数

段階的な解答

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 へ

   任意の 2 数について 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