![ユークリッド幾何(0928)その1](http://www.kitashirakawa.jp/yama-blog/wp-content/uploads/2023/05/2021-05-19-23.22.08-2-e1685531534636.jpg)
福西です。前回、帰り際に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<∞
と言えることになります。
“ユークリッド幾何(0928)その1” への1件のフィードバック