59. ユークリッドの互除法の証明の行間を埋める

私の世代は授業として整数を扱わなかったので、ユークリッドの互除法についても「名前はよく聞く」くらいで実態は毎回調べていました。

そんなことを人生で10回くらい繰り返している気がするので、そろそろ証明をちゃんと理解してメソッドを覚えたいと思います。

ユークリッドの互除法の主張は以下のとおりです。

整数の割り算の等式  において、 が成立する。

は「 と の最大公約数」です。つまり、「 と の最大公約数が知りたければ、 を計算して余り を求め、 と の最大公約数を調べれば良い」ということです。

これによってどんどん対象の数を小さくしていき、最終的に「余り 0」となった時点での が最大公約数になります。これは、 になったということから、 は の倍数である、つまり であることが分かったという意味です。

さて、これの証明ですが、非常にシンプルに記述されるものの若干癖があって、理解に引っかかる部分が多かったです。以下のサイトの証明を引用します。

manabitimes.jp

【証明】
 とする。

①
 と  は  の倍数なので、 も  の倍数になる。
よって、 は  と  の公約数。
最大公約数は公約数の中で最大のものなので、


②
 と  は  の倍数なので、 も  の倍数になる。
よって、 は  と  の公約数。
最大公約数は公約数の中で最大のものなので、


①,②より  が示された。

私はこの証明を見たときにスラスラ理解できなかったので、少しずつ行間を埋めていきましょう。①と②は証明構造は同じなので、①のみ考えます。

「 と は の倍数なので」について。

の定義からこいつは と の公約数です。そのため、 も も の倍数になります。

「 も の倍数になる」について。

先ほどの考察から、ある整数 を用いて 、 と置けます。よって、 となり、 も の倍数であることが分かります。

「よって、 は と の公約数」について。

先ほどの考察から、 が の倍数であることが分かりました。つまり、 は の公約数です。

「最大公約数は公約数の中で最大のものなので、」について。

ここが一番「ん？」となった部分です。まず、今まで について考えていたのですが、ここで注目しているものは に変化しています。「今までとは違う対象を考えている」ということに注意してください。
ここで考えているのは 、つまり と の最大公約数です。これが何になるのか？ということは今の時点では分からないですが、 と の公約数（最大とは限らない）については、今までの考察から1つ分かっています。それは です。
だから、 が成立しますよ、という文になっています。

②についての行間埋めも同様になります。

これで「 かつ 」が示されたので、「」である必要がある、ということでした。