ドラゴンスター山下の数学物語21

みなさんこんにちは！
ドラゴンスター山下の数学物語第21回です。

今回は『ユークリッドの互除法』について書きたいと思います。
『ユークリッドの互除法』は2014年度受験生から新たに適用された学習要領、
いわゆる“新課程”において、数学Aに新しく導入された内容になります。
今回なぜこの話題を取り上げたかというと、旧課程世代である私自身、
高校生の時には習わなかった内容なので個人的にすごく新鮮味があることがまず一つです。
また授業をしている中で、互除法の使用法は知っていても、なぜそうなるのか、
何をやっているのかを理解していない生徒が多かったからです。

ユークリッド互除法がまだ怪しいという人は、ぜひ今回で復習しておいてくださいね！

では本題に入りたいと思います。
そもそも、ユークリッドの互除法とはどういった定理なのかというと、

整数aを整数bで割った時の商をq、余りをrとするとき、
つまりa=bq+rが成り立つとき、
(aとbの最大公約数)=(bとrの最大公約数)
が成立する。

という内容です。
最大公約数をつくる数の組の変換ができるのですね。

それでは、どうしてそんなことが出来るのか、証明をしておきたいと思います。

(証明)
aとbの最大公約数をm_______(1)、
bとrの最大公約数をn________(2)とおく。
定理の条件より、a=bq+r_______(3)　が成り立つ。
ここで(2)よりbとrはnの倍数だから、aもnの倍数となる。
ゆえにnはaとbの公約数となる。(1)よりaとbの公約数の中で最大のものがmであるから、n≦mが成立する。

また(3)を移項すると、r=a-bqが成り立つ。
ここで(1)よりaとbはmの倍数だから、rもmの倍数となる。
ゆえにmはbとrの公約数となる。(2)よりbとrの公約数の中で最大のものがnであるから、m≦nが成立する。

以上よりn≦mかつn≧mとなりn=mがいえる。
よって主張が成立する。

(証明終)

少し難しいかもしれませんが、mとnの最大性に注意すれば、
同じことを二度、繰り返すだけで証明ができます。

次に互除法が具体的にどういったときに役立つのかということですが、

例えば40と28の最大公約数はなんですか？と聞かれたとします。
この場合は簡単で、
40の約数は1、2、4、5、8、10、20、40。
一方、28の約数は1、2、4、7、14、28 ですね。
以上見比べると、4が最大公約数となります。簡単ですね。

では、759と161の最大公約数はなんですか？と聞かれた場合はどうでしょうか。
先ほどと同じやり方では、なかなか大変そうじゃないですか？
こういったときに、今回のユークリッド互除法が非常に役立つのです。

では、実際にやってみます。
まず、759を161で割ります。すると商が4、余りが115になります。
つまり759=161・4+115ということです。
ここでユークリッドの互除法を適用すると、
(759と161の最大公約数)＝(161と115の最大公約数)
が成り立ちます。
759と161の最大公約数を求めるよりは、
161と115の最大公約数を求める方が、少しは楽になりそうですよね。

ですがまだ終わりではありません。
今度は、161を115で割ってみましょう。商が1、余りが46です。
つまり、161=115・1＋46です。
ここでまたユークリッド互除法により、
(161と115の最大公約数)＝(115と46の最大公約数)となります。

さっきのと合わせると、(759と161)=(161と115)＝(115と46)
となりました。だいぶ数が減ってきましたね。

同様に、115=46・2+23より、
(759と161の最大公約数)=…=(46と23の最大公約数)=23
と出ます。

このようにして、どれだけ大きい数の組であっても、
何度も何度も繰り返してひたすら割っていけば、
いずれは最大公約数を求めることができます。
このように同様の手順で繰り返し計算していくことをアルゴリズムと言います。
ユークリッド互除法の最大の特長はこの“アルゴリズム”です。
少し面倒な時もありますが、非常に万能性の高い定理です。
ちなみに、小さい方の数がN桁の自然数であれば、
互除法は５N回以内で終わることが知られています。

今回はユークリッド互除法の仕組みと使い方についてお話しました。

私がこの互除法をはじめてきちんと学習したのは大学生になってからです。
新課程で追加された分野の内容は、比較的難しめのものが多いかもしれませんね。
しかし、だからこそ適当に乗り切るのではなく、
学習していることの意味をしっかり根本から理解するよう意識して進めていくように
心掛けて頂きたいと思います。

いよいよスタートの季節、誰よりも輝かしいスタートダッシュが切れるように、
一緒に頑張っていきましょう。

名大理学部数理科学科　山下龍星