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

 

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

 

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

 

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

 

(108,63)=(63,108-63)…(1)

=(63,45)=(45,63-45)

=(45,18)=(18,45-18×2)

=(18,9)

=9

 

よって、(108,63)=9。

 

さて、(1)の部分でしていることは、まず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になります。あまりが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…(2)

63=45×1+18…(3)

45=18×2+9…(4)

18=9×2…(5)

 

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

18は9で割り切れる。そしてこの9が18を割る最大の数である。…(5)

45は、18×2+9だから、(5)から、9で割り切れる。…(4)

63は、45×1+18だから、(4)と(5)から、9で割り切れる。…(3)

108は、63×1+45だから、(3)と(4)から、9で割り切れる。…(2)

 

よって、(2)と(3)から、108も63も、9で割り切れる。そして(5)から、この9が最大の公約数である。

 

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

 

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

 

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

a=bq+r、0≦r<bとするとき、

(a,b)=m ⇒ (b,r)=m

であることを証明せよ。

 

A君の証明(途中)

ステップ1

(a,b)=mだから、aはmの倍数。またbもmの倍数。

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

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

 

ステップ2

次に、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、n<∞

 

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

Share