最大公約数・最小公倍数とユークリッドの互除法の求め方

1. 最大公約数と最小公倍数とは

• 最大公約数(GCD): 2つ以上の整数に共通する約数のうち、最大のもの
• 最小公倍数(LCM): 2つ以上の整数に共通する倍数のうち、最小のもの

小さい数どうしなら素因数分解で求められますが、桁数が大きくなると素因数分解自体が大変になります。そこで役立つのが、この記事で紹介するユークリッドの互除法です。

2. 最大公約数と最小公倍数の関係

2つの自然数 $a, b$ の最大公約数を $g$、最小公倍数を $l$ とすると、次の関係が成り立ちます。

$$a \times b = g \times l$$

一方がわかれば、もう一方は割り算だけで求められるので、覚えておくと計算が速くなります。

2.1. 例題1: 素因数分解で求める

$24$ と $36$ の最大公約数と最小公倍数を、素因数分解を使って求めなさい。

$$24 = 2^3 \times 3, \qquad 36 = 2^2 \times 3^2$$

最大公約数は、共通する素因数を小さいほうの指数でかけ合わせます。

$$\gcd(24, 36) = 2^2 \times 3 = 12$$

最小公倍数は、現れるすべての素因数を大きいほうの指数でかけ合わせます。

$$\text{lcm}(24, 36) = 2^3 \times 3^2 = 72$$

確認すると、$12 \times 72 = 864$、$24 \times 36 = 864$ で一致します。

3. ユークリッドの互除法とは

ユークリッドの互除法は、「2つの整数 $a, b$($a > b$)の最大公約数は、$a$ を $b$ で割った余り $r$ と $b$ の最大公約数に等しい」という性質を使って、割り算を繰り返すことで最大公約数を求める方法です。

$$\gcd(a, b) = \gcd(b, r) \quad (r \text{は } a \div b \text{ の余り})$$

余りが $0$ になったときの割る数が、求める最大公約数です。素因数分解が難しい大きな数でも、割り算を繰り返すだけで確実に最大公約数を求められるのが最大のメリットです。

4. ユークリッドの互除法の手順

1. 大きいほうの数を小さいほうの数で割り、余りを求める
2. 「割った数」と「余り」の組に置き換えて、同じ割り算を繰り返す
3. 余りが $0$ になったときの「割る数」が最大公約数

（本文中への画像挿入案: /images/math-a/yuukurido-gojoho-tejun.png、alt=「ユークリッドの互除法の計算手順を示したフローチャート」をこのセクションの下に配置すると、割り算を繰り返す流れが視覚的に伝わりやすくなります。)

4.1. 例題2: 大きい数の最大公約数を求める

$1071$ と $462$ の最大公約数を、ユークリッドの互除法で求めなさい。

$1071 = 462 \times 2 + 147$ $462 = 147 \times 3 + 21$ $147 = 21 \times 7 + 0$

余りが $0$ になったときの割る数は $21$ なので、$\gcd(1071, 462) = 21$ です。

5. ユークリッドの互除法で最小公倍数も求める

最大公約数がわかれば、先ほどの関係式 $a \times b = g \times l$ を使って最小公倍数もすぐに求められます。

5.1. 例題3: 最小公倍数を求める

例題2の結果を使って、$1071$ と $462$ の最小公倍数を求めなさい。

$$l = \frac{a \times b}{g} = \frac{1071 \times 462}{21} = 51 \times 462 = 23562$$

6. クイズ

1. ユークリッドの互除法を使って、$270$ と $192$ の最大公約数を求めなさい。

   • 答えを見る

     正解: $6$。$270=192\times1+78$、$192=78\times2+36$、$78=36\times2+6$、$36=6\times6+0$ より、最大公約数は $6$。

2. 最大公約数が $6$、最小公倍数が $72$ である2つの自然数 $a, b$ について、$a \times b$ の値を求めなさい。

   • 答えを見る

     正解: $432$。$a\times b = g\times l = 6\times72=432$。