「ユークリッドの互除法」最大公約数を算出するアルゴリズムの証明

約数? 因数?

 0でない整数aとbがあるとする。
数字ガラクタ「数字と数式の種類」数学の基礎の基礎。 ここでaがbを割りきれるとする。
つまり適当な整数kがあるとして、b = akの形を作れるとする。
aはようするにbの約数というやつである。
aが1かbしか成り立たないなら、bは素数ということになる。
123「素数とゼータ関数」リーマン予想に晒された架空の実領域  そうではないとする。
例えばaが1と6以外に2と3なら、bは6であろう。
6の約数は1、2、3、6である。
そういうのはまた「因数いんすう(factor)」と呼ばれる。

 約数と因数は 基本的に同じ意味なのだが、因数の方がやや抽象的な感じがする。

gcd。最大公約数の示し方

 それではまた、2つの整数a、bをあらためて用意する。
それらのどちらの約数の中にもkがある場合、kはaとbの「共通因数(Common factor)」とか「公約数(Common divisor)」などと言う。

 例えば4は12と20の共通因数(公約数)である。
またこの場合の4は12と20の共通因数の中で最大の数、いわゆる「最大公約数(greatest common divisor)」となる。

 ある数と数の最大公約数の書き方として、以下のようなものがある。
gcd(a、b)
例えば gcd(12、20) = 4 みたいな感じである。

 gcd(greatest common divisor)でなく、gcm(greatest common measure)が使われる場合もある。
また、もし gcd(a、b) = 1 なら、「aとbは互いに素である(a and b are relatively prime)」とかいうふうに表現される。

X+XがYで割れるなら、X+X+XもYで割りきれる

 例えばxで割りきれる数yがあるとする。
この場合y = x + x + x……も同然であろう(ここではこれは詳しく定義はしない。時には直感が大事である)。
x + x + x……というのは有限の数とする。
しかしx + x + x……の形なら、xで割りきれる数だから、明らかにx + x + x……+ xも、xで割りきれる数である。
森の扉「無限量」無限の大きさの証明、比較、カントールの集合論的方法  やはりこういうのは、ちゃんと数字をあてた方がわかりやすいという人もいるだろう。
45は5で割りきれるわけだが、45というのは5×9でもある。
5×9+5は、つまり5×10であり、やはり5で割りきれる50である。

 つまり何が言いたいかというと、xで割りきれる数yがあるなら、y + xもまたxで割りきれるということである。
このことを理解しておくことは、以下の話を理解するのに役立つ。

ユークリッド・アルゴリズム

 aとbの最大公約数を求めたいとする。
力押しでもいいし、コンピューターの助けを借りてもいいが、なるべく早くすませたく、コンピューターも使えない状況なら、「ユークリッドの互除法ごじょほう(Euclidean Algorithm)」というのが便利である。
おそらくaとbの数が大きければ大きいほど、その威力を実感できる。

 場合によっては、ごく簡単である。
例えばaとbがあってaがbで割りきれる数なら、それすなわちbがaとbの最大公約数である。
例えば100は10で割りきれるわけだが、 gcd(100、10) = 10 なわけである。

 しかし例えば1000と562ならばどうか。
この場合1000を562で割ると明らかに438余ってしまう。
それと、そんな計算はわざわざするまでもなく、1000の約数に562が入ってないのは明らかすぎる。
つまりこの時、562が公約数はありえない。
こういう場合に、わざわざ1000と562の約数を全て算出し、照らし合わせていかなくても、これらの最大公約数を見つけることができる術がユークリッドの互除法である。
幾何学なぜ数学を学ぶのか?「エウクレイデスと原論の謎」

余りを余りで割っていく

 以下の話において、aとb以外は定数でないことには注意(エッセー1)。

 aとbを割ると、余りがsでてくるとする。
この場合に商(割り算の答)がqだとすると、以下の形を用意できる。
a = q × b + s(1)
ここからちょっとしたアルゴリズムを作る(仮にYアルゴリズムと呼ぶことにする)。

 (1)におけるaとqのことはもう忘れ、次にbをsで割る。
するとまた、そこで新たな商qと余りsが発生するだろう。
つまり(1)のsを区別のためs_とすると、また以下のような形が現れる。
b = q × s_ + s(2)
以降、(2)の式の場合のbをs_に、s_をsに置き換える作業を、式のsが0になるまで繰り返していく。

 言葉で説明するならこのYアルゴリズムは、ある数xをyで割り、出てきた余りでyを割る。
さらにそうして出てきた余りで、前の式の余りを割るというのを、余りが0になるまで繰り返すというものである。

(エッセー1)ワタシはツカイマワスノがスキ

 今は数学よりもコンピューターのプログラミングに慣れてる人の方が多いだろうし、多くなっていくと思う。
プログラミングでは、ある変数を使い回したりすることもある。
だから数学の思考などにおいても、使い回せるものは使いまわすのがよいと思う(ある程度慣れてる人が多いだろうし)。

 個人的には、p1、p2、p3……とか、pn-1、pn、pn+1……みたいなのは、むしろわかりにくいと思います。

やがては必ず0になる

 Yアルゴリズムに終わりがない可能性はあるだろうか。
そんなものはおそらくない。

 このアルゴリズムの肝は、あるふたつの数a、bの商qと余りsを求める形の式 a = q × b + s である。
これの余りsだが、それがbより大きい数であることはありえないだろう。
大きい数だとしたら、qをしかるべき数だけ倍化して、また小さくなるだけだ。
そしてYアルゴリズムでは、次式のbのポジションに現在のsが入ることになる。
つまり次式の余りは、現在の余りよりさらに小さくなるのは必然。

 Yアルゴリズムにおいて、余りsは小さくなっていくわけだが、そうなると、やがては0になるのも必然というわけである。
ゼロの空間的な何か「ゼロとは何か」位取りの記号、インド人の発見  そしてこのYアルゴリズムこそが、そもそもユークリッドの互除法の肝なのである。

アルゴリズムが止まった時

 ある数aとbに対し、Yアルゴリズムを適用させてみる(数字は掛け算とかでないことに注意)。

a = q × b + s(1)

b = q2 × s + s2(2)

s = q3 × s2 + s3(3)

s2 = q4 × s3 + s4(4)

s3 = q5 × s4 + s5(5)
……みたいな感じで繰り返されるわけだが、仮に(5)における余り(s5)が0になったとする。
つまり s3 = q5 × s4 + 0(5) になり、アルゴリズムが止まったとする。
肝心なのはここからだ。

つまり公約数

 まず(5)から、s3がs4で割りきれる数なのは明らかであろう。
割りきれないなら余りは0でないはずだから。

 ここで、xで割りきれる数yがあるなら、y + xもまたxで割りきれるということを思いだそう。

(4)の式からs2は、s4で割りきれる数であるs3 + s4である。
つまりs2はs4で割りきれる。

 同じように考えていけばs2もsも、そしてbとaもs4で割りきれるということになる。

 つまりs4は、aとbの公約数である。

その中で最大の数でもある

 次にs4とは別に、aとbの別の公約数zがあるとしよう。
アルゴリズムの最初の式 a = q × b + s(1) を用意する。
zは、aとbのどちらも割りきれるわけだから、(1)が成り立つならsも割れなければおかしい。

 続いて次の b = q2 × s + s2(2) はどうか。
zはbとsのどちらも割りきれるわけだから、s2も割りきれなければおかしい。

 やはり同じように考えていけば、zはs4を割りきれることになるが、だとするとzがs4より大きいはずはない。

 というわけで、いよいよ結論が出てくる。
つまりYアルゴリズムの最後の式の前の式の余りsN(今回の上記例の場合はs4)こそが、aとbの最大公約数である。
なぜならそれは公約数でかつ、他のどの公約数zよりも大きいから。

 そしてこのYアルゴリズムの性質を利用して、2つの数a、bの最大公約数を見つける手法こそが、ユークリッドの互除法というものである。

具体例。例えば1000と562の場合

 実際にユークリッドの互除法で、1000と562の最大公約数を求めてみる。

1000 = 1 × 562 + 438(1)

562 = 1 × 438 + 124(2)

438 = 3 × 124 + 66(3)

124 = 1 × 66 + 58(4)

66 = 1 × 58 + 8(5)

58 = 7 × 8 + 2(6)

8 = 4 × 2 + 0(end)

 つまり、1000と562の最大公約数は(6)の式の余り、すなわち2なわけである。

 それと、最低限の機能の電卓でa = q × b + sの形を比較的簡単に求めるためには、まずa÷bを普通に行う。
電卓なら余りがいくつとかはでないで、普通に答は小数になるはず。
その答の小数の小数点以降の数を全て切り捨てる。
切り捨てた後の答えが、式のqにあたる。
sに関しては a – b × q で求めれる。

コメントを残す

メールアドレスが公開されることはありません。

CAPTCHA