最大公約数・最小公倍数

問題

$(1)\quad$ $504$と$360$の最大公約数と最小公倍数を求めよ。

$(2)\quad$ ユークリッドの互除法を用いて、$391$と$253$の最大公約数を求めよ。

$(3)\quad$ $2$つの自然数$a, b$の最大公約数が$18$、最小公倍数が$756$であるとき、$a \times b$の値を求めよ。

解説

最大公約数と最小公倍数の問題について解説します。

最大公約数と最小公倍数って何ですか？

まずは定義から確認していこう！

$\textcolor{red}{\text{最大公約数}}$（GCD）は、$2$つ以上の整数に共通する約数のうち最大のもの。

$\textcolor{red}{\text{最小公倍数}}$（LCM）は、$2$つ以上の整数に共通する倍数のうち最小の正のもの、のことだよ。

最大公約数・最小公倍数は$\textcolor{red}{\text{素因数分解}}$を使って求めることができます。

それでは問題を解いていきましょう。

まずはそれぞれの数を素因数分解しよう。

$504$と$360$を素因数分解すると、

素因数分解ができたら、最大公約数と最小公倍数を求めていくよ。

最大公約数は、共通する素因数の最小のべきをとります。共通する素因数は$2$と$3$で、

最小公倍数は、すべての素因数の最大のべきをとります。出てくる素因数は$2, 3, 5, 7$で、

素因数分解すれば、どちらも求められるんですね！

その通り！素因数分解は整数問題の基本だから、しっかり身につけておこうね。

$391$とか$253$って、素因数分解が大変そうです...

そういうときに便利なのがユークリッドの互除法だよ！

割り算を繰り返すだけで最大公約数が求められるんだ。

実際にやってみましょう。$391$を$253$で割ると、

余りが$138$なので、次は$253$を$138$で割ります。

余りが$115$なので、$138$を$115$で割ります。

余りが$23$なので、$115$を$23$で割ります。

余りが$0$になりました！最後の割る数が$23$なので、

割り算を繰り返すだけでいいんですね！

そうだよ！ちなみに確認すると、$391 = 23 \times 17$、$253 = 23 \times 11$ だから、確かに最大公約数は$23$だね。

数が大きくて素因数分解が難しいときは、ユークリッドの互除法が強い味方になるよ。

この問題では、最大公約数と最小公倍数の間の重要な関係式を使うよ。

$2$つの自然数$a, b$について、次の関係が成り立ちます。

最大公約数と最小公倍数を掛けると$a \times b$になるんですか！

その通り！とても便利な公式だから覚えておこうね。

理由を簡単に説明すると、$a = \gcd(a,b) \times a'$、$b = \gcd(a,b) \times b'$（$a'$と$b'$は互いに素）とおくと、$\text{lcm}(a,b) = \gcd(a,b) \times a' \times b'$ となるんだ。

だから$\gcd \times \text{lcm} = \gcd^2 \times a' \times b' = a \times b$ が成り立つよ。

では、この関係式に$\gcd(a, b) = 18$、$\text{lcm}(a, b) = 756$を代入すると、

代入するだけで求められるんですね！

この公式を知っているかどうかで差がつく問題だね。しっかり覚えておこう！

ここでは最大公約数（GCD）と最小公倍数（LCM）の求め方について学習しました。

素因数分解を使う方法はどんな場合にも使えますが、数が大きいときはユークリッドの互除法が効率的です。

また、$\gcd(a,b) \times \text{lcm}(a,b) = a \times b$ の関係式は問題でよく使うので、ぜひ覚えておきましょう！