ユークリッドの互除法は最大公約数を計算する効率的な方法として古くから知られている方法です。最も古いしかし重要なアルゴリズムと言えます。ここではこれについて説明します。 ユークリッド（-３３０？～-２７５）はユークリッド幾何学の名前で有名な古代ギリシアの数学者です。 ユークリッドは非常に有名ですが，ユークリッド自身についてはあまり知られていません。確実なことは彼が「原論」と言われる著作を 残したことぐらいです。 ユークリッドの「原論」は昔「幾何学原論」といわれたこともありましたが，「原論」はいわゆるユークリッド幾何学の原典です。このユークリッド「原論」は全１３巻からなる大著で，その全貌を見るのは大変ですが，幸い共立出版から日本語訳が出ていて，身近に触れることも出来ます。比較的大きな図書館には蔵書されていると思いますから，興味のある人は一度ご覧になってみると良いと思います。 この「原論」は幾何学だけでなく数論も含んだ，当時のギリシア正統的数学の集大成ともいえるものです。 ユークリッドの互除法は「原論」第７巻命題１から命題３に書かれている方法のことです。ユークリッドの互除法という名前もこのことに由来します。数学史の研究によると，「原論」はユークリッド自身の著作と言うよりは，当時の数学をまとめた著作と言われています。そしてこの成果はもう少し前のピタゴラスの時代のものと言われています。ですから本当はピタゴラスの互除法というのが正しいかもしれません。
ユークリッドの互除法は２つの自然数 a，b の最大公約数を計算する方法です。 a と b の最大公約数の計算方法として，a と b を素因数分解してその共通項を見つけるというものがあります。この方法は小さい数の場合は計算に適していますが，a と b が少し大きくなるとこの方法では出来ません。 例えば，15 と 21 の最大公約数は 15=3・5 かつ 21=3・7 なので，3 となります。 しかし，12707 と 12319 の最大公約数をこの方法で簡単に計算できるでしょうか。勿論頑張って，12707 と 12319 の素因数分解を見つけるという道もあります。しかし，実は 大きな数の素因数分解は難しい のです。この大きな数が素因数分解が難しいと言う事実は有名なことで，暗号系の中にはこの事実を使って安全性を保証しているものもあります。 一般に素因数分解は難しいのですが，実は最大公約数の計算には効率的なうまい方法があるのです。それがユークリッドの互除法です。
ユークリッドの互除法の原理を説明しましょう。 a と b の最大公約数を GCD(a, b) と表します。a > b > 0 とし，a を b で割った時のあまりを r >=0 とします。このとき次が成立します。 GCD(a,b)= GCD(b,r) このことの証明をしましょう。a を b で割ったときの商を q とすると， a = q*b + r， あるいは移項して r = a - q*b と表されます。簡単のためGCD(a,b)を c と表します。c は a と b を割り切りますから，上の右式から，r も割り切ります。従って c は b と r の公約数になります。特に c <= GCD(b,r) となります。そこで逆にGCD(b,r)を c' とします。このとき上の左式から c' は a を割り切ることが分かります。従って，c' はa と b の公約数です。従って c' <= GCD(a,b)=c となります。故に上の c <= GCD(b,r)=c' とあわせてc=c' となります。 この命題の内容を説明しましょう。この命題は GCD(a,b) は GCD(b,r) に等しいと言っています。ですから，GCD(a,b) を求めるには， GCD(b,r) を求めれば良いわけです。ここで a>b>r の関係があることに注意しましょう。a , b に比べて b, r の方が小さいので計算が簡単なはずです。もし GCD(b,r)が分からなかったら，今度は b を r で割って同様なことを行えばもっと簡単になります。上の操作は割り算が出来る間続けられますから， GCD(x,0), x>0 の形になるまで，続けられます。明らかに GCD(x,0)=x ですから，これで求められました。
上の例で実際に計算をしてみましょう。 GCD(12707,12319) の計算 12707=1*12319+388， これから，GCD(12707,12319)=GCD(12319,388) 以上から， GCD(12707,12319)=97 となります。
上の例を見ると，a, b の大きさに比べて，計算の回数が少ないことに気が付いたでしょう。上の例が特殊と言うわけではありません。実は次のことが成立します。 GCD(a,b) (a>b) の計算で互除法の計算回数は b の桁数の５倍以下である。 これは素晴らしい事実です。 例えば１００桁の数の最大公約数でも高々５００回の計算で求まるということです。１００桁の数は例えば 100000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000 です！ |