一松信の「暗号の数理」を読んでいたら「ユークリッドの互除法」というものがでてきた。二つの正の整数m、nの最大公約数を求めるアルゴリズムである。下記のような手順だ。
- mとnを比較し、必要なら入れかえてm≧nとせよ。
- mをnで割り、商をq、余りをrとせよ。
- 余りrが0(割り切れた)なら、そのときの除数nが最大公約数である。これで完了。
- 余りrが0でなければ、除数nと余りrとをm、n,と置き直して、2.へ戻れ、
この操作を反復すれば、いつか必ず3.に逹っして、完了するであろう。
——一松信「暗号の数理」より
で、なんで、これで最大公約数が求まるのだろう……。
ピンとこなくて考えこんでしまった。
うーむ。
n自身が最大公約数のとき、求まるのはわかる。では2周目はどうだろう。一回目のrが最大公約数の場合。もちろんそのときはrでnが割り切れるはずだ。もちろん、mも割り切れる(mはnとrに分解できるのだから)。
あ、なるほど。そういうことか。
あとは以下同文。
(defun Euclid(m n)
"ユークリッドの互除法。m、nの最大公約数を求める。"
(if (< m n)
(Euclid n m)
(progn
(let ((q (/ m n))
(r (mod m n)))
(if (= r 0)
n
(Euclid n r))))))
(Euclid 25 5) 5 (Euclid 7 5) 1
