ユークリッドの互除法 （12/5）

ユークリッドの互除法
さて、ユークリッドとは実在する人物の名前なんだけれど、ユークリッドの生涯については、詳しいことはほとんど分かっていないらしいです。


【公約数について】

　例えば、３０と４５の約数は、

３０の約数・・・１、２、３、５、６、１０、１５、３０
４５の約数・・・１、３、５、９、１５、４５

ですから、２つの約数のうち共通の｢１、３、５、１５｣の４つの数字が３０と４５の公約数となります。
また、公約数のうち最大の約数を最大公約数といい、この場合１５となります。ここで、最大公約数を求めるときに、いまのように１つ１つ約数を取り上げて比べていくのではなく、もっと簡単に求める方法があります。その方法がユークリッドの互除法です。


【ユークリッドの互除法について】

　これは前述の「原論」の第７章にやや異なった形で述べられていますが、それはユークリッドよりも１００年ほど前にすでに発見されていたと伝えられているそうですよ。

【ユークリッドの互除法】

２つの整数aとbについて、

a をb で割った余りをr1 　(b >r1)
b をr1で割った余りをr2 　(r1>r2)
r1をr2で割った余りをr3 　(r2>r3)
　　・・・・・・・・・・
としていくと、r1>r2>r3･････≧0 となって余りはいつか0になる。

そこで余りが○>□となって、○が□で割り切れたとすると、□が最大公約数である。

もうちょっと一般化していうと、２つの整数aとbがあり、aがbで割り切れないとき、kを任意の整数として、aとbの最大公約数はa+bkとbの最大公約数に等しいということです。


それでは、６０と１６８の最大公約数をこの方法で求めてみることにします。

１６８÷６０＝２ 余り ４８
　６０÷４８＝１ 余り １２
　４８÷１２＝４ 余り 　０ →　４８が１２で割り切れるので、１２が６０と１６８の最大公約数となる。

ユークリッドの互除法を使うと、いつか必ず割り切れて、そのときの割った数が最大公約数となります。
（ユークリッドの互除法はＮ桁の数に対して５Ｎ回以内で終了することがわかっています。）

でも、なぜこんなにも簡単に最大公約数が求まるのか不思議ですね？どうしてこうなるのかは説明が難しくなりますが下記の通りです。（わからない人はとばしてもいいでしょう）


【互除法の原理の証明】

２つの整数aとbの最大公約数をＧとおくと、a=a'Ｇ，b=b'Ｇ(a'とb'は互いに素(注))とおける。
（注；互いに素とはa'とb'の公約数が1以外にはないということ。）
同様に、bとrの最大公約数の最大公約数をＧ'とおくと、b=b''Ｇ'，r=r'Ｇ'となる。

このことを以下の①～③で利用して考えてみる。

① aをbで割ったときの商をq，余りをrとすると、a=bq+r (0≦r　 r=a-bq となる。
　ここで、２つの整数aとbは、a=a'Ｇ，b=b'Ｇとおけるから、
　 r=a'Ｇ-b'Ｇq=(a'-b'q)Ｇと表せる。

　すなわち、r=r'Ｇ'であることから、ＧはＧ’の約数である。

② b=b''Ｇ'，r=r'Ｇ'より、a=bq+r=b''Ｇ'q+r'Ｇ'=(b''q+r')Ｇ'となる。

　すなわち、a=a'Ｇ であることから、Ｇ’はＧの約数である

③ ①と②が同時に成り立つので、Ｇ＝Ｇ’である。

以上のことをもう少し簡単に表現すると、aをｂで割ったときの余りrは、aとbの最大公約数を因数にもつ。言いかえると

『aとbの最大公約数はbとrの最大公約数と考えてよい。』ことがわかります。


この証明は、いわゆる｢必要十分条件｣という考え方から導かれる証明法で、なかなか説明して理解させるのに苦労します。しかも、aやらbやらたくさんの文字を使用するので、読むのさえ苦労することでしょう。



それでは３００７と１６４９の最大公約数をユークリッドの互除法を使って求めてみましょう。！！とてもじゃないけれど最初にしたように２つの数のそれぞれの約数を並べて比較するなんて大変ですよね？ユークリッドの互除法（先人の知恵）のありがたさをつくづく感じてしまいます．．．

（答えは９７となります。）



↑の文章が理解できないという人は、↓にわかりやすい説明を載せました。２数を割られる数、割る数とすると、


割られる数÷わる数＝あまり①
わる数÷あまり①＝あまり②
あまり①÷あまり②＝あまり③
あまり②÷あまり③＝0

あまり③が最大公約数。


つまりはこういうことです。

Ｑ，Ｅ，Ｄ