数学学習記 その８

ふー。出来た。
これでいいはず。これでいいはず。筈。たぶん。

ユークリッドの互除法の説明。互除法というのは２数の最大公約数を求める操作です。文中では便宜的に「ａとｂの最大公約数」を「 (a,b) 」と表記します。では、以下。

突然ですが、とりあえず、長さ５１の線分を３６で割ってみる。

５１÷３６＝１あまり１５
このとき、１５が (51,36) の第一候補となる。図を見れば分かるように、３６から５１までは１５が一つ分しか差がなく、すなわち１５なら３６と５１の間を最小の一度でまたぐことができる。九九で１５の段を数えていったときに３６のちょうど次に５１がくるイメージ。なので１５が３６と５１の公約数であると仮定すれば、それより大きい公約数は存在しない筈である。
もし、１５より大きい公約数を仮設したら、３６の次に５１がくることはない（図参照・３６までピッタリ合った（式としては公約数が１６だったら１６×ｎ＝３６）として、そこから１５より大きい数を加えると必ず５１オーバーになる）また、３６にピッタリ合わなければそもそも３６の約数ではない。すなわち、１５より大きい数は公約数になりえない。
こうして「もし１５が３６と５１の公約数ならば、直ちに１５が最大公約数になる」ことが決まる。
では１５が公約数でなかった場合どうするのか。そのときは１５の約数が候補にあがる。３６と５１の公約数はとにかく３６を等分し、同時に５１も同じ大きさに等分する。となると図で考えれば１５も完全に等分する筈だからである（図の直線の上下に同じ間隔で目盛を振っていくイメージ）。

では１５は本当に３６と５１の公約数なのか。手始めに３６について調べる（また、１５が３６の約数であることが分かれば図から５１の約数であることも判断できる。３６が１５で等分できれば、残るのは１５だけなので、全て１５で等分できるようになるからである）。では実践。

３６÷１５＝２あまり６
割り切れませんでしたー！

よって１５は (51,36) ではないことが分かった。次の段階として二つ上の段落に書いたように、今度は１５の約数でなるべく大きいのを試したい。このとき、３６と１５の最大公約数 (36,15) を探すことになる。というのは、元々３６と５１の最大公約数を求めているのだから、１５の約数であっても３６の約数でなかったら本末転倒なのである。
で、前に書いてある説明に基づき、６が３６と１５の最大公約数であることが予想され、さっきと同じようにやっぱり１５だけ調べればいいから、

１５÷６＝２あまり３
割り切れませんでしたーーー！！！　畜生！！

よって６は (36,15) ではないことが分かった。引き続き (36,15) を探すことになる。ところで……あなたは気付いていたでしょうか。本来は５１と３６の最大公約数を探していました。ところが今、私達が求めているのは３６と１５の最大公約数。これはループ。たらい回し。マトリョーシカ。しかし物語は必ず結末へと収束する。明けない夜はない。この構造は問題の核心に向かって渦を巻いているので安心してよいのです。
気を取り直して、 (36,15) について。ここまでで (51,36) のときと同じようにして「６！」と予想を立てたが、見事に外れた。こんなときどうしたか。あくまでルールに従うとすれば……そう、次の候補は「６の約数」である。そして、探すのは「１５と６の最大公約数」（なんで？　という人はひとつ上の段落を見よう！）。んで、そいつは「３！」と予想がつく（ひとつ上の式を参照）。もちろん６だけを調べればオッケー。てなわけで

６÷３＝２
割れた！！！

こうして (15,6) が３である、ということが分かった。この (15,6) がそのまますなわち (36,15) になり（ひとつ上の段落参照・ (36,15) を探していて (15,6) が出た）、やがては (51,36) となる（ (51,36) の候補の一つとして (36,15) があがった）。
(51,36) ＝ (36,15) ＝ (15,6) ＝３
これで完了。
結局、互除法というのは割り算を繰り返して最大公約数を求め続ける操作なのでした。で、最終的に割り切れたところの“割る数”が元々求めたかった最大公約数である、と。

• • • • • • • • • • • -

以上。……で！　どうでしょう。これで。なにぶん門外漢の書いたものですから不備などあると思いますし、この説明も長い＆分かりづらい / わけがわからないかも知れません（書いている僕でさえしばしば現在位置を見失いました）。ただ、互除法の理解で悩んでいる方いましたら（いるのか）、これが少しでもヒントになれば素敵だなあと思います。