【高校数学】ユークリッドの互除法の考え方と応用例を徹底解説！
目次
ユークリッドの互除法とは？
ユークリッドの互除法とは、2つの整数の最大公約数（GCD）を求める効率的なアルゴリズムです。紀元前300年ごろに活躍した数学者ユークリッドによって『原論』に記された方法です。
この方法は、次のような性質に基づいています：
- 2つの整数 \(a\) と \(b\)（ただし \(a > b\)）の最大公約数は、\(a\) を \(b\) で割った余り \(r\) と \(b\) の最大公約数に等しい：\(\gcd(a, b) = \gcd(b, r)\)
基本的な例題
例題：252と105の最大公約数をユークリッドの互除法で求めなさい。
まず、252を105で割ります：
次に、105を42で割ります：
\[ 105 ÷ 42 = 2 \text{ 余り } 21 \quad \Rightarrow \quad 105 = 42 \times 2 + 21 \]続けて、42を21で割ります：
\[ 42 ÷ 21 = 2 \text{ 余り } 0 \quad \Rightarrow \quad 42 = 21 \times 2 + 0 \]余りが0になったので、最後の割る数21が最大公約数です。
よって、\(\gcd(252, 105) = 21\)
なぜこの方法で最大公約数が求まるのか？
ユークリッドの互除法が正しい理由は、次の性質に基づきます：
- 2つの整数の公約数は、その差や余りに対しても公約数となる
- そのため、余りを使って割り続けることで、最終的に最大の公約数にたどりつく
形式的には次のように書けます：
\[ \gcd(a, b) = \gcd(b, a \mod b) \]応用問題への発展
応用例1：300と84の最大公約数を求め、その値を使って分数 \(\frac{300}{84}\) を既約分数にせよ。
まずユークリッドの互除法を行います：
よって、最大公約数は12です。よって、次のように約分できます：
\[ \frac{300}{84} = \frac{25}{7} \]応用例2：2人がそれぞれ300mと84mの長さのロープを持っていて、同じ長さに切り分けたい。最も長く切るには1本何mにすればよいか？
この問題も最大公約数を求めればOKです。先ほどと同じく答えは12mです。
拡張：一次不定方程式への応用
ユークリッドの互除法は、一次不定方程式（ディオファントス方程式）にも応用できます。
たとえば、次のような方程式：
\[ 105x + 252y = 21 \]この方程式の解を整数の範囲で求めたい場合、まず \(\gcd(105, 252) = 21\) であることを確かめます。右辺がこのGCDで割り切れるので、整数解が存在します。
ユークリッドの互除法の途中計算を使って、拡張ユークリッドの互除法で解を求めることができます。
ユークリッドの互除法の式をさかのぼって書くと：
\[ 21 = 105 – 42 \times 2 \\ 42 = 252 – 105 \times 2 \Rightarrow 21 = 105 – (252 – 105 \times 2)\times 2 = 105 \times 5 – 252 \times 2 \]よって、\((x, y) = (5, -2)\) は方程式 \(105x + 252y = 21\) の一組の整数解です。
まとめ
- ユークリッドの互除法は、最大公約数を素早く求める方法です。
- 何度も割り算を繰り返し、最後の割る数が最大公約数となります。
- 分数の約分や整数の分割問題、一次不定方程式など、さまざまな応用が可能です。
受験や定期試験でもよく出題される重要な考え方なので、しっかりマスターしておきましょう！
