ユークリッド互除法をまとめよう。何をやってるかのイメージを知ってもらうため、絵を使ってわかりやすく説明していく。
1. 何のために使うの？
ユークリッド互除法の使い道は
- ２つの数の最大公約数を求められる
- 分母と分子の最大公約数がわかる→分数が約分できる
ということである。いずれにせよ最大公約数を求める。
2. 最大公約数って何？
結果からたどっていこう。下のような場合
- Aさん：「5個入りの飴」を8袋
- Bさん：「5個入りの飴」を3袋
合計は
- Aさん：40個の飴
- Bさん：15個の飴
である。この場合、最大公約数は 5 である。
同じ飴の数が入った袋でくくれる場合に、「１袋あたりどれだけの飴が入っているか」が最大公約数である。
3. ユークリッド互除法の流れを絵で見る
上のすぐにわかる簡単な例題、「40と15の最大公約数を求める」をユークリッド互除法で解いていこう。
最終的なゴールは同じサイズの袋で分けることである。
ゴールを目指すため、とりあえず下のいくつかの操作を絵で追っていってほしい。まず全部の飴を大きな袋で囲む。
次に大きい方の袋を、小さい方の袋で分けてみる。つまり、青色の袋何個分かを調べる。
そうすると、余りがでる。さらに青色の袋を、緑の袋で分けてみる。つまり、緑色の袋何個分かを調べる。
まだ赤色で囲んだ余りがある。さらに緑色の袋を、赤色で分けてみよう。つまり、赤袋何個分かを調べる。
余りがなくなった！したがって、緑色の袋は赤色の袋２個でちょうど分けることができる。
ところで、青色の袋が「緑色の袋」と「赤色の袋」で分けられることを思い出してほしい。
ということは、青色の袋は赤色の袋でまとめることができる！
さらに、最初の大きな袋（全体）はどんな風に分けられていたかを考える。青と緑で分けられていたはずだ。
結局、もともとの大きな袋は赤色の袋だけてちょうど分けることができる。以上の結果をまとめておこう。
両方とも赤色の袋で分けられることがわかった。したがって、
赤色の袋の中に入っている飴の個数＝最大公約数
となる。この場合は、5が最大公約数である。約分する場合は、
となる。分母と分子は、それぞれの袋にある赤色の袋の数に対応する。つまり何セットできているか、ということである。
これがユークリッド互除法の流れを絵で考えた場合である。
4. ユークリッド互除法の仕組みを数式で見てみる
上の流れを数字で表してみる。
上の絵を数式で表す
下の図は作業の流れを簡単に表している。
- 左側：袋に分割する作業
- 右側：一番小さい袋（赤袋）で全体をまとめ直す作業
左側については割り算で表すと簡単である。つまり、
（割られる数）＝（割る数）×（商）＋（余り）
となる（下図）。
最終的に余りが０になるところまで計算していけば良い。
一般化してみる
数字を記号に置き換えておく。ここでは上と同様に、３回の作業で割り切れる場合を書いている。実際にはもっと計算が必要かもしれないし、少ないかもしれない。
とにかく何回か割り算して、割り切れるまで繰り返せば良い。最後に割り切れるようになったときの「割る数」が最大公約数である。
＊このとき「最大公約数＝１」であれば、２つの数は互いに素であったということである。そのときは、約分はできない既約分数である。
例題を解いて
以下の分数をユークリッド互除法を用いて約分しよう。
方針：4095と1911の最大公約数をユークリッド互除法で求める。
【解答図】割り算していく。
したがって
かんたん！
5. まとめ
ユークリッド互除法を絵で見てきた。操作が割り算（引き算の繰り返し）だけなので単純に計算できる。ユークリッド互除法の仕組みがわかれば、いつでもどこでも自由に最大公約数を求めることができる。