- 145 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/10 23:50]
- C=aX+a"=bY+b"=cZ+c"=dW+d"(X,Y,Z,Wは0以上の整数)
となる最小の正の数Cを求めます。
cZ+c"=dW+d"
となる最小の正の数を(cd)"とすると
(c*d)V+(cd)"=cZ+c"=dW+d"
となります。今度は
bY+b"=(c*d)V+(cd)"
となる最小の正の数を(bcd)"とすると
aX+a"=(b*c*d)U+(bcd)"
・・・以下同じ・・・
拡張ユークリッドの互除法を繰り返していけばOK
