ユークリッドの互除法

多くの人が, 割る数と商 quotient, 余り remainder から元の数を復元する方法として次の定理を習っていると思う。 (勿論定理の名前は初めて聞くと思われるが) (証明は [高木] p. 2 定理 1, 2 を見ること)

[除法定理 division algorithm]
任意の整数 a, b (但し b > 0) に対して唯一組の整数 q, r が存在して
a = bq + r, (0 ≤ r < b)
が成立する。

さて, ユークリッドの有名な「原論 Elements」の第 7 巻の命題 1 と 2 が 有名な「ユークリッドの互除法 Euclidean algorithm」である。最古のアルゴリズムの一つであり, 最大公約数 greatest common divisor, greatest common measure を求めるのに殆ど改良の余地のない 算法である (ほんの少しだけ現在では改良されているが, 殆ど実用上影響がない)。

とりあえず, ユークリッドの原文を見てみよう (日本語訳だが)。

命題 1: 二つの等しくない値が与えられ, 小さい方の数を大きい方の数から引けるだけ引いていく。 これを繰り返し行っていってもしも最後に 1 が残るのならば, 最初の二数は互いに素である。

命題 2: 互いに素ではない二数が与えられたときに, それらの最大公約数を求める方法。

というわけで, 命題 2 は「命題」ではないのだが, そのあとを見ると今日 ユークリッドの互除法と呼んでいるものと同じになる。

現代流に直すと次のような定理になる。

定理: a = bq + r, (0 ≤ r < b) に対して, b と r の約数は, a, b の約数でもある。

この定理は一寸考えてみれば明らかであろう。

この定理から, a, b の約数を求めるには, 一回割り算して b と r の約数を求めれば良くって, b と r の約数を求めるためには, もう一度割り算して b = rq 1 + r 1 の r と r 1 の約数を求めれば良く, そのためには r 1 = r 1q 2 + r 2 の r 1 と r 2 の約数を求めれば良く,... &c.

というようにしていくと, 除法定理によって b > r > r 1 > r 2 > ・・・> 0 だから (有限回で) 必ず終って, 最後に割り切ったときの「割る数」が最初の a, b の最大公約数になっているのである。

これは所謂(いわゆる)再帰的アルゴリズム recursive algorithm であるが 実装する際には必ずしも再帰的呼び出しを行う必要はない。現にここでの applet は for 文で実装されている。

又, 同様のことが (体が係数になっている一変数の) 多項式環でも成立することが知られている。

さてまた, a, b の最小公倍数 M についても次の事が知られている。最大公約数を d とする。

定理: ab = Md.

ここの applet はこれを用いて最小公倍数を求めている。

Saturday, 25th March, 2000.

参考文献:
岩波数学辞典 第 3 版, 180「初等整数論」の項。
高木貞治: 初等整数論講義, 第 2 版, 共立出版。
The Thirteen Books of Euclid's Elements, translated from the text of Heiberg, with introduction and commentary by Sir Thomas L. Heath & al., Dover Publications, INC. (日本語訳も出ている筈)

BACK