ユークリッドの互除法で最大公約数が求まる仕組み

　前回、最大公約数や最小公倍数の求め方について書きました。大体は前回のやり方で事足りると思いますが、約数に気づけないと苦しむでしょう。そんなときに便利な方法があって、ユークリッドの互除法と言います。これは、最大公約数を求めるための方法ですが、一次不等式の整数解を求めるときにも使えるものです。今回は、ユークリッドの互除法とは何か、また、その使い方、さらに、その仕組みについて書こうと思います。ここでは納得してもらうことが目的なので、厳密な証明ではなく、比較的理解しやすいよう解説してみます。

　まずはユークリッドの互除法とは何かを簡単に説明します。ユークリッドの互除法とは、「整数Aを整数Bで割ったとき（A＞B）の余りをRとするとき、AとBの最大公約数は、BとRの最大公約数に一致する」というものです。いまいち分かりにくいかもしれませんが、AよりBやRの方が小さいはずなので、これを繰り返し用いると、最大公約数が求まるところまで行きつくということなのです。ちょっとイメージしにくいと思うので、ひとつ具体例を出して計算してみましょう。

（問題）３２１９と６２９の最大公約数を求めよ。

　これは約数から見つけ出すのはちょっと難しいですね。では、ユークリッドの互除法を使います。まずは、３２１９を６２９で割り、出た余りで６２９を割り・・・と続けてみます。下図を右から順に見てください。

　いかがでしょうか？余りが０になったので、３２１９と６２９の最大公約数は３７ということが求まりました。こうやって機械的に求まるので、ややこしい数のときは有効ですね。では次に、何故このような方法で最大公約数が求まるのでしょうか？その仕組みを図を使って解説してみます。

　まず、AとBの最大公約数をGと仮定します。すると、AもBも、G×（整数）と表現することが出来ます。つまり、AもBもGというレンガみたいなものが何個か積みあがって出来ているとイメージできます（下図右）。そして、AをBで割ったときの余りをCとして、次はBをCで割ります。（下図中）

 　これをどんどん繰り返していくと、最終的に、上図左のようにレンガ１個分で割り切ることが出来るはずです。こうやって残ったものがG、つまり最大公約数なわけです。

　いかがでしょうか？イメージ的には、割り算というよりは、大きい数を小さい数で削り取っていく感じです。そしたら最後は、AとBの共通の最小単位のレンガが残る。それが、最大公約数というわけです。

　具体的な数字で説明した方が分かりやすかったかもしれませんが、少しはイメージしていただけましたでしょうか？分かりやすかったよ！って方は、フォローなどしていただけると嬉しいです。