ここから本文です

中国剰余定理について質問です。 pで割ってa余り、qで割ってbで余る数はpqの中...

pi_********さん

2010/10/1321:19:07

中国剰余定理について質問です。

pで割ってa余り、qで割ってbで余る数はpqの中に一つ存在する(pとqは互いに素)とのことですが
探し方とかってありますか?

例えば
p=17
q=12

だと
17×12=204個の中から探さないといけないわけですが。

補足回答ありがとうございます。

ちょっと分からなかったので質問させてください。
ー84a+85bですとa=2,b=1だとマイナスの値になってしまいませんか。
1~204の中にあると思うのですが。。。

閲覧数:
297
回答数:
1

違反報告

ベストアンサーに選ばれた回答

you********さん

編集あり2010/10/1506:37:20

まず、mp+nq=1となる整数m,nを見つけます(ユークリッドの互除法などを用いて見つけることができます)。
すると、nq≡1 (mod p), mp≡1 (mod q)となります。

そこで、x=anq+bmpとすると
x≡anq≡a (mod p)
x≡bmp≡b (mod q)
となり、x (mod pq)が求める数です。

p=17,q=12の場合を例に、ユークリッドの互除法を用いて整数m,nを求め、それを用いて解x (mod 17*12)を求めてみます。
まず、整数m,nを求めるため、ユークリッドの互除法を用いると
17=1*12+5、12=2*5+2、5=2*2+1
となります。
1=5ー2*2に、2=12ー2*5を代入して
1=5ー2(12ー2*5)
右辺を展開して、12と5についてまとめると
1=ー2*12+5*5
さらに、5=17ー1*12を代入すると
1=ー2*12+5(17ー1*12)
右辺を展開して、17と12についてまとめると
1=5*17ー7*12
よって、m=5,n=ー7となります。

そして、x=(ー7)*12a+5*12b=ー84a+85bとすると
x≡a (mod 17)
x≡b (mod 12)
となります。
ーーーーーーーーーーーーーーーーーーーーーーーーーー
【補足についての追記】
紛らわしくてごめんなさい。解は、xではなくてx (mod pq)です。
ご指摘のとおり、xは0から203までの範囲に入らないことがあります。その場合でも、必要に応じてxに17*12の倍数を加えるまたは減ずることで、X≡x (mod 17*12)で0≦X≦<17*12となるXが一意的に定まります。そういう意味で解は、x (mod pq)なのです。

質問した人からのコメント

2010/10/15 20:00:08

詳しい解説ありがとうございました。

あわせて知りたい

みんなで作る知恵袋 悩みや疑問、なんでも気軽にきいちゃおう!

Q&Aをキーワードで検索:

Yahoo! JAPANは、回答に記載された内容の信ぴょう性、正確性を保証しておりません。
お客様自身の責任と判断で、ご利用ください。
本文はここまでです このページの先頭へ

「追加する」ボタンを押してください。

閉じる

※知恵コレクションに追加された質問は選択されたID/ニックネームのMy知恵袋で確認できます。

不適切な投稿でないことを報告しました。

閉じる