« れおぱるど | トップページ | やってしまった・・・ »

2007/10/27

やっと分かった。

”一次合同式の解x”と”拡張ユークリッドの不定方程式の解x”の扱い方がやっとわかった。

考えてた問題は、正の値で出せばよかったようだ。

この条件さえ出されれば問題は解決。拡張ユークリッドの不定方程式で求まったxの値を利用すればいいわけです。このxの値が正ならそのまま合同式の解として採用し、もしxの値が負ならこの値にb(ax ≡ 1 mod b のb)を加えることで合同式の解とすることができます。

この処理を文章どおりに書くとif文になってしまいますが、X = (x + b) % b (X:合同式の解、x:不定方程式の解)とすれば一行で求まります。

|

« れおぱるど | トップページ | やってしまった・・・ »

Algorithm」カテゴリの記事

コメント

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/222903/16889027

この記事へのトラックバック一覧です: やっと分かった。:

« れおぱるど | トップページ | やってしまった・・・ »