ユークリッド幾何（0928）その１

福西です。前回、帰り際にABC予想の話を少ししたら、3年生のA君が興味を持ってくれたようでした。

 

そこで、今回は数論の入り口でもある「ユークリッドの互除法」を取り挙げました。その名のとおり、『原論』（第７巻命題1～3）にある定理です。また今学期は、3年生のＡ君は作図法によるアルゴリズムをテーマにしてきましたので、「世界最古のアルゴリズム」とされるこの定理を、ぜひ自分の手でも証明してほしいと思いました。

 

ユークリッドの互除法は、二つの数の最大公約数を求めるアルゴリズムです。小さい数ならまだ素因数分解に頼れますが、桁が1つ2つと増えるごとに、その苦労が10倍、100倍になっていくとしたら、その苦労をせめて2倍、3倍程度におさえたいものです。そこで考え出された方法です。

 

たとえば108と63の最大公約数は、以下のようにして求めます。ここで、（a,b）＝mは、「aとbの最大公約数はmである」ということを表す記号とします。

 

（108,63）＝（63,108－63）…（１）

＝（63,45）＝（45,63－45）

＝（45,18）＝（18,45－18×2）

＝（18,9）

＝9

 

よって、（108,63）＝9。

 

さて、（１）の部分でしていることは、まずa÷bをして、そのあまりを取り出しています。そしてそのあまりをrとすると、（a,b）＝(b,r)と式を書きかえているということです。（これを「作業」と呼びましょう。そして、なぜこの作業をすれば上手くいくかは、あとで証明することになります）。

 

（作業）

a＝b×1＋r　（r＜b）

r＝a－b×1

（a,b）＝（b,r）

 

そしてa＞bとすると、rは必ずbよりも小さくなるという性質があります。次は、bをrで割り、またあまりを出します。つまり、この作業を繰り返していくと、rはだんだん小さくなります。（そして「あまり」が０より小さくなることはありません。これもミソです）。小さくなると言うことは、いつか0になります。あまりが0ということは、すなわち割り切れた状態です。その時が、最大公約数の求まったときである、というのがユークリッドの互除法の主張です。またそのように「同じ作業」を「有限回」繰り返すことによって答を求められることが、「アルゴリズム」といわれる由縁です。

 

式だとまだ直感的にわかりにくいので、今度は、絵（図形）で見て行きましょう。

 

まず、横長に長方形をかきます。そして長いほうをa＝108、短いほうをb＝63とします。そして次のような問題を考えます。

 

問い

上の長方形を「できるだけ大きな正方形」のタイルで敷き詰めよ。ただし正方形の一辺は自然数とする。

 

ユークリッドの互除法の方針は、「まず、長方形の中から、最大の正方形を（可能な個数）とりのぞけ」ということです。

 

つまり、最大とは、その長方形の短い方の辺を一辺とする正方形になります。そしてそれをとりのぞくと、あまった部分にまた長方形ができます（左図）。

 

その長方形に対し、「また、最大の正方形をとれ」というのが、互除法の要請です（右図：90度回転させています）。このように、あまった部分にできた長方形から、どんどん長方形の短い方を一辺とする正方形をのぞいていきます。

 

最初の長方形は、たて108よこ63でしたが、一辺63の正方形をとりのぞくと、次にできた長方形は、たて63よこ45です。そこから一辺45の正方形をとりのぞくと、たて45よこ18のちょうほうけいができます。この流れが、（108,63）→（63,45）→（45,18）に対応しています。

 

たて18よこ45の長方形から一辺18の正方形を2個とりのぞくと、たて9よこ18長方形ができます。そして、これはいよいよ、一辺9の正方形で「きれいに」埋め尽くせます。

 

ということは、全体（たて108よこ63）の長方形も、一辺9の正方形で埋め尽くせることになります。

 

なぜなら、

一つ前のステップの「一辺18の正方形」も「一辺9の正方形」で埋め尽くせて、

その前の「一辺45の正方形」も「一辺18と一辺9の正方形」で埋め尽くせて、

その前の「一辺63の正方形」は、「一辺45と一辺18の正方形」で埋め尽くせて、

そして、もとの「たて108よこ63の長方形」は、「それ以前の正方形」で埋め尽くせる

からです。

 

これをふたたび式に書きあらわすと、

 

108＝63×1＋45…（２）

63＝45×1＋18…（３）

45＝18×2＋9…（４）

18＝9×2…（５）

 

これを逆からたどっていって、

18は9で割り切れる。そしてこの9が18を割る最大の数である。…（５）

45は、18×2＋9だから、（５）から、9で割り切れる。…（４）

63は、45×1＋18だから、（４）と（５）から、9で割り切れる。…（３）

108は、63×1＋45だから、（３）と（４）から、9で割り切れる。…（２）

 

よって、（２）と（３）から、108も63も、9で割り切れる。そして（５）から、この9が最大の公約数である。

 

これが互除法の主張していることでした。

 

さて、3年生のＡ君には、互除法がなぜうまくいくのか、その根本のところである、以下の式の証明を考えてもらいました。

 

a,bはa＞bの自然数とする。

a＝bq＋r、0≦r＜bとするとき、

（a,b）＝m　⇒　（b,r）＝m

であることを証明せよ。

 

Ａ君の証明（途中）

ステップ１

（a,b）＝mだから、aはmの倍数。またbもmの倍数。

さて、r＝a－bqなので、a、bがmの倍数だから、rもmの倍数。

よって、mはbとrの公約数。

 

ステップ２

次に、mがbとrの「最大」公約数であることを示す。

（a,b）＝mだから、a＝ma’、b＝mb’。

mはaとbの最大公約数だから、a’とb’は公約数を持たない。←注：「互いに素」。式では（a’,b’）＝1と書けます。

r＝a－bq

＝ma’－mb’q

＝m（a’－b’q）。

一方、

b＝mb’。

そして、a’－b’qとb’が「公約数を持たない」ことを示せば良い。

 

授業でA君が考えてくれたのは、ここまでです。あともう一押しですね。

最後のことを示すためには、先に確認してくれた「a’とb’は公約数を持たない」ことが使えます。

 

もしこれが証明できれば、最大公約数が次々と前の項を「あまり」でわったその「あまり」の中に保存されていくことがいえます。あとは、rが徐々に小さくなっていき、やがては0になる性質から、繰り返しが有限回で終わることがいえます。

 

すなわち、今添え字を使って、

aをa0、

bをa1とし、

そのつど出てくるあまりのr1、r2…を、a2、a3…とすると、

 

（a0,a1）＝（a1,a2）＝（a2,a3）＝…＝（a(s),a(s+1)）＝…＝（a(n－1),a(n)）＝（m・a(n),a(n)）＝m

a0＞a1＞a2＞…a(s)＞a_(s+1)＞…a(n)＞a(n＋1)（＝r(n)）＝0、ｎ<∞

 

と言えることになります。