ユークリッドの互除法を”解法暗記”している人へ
この記事は、
・ユークリッドの互除法の「やり方」は分かっているが、その【仕組み】を聞かれたら説明できない、、、というあなたへ向けて、
・なぜユークリッドの互除法を使えば、最大公約数がもとまるのか、徹底解説していきます。
・この記事で仕組みまで理解できれば、今までなんとなく解いていた整数問題の見方が変わってくるようになります。
ぜひじっくりとご覧ください。
※2019/06/20更新：確認問題を差し替えました。
目次(タップした所へ飛びます)
ユークリッドの互除法の仕組み
さて、整数問題では時々最大公約数を見つける必要がある場合に出くわします。「不定方程式を解く際に必要な特殊解」もその応用例ですね。
この最大公約数を見つける数の組みが（12と20）のような小さな数の場合は、次の様な素因数分解で簡単に見つけることができます。
→12=2・２・３、20＝２・２・５より、2・２＝４//
互除法の復習
ところが、例えば(1219と583)の最大公約数を求めようとすると、かなり苦労します。
素因数分解をしようにも、２でも３でも４、５、、、、となかなか割り切れる数が見つかりません。
このような時に、ユークリッドの互除法を利用することで、簡単に最大公約数が見つかります。
最大公約数を見つける具体的な手順
具体的には、
大きい方の数（1219)を小さい方の数(583)で割って、1219÷583=2、、、53
⇔1219＝583×2 +53
次に、割った数(583)を余りである(53)で割り、583÷53=11,,,0（余り０：割り切れた）
⇔583＝53×11
割り切れたので、この商である「53」が1219と583の最大公約数です。
試しに、検算してみると1219÷53=23、一方で、583÷53=11 。
ここで、23と11は互いに素（１以外に公約数を持たない）なので、
確かに1219と583の最大公約数が53であることが確認できました。
何故ユークリッドの互除法が上手くいくのか ?(本題)
上記のように、非常に便利なこの「ユークリッドの互除法」ですが、どうしてこのように上手く最大公約数が見つかるのでしょうか。
この項では、できるだけ丁寧にその仕組みを解説していきます。
ユークリッドの互除法で上手くいく理由
ここからは、任意の正の整数AとB（；ただしA＞Bの関係であるとします）さらにその最大公約数をGとします。
まず、Aは当然Gを約数に持ちます。同様に、BもGを約数に持つことから、
A＝Gm
B＝Gn (m,nは互いに素な整数)とおく事ができます。
ここで、最大公約数を求めるためにユークリッドの互除法で何をしていたか思い出してみると、
大きい方の数字Aを小さい方の数字Bで割っていました。
そこで、AをBで割った時の商と余りをそれぞれp,qとすると、A＝B×p＋q と書くことができます。
さらに、割った数（ここではB）を余り（ここではq）でもう一度割ります。
（文字が増えてきて、ややこしく感じてきたら、先ほど上で行った【1219と583の最大公約数を求めた手順】を見直して、対応させてみてください。）
この時のBとqの最大公約数をHとすれば、
B＝Hm' 、q=Hn' （m'とn'は互いに素）とおけます。
ここで、A=B×p＋qに代入すると
A=Hm'p+Hn'⇔A=(m'p+n')H
と変形できるので、HはAの約数、かつ、B=Hm'とq=Hn'より、HはA、B、qの共通の約数（＝すなわち公約数）である事がわかります。
(文字式が続きますが、もう少しだけ我慢してください。)
次に、A＝B×p+qをq＝AーBpと移項して、はじめに設定したA＝GmとB＝Gnを代入します。
すると、q＝GmーGnp⇔q＝G(mーnp)
・・・となるので、Gはqの約数で、かつA＝GmとB＝Gnより、GはA、B、qの共通の約数(＝公約数)であることが分かりました。
最大公約数GとHの関係
・・・ここで、黄色でマークした部分を見てみると、全く同じことを書いている事が分かります！
これは、すなわち【G=Hである】ということを意味します。
はじめの例を使いながら整理すると、A(1219)とB(583)の最大公約数G(この値を求めたい)は、
B（割る数:583）とq（余り:53）の最大公約数H(53)と等しい。
従って、上で紹介した“大きな数を小さな数で割り、
割った数をさらにその余りで割る”ことによって割り切れた商(＝53)が、
元々の最大公約数である仕組みがわかったことになります。
もし割り切れるまで何回かかかっても・・・
もし2回で割り切れず、もう一度割り算をする必要がある場合でも、
Hと、“その次に割られる数(余りのq)”と“その余り”の最大公約数“I”が等しい・・・。
といった風に、最終的にAとBの最大公約数G＝H＝I、となるので、
この方法を余りが0になるまで繰り返すことでGが求まります。
少し難しいですが、以上がユークリッドの互除法によって最大公約数が求まる仕組みです。
確認問題：最大公約数とユークリッドの互除法
ここで、上の仕組みの理解を固めるために、もう一問最大公約数を求める問題を解きます。
先ほどの“ヤヤコシイ”文字式と照らし合わせながら、一つ一つ確認していきましょう。
問2：「814」と「555」の最大公約数を求めよ。
(一)：814÷555=1、、、259
⇔814=555×1+259
(二)：555÷259=2、、、37
⇔555=259×2+37
(三)：259÷37＝7、、、0
⇔259=37×7
ここで割り切れたので終了します。
(三)より、"37"が814と555の最大公約数である事が分かります。
(上で説明した、2回で割り切れない、3回割り算が必要な場合でした)
まとめと整数問題の関連記事
さて、今回は文字式が多く一回で全て理解するのは大変だった人もいるかと思います。
ぜひ何度も読み返して「人に仕組みを説明できる」レベルまでユークリッドの互除法を自分のものにしましょう！
次回(不定方程式の特殊解とユークリッドの互除法:作成しました)
次回は、ユークリッドの互除法(応用編)として『不定方程式の特殊解の探し方と一般解の求め方(作成中)』を解説します。完成しました↓
・「一次不定方程式(3):特殊解をユークリッドの互除法で見つける型」
＜関連：「整数問題をひらめき無しで解く為の解法記事１１選まとめ」＞
今回も最後までご覧いただきまして有難うございました。
「スマホで学ぶサイト、スマナビング！」では皆さんのご意見や、記事のリクエスト、SNSでの反応などをもとに日々記事の改善、追加、更新を行なっています。
記事のリクエストやご質問/ご意見はコメント欄までお寄せください。
また、いいね！、B！やシェア、Twitterのフォローをしていただけると励みになります。