🔙 Back to Top

Tue Oct 21 22:34:41 JST 2014

拡張ユークリッド互除法

地味に苦手。

正の整数の対 (m, n) に対して、 gcd(m, n) を g としたら、

a * m + b * n == g

となるような整数の対 (a, b) が存在する。

拙作 milk を使ってる。

で、やりたいのは多倍長でないと扱えないような数だったのを思い出して慣れないCommon Lisp で書いてみた。