ユークリッドの互除法って何に使うの?
ユークリッドの互除法とは、2つの数の最大公約数を求めるための計算方法です。
例えば、6と8の最大公約数を考えてみましょう。
$6=2×3$
$8=2×2×2$
なので、最小公倍数は6と8の最大公約数は2です。
6と8は見た瞬間すぐに素因数分解できるので、簡単に最大公約数を求めることができます。
では、791と1243の最大公約数はどうでしょう?
すぐには分かりません。
大きい数の素因数分解は、意外と難しいのです。
そこで、ユークリッドの互除法が登場します。
最大公約数を面積で考える発想
ユークリッドの互除法の基本的な発想は、最大公約数を面積で考える、というものです。
簡略のため、ここでは8と22の最大公約数を考えましょう。
縦の長さが8、横の長さが22の長方形を考えます。
この長方形を、同じ大きさの正方形で敷き詰めていくことを考えます。
例えば、一辺の長さが1の正方形なら、絶対に敷き詰めることがでますよね。
縦に8個、横に22個正方形を並べて行けば完了です。
実際に敷き詰めると上の図のようになります。
つまり、1辺の長さが1の正方形であれば、どんな長方形でも敷き詰めができます。
でもこれは当たり前すぎて面白くありません。
最大公約数を考えたいので、1辺の長さが1ではなく、なるべく大きい正方形で敷き詰めをしたいものです。
例えば、一辺の長さが5の場合はどうでしょうか?
はみ出してしまいました。
一辺の長さが5の正方形では、この長方形は敷き詰めできないようです。
そこでユークリッドさんんはこう考えます。
とりあえず最大限でかい正方形を並べていって、段々小さくすりゃよくね?と。
今回は縦の長さが8、横の長さが22なので、ひとまず一辺の長さが8の正方形を何個並べることができるか考えます。
22は8より大きいので、1つは必ず入ります。
では2つ目は?入ります。
3つ目は?8×3=24で、22を超えてしまうので、無理です。
2個まで入りますね。並べてみると、こうなります。
一辺の長さが8の正方形が2個入って、長さが6余ります。
長方形のよこの長さに着目してこれを式にすると、
22=8×2+6 となります。
色のついていない白い長方形に着目しましょう。
縦の長さが8で、横の長さが6です。
今度は一辺の長さが6の正方形を白い部分に入れてみます。
一辺の長さが6の正方形は、1個入って、長さが2余ります。
これを縦の長さに注目して式にすると、
8=6×1+2 となります。
さて、まだ色のついていない白い長方形に着目してみましょう。
縦の長さが2、横の長さが6の長方形です。
これに、一辺の長さが2の正方形を入れていきます。
余りなく、ぴったりはまりました!!
これを式で表すと、
6=2×3+0 となります。
ぴったりはまったので、今回の最大公約数は2ということが分かりました。
式をまとめると、こうです。
余りが0になるまで繰り返していくところがポイントです。
ちなみに、最大公約数が1の場合はあまりが1になった時点で終わってもかまいません。
このように、割り算を繰り返して最大公約数を求めていく計算を、ユークリッドの互除法といいます。
8と22くらいなら、わざわざユークリッドの互除法を使うまでもありませんが、
数が大きくなってくるとこれが有効です。
試しに791と1243の最大公約数を調べてみましょう。
1243=791×1+452
791=452×1+339
452=339×1+113
339=113×3+0
よって、791と1243の最大公約数は113です。
まとめ
いかがでしたか?
ユークリッドの互除法は、意味がよく分からないまま計算手順だけ覚えさせられるものの筆頭ですが、
最大公約数を面積で捉えているという発想を知っていると、多少は風通しがよくなります。
皆さんの学びの一助となれば幸いです。
コメント