フェルマーの小定理

質問

RSAの勉強をしています。そこで質問なんですが
p,qは異なる素数で
a^b≡x (mod p)
a^b≡x (mod q)
のとき、
a^b≡x (mod p*q)になるのは明らかなんでしょうか。

回答No.3

---------- · ベストアンサー

明らかですが、式で書いてみましょう。
a^bをcと置きます（ここではa^bに意味はなさそうなので）。
cもxも整数とします。

mod pとmod qの式から次の２つを満たす整数mとnが存在します。
c=pm+x
c=qn+x

上の２つの式の左辺同士は一緒なので
もちろん、右辺同士も一緒で、
pm+x=qn+x
が得られ、
pm=qn
がわかります。

ここで、pとqは互いに異なる素数なので、
pm=qnから、mはqの倍数でないといけません。
つまり、m=qMとなる整数Mが存在します。
これを一番初めの式に入れると、
c=pm+x
=pqM+x
となり、これは
c≡x(mod pq)
をあらわしています。

お礼

回答ありがとうございます。おかげで納得できました。
どうやらフェルマーの小定理とは関係ないところで悩んでいたようですね。

回答No.2

koko_u_

直観的には明らかですが、数学的には証明を必要とします。

つまり、「整数 n について、n が p、q で割り切れれば、pq でも割り切れる。」( n が a^b - x ということね)

普通は、p、q が互いに素であれば px + qy = 1 となる整数 x y が存在することを利用するのが簡単でしょう。

回答No.1

BaritoneSax

明らかです。
１　a^b≡x (mod p)
２　a^b≡x (mod q)
１式は　（a^b）はｐの倍数よりｘだけ大きい。
２式は　（a^b）はｑの倍数よりｘだけ大きい。

a^b≡x (mod p*q)　ｐ掛けるｑはｐの倍数であり、かつ、ｑの倍数です。　ｐもｑも素数ですので１以外に公約数はないので（a^b）は（p*q)の倍数よりｘだけ大きくなります。