• ベストアンサー

フェルマーの小定理

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) をあらわしています。

northbig
質問者

お礼

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

全文を見る
すると、全ての回答が全文表示されます。

その他の回答 (2)

  • koko_u_
  • ベストアンサー率18% (459/2509)
回答No.2

直観的には明らかですが、数学的には証明を必要とします。 つまり、「整数 n について、n が p、q で割り切れれば、pq でも割り切れる。」( n が a^b - x ということね) 普通は、p、q が互いに素であれば px + qy = 1 となる整数 x y が存在することを利用するのが簡単でしょう。

全文を見る
すると、全ての回答が全文表示されます。
回答No.1

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

全文を見る
すると、全ての回答が全文表示されます。
  1. カテゴリ
  2. 学問・教育
  3. 数学・算数

関連するQ&A

  • フェルマーの小定理

    http://www.math.kobe-u.ac.jp/~taka/asir-book-html/main/node96.html このサイトの"証明: 定理 17.2 をx = m^(q-1) mod pに対して適応すると"という行からひとつしたの (m^(q-1))^(p-1) = m^(n') = 1 mod p これはフェルマーの小定理を用いて導いてるのは分かります．しかし，m と p　が互いに素でなければ成り立たないはずなのにそこに言及していないのが気になります．なぜ成り立つのでしょうか？

  • フェルマの小定理について

    次の主張（フェルマの小定理）の証明を与えよ。 「ｐが素数のとき、aがpと互いに素な整数ならば、a^(p-1) ≡ 1 (mod p) が成立する。」 フェルマの小定理についてあまり詳しくないので分かりやすく教えていただけると嬉しいです。 宜しくお願い致します。

  • 中国剰余定理　3数

    余りが条件式を満たすがわからないので質問します。 p,q,rどの2つをとっても、互いに素な自然数とする。a,b,cを任意の整数とする。このとき、　x≡a mod(p),x≡b mod(q),x≡c mod(r) を満たす整数ｘが、0からpqr-1までの間に1つ存在する。この定理の証明は、 (qr)s≡1 mod(p),(rp)t≡1 mod(q),(pq)u≡1 mod(r),を満たすs,t,uを求めることから始まります。sであれば、(qr)s+py=1・・・(1)という１次不定方程式を解くことで、得られます。q,rがpと互いに素であるから、qr,pが互いに素なので(1)を満たすs,yは存在します。同様にt,uが得られます。x=a(qr)s+b(rp)t+c(pq)u・・・(2)とおけば、xは条件式を満たします。(2)をｐで割った余りは、a*1+0+0=aとなります。qで割れば余りb,rで割れば余りc,となります。ここからがわからない箇所です。このxをpqrで割った余りも条件式をみたします。 まず、自分の計算では、x=a(qr)s+b(rp)t+c(pq)u=pqr{as(1/p)+bt(1/q)+cu(1/r)}となり余りが出ません。そして条件式x≡a mod(p),x≡b mod(q),x≡c mod(r) を満たしているとも思えません。どなたか自分の考えの間違いを教えてください。お願いします。

  • フェルマーの最終定理(n=4)

    p,qは互いに素な自然数とする。以下の問いに答えよ。 (1)p,qがともに奇数であるとき、p^4+q^4は自然数の2乗にならないことをするせ。 これは、平方数を4で割った余りは、0または1で、条件よりp^2,q^2も奇数で p^4+q^4≡1+1=2(mod 4) mod 4で0または1でないので、平方数ではない。と書かれています。 (2)qは奇数とする。つぎの手順に従って、(2p)^4+q^4が自然数の2乗にならないことを背理法を用いてしるせ。 [1]次の仮定(H)が成り立つものとして、以下の問(A)～(D)に答えよ。 仮定(H):(2p)^4+q^4=r^2となる自然数rが存在する。 (A)2pとrは互いに素になることをしるせ。 　仮定(H)より2pが偶数で、qが奇数なので、rは奇数です。ここからがわからないところです。2pとrの最大公約数をdとおくと、ｄは奇数です。 　自分は、偶数を　2*奇数、2*偶数、奇数を2*奇数+1、2*偶数+1、として、最大公約数が奇数なら、偶数も奇数も奇数で割って、自然数になるのか確かめようとしましたが、失敗しました。 　どなたか偶数と奇数の最大公約数は奇数になることを証明してください。お願いします。　

  • フェルマーの定理の公式の解き方について

    秘密鍵と公開鍵について勉強していますが、フェルマーの定理が使われていると聞いたのですが、このフェルマーの定理というのは大学とかで習うものなのでしょうか？x ≡ 0 (mod p) でなければ x^(p-1) ≡ 1 (mod p) という式をみても計算方法がよくわからず困っています。よくわかる参考書等をご存知の方がいらっしゃればご教授お願いします。

  • フェルマーの小定理の証明過程について

    英語ですいません。 let p ≧ 1 be a prime and let a be a positive integer not divisible by p. (a) Given any integer b in the set {1 , ...... , p-1}, explain why you know there is some x ∈ {1, .... , p-1} such that ax ≡ b (mod p). (b) for a fixed b, is the x from question (a) unique? Prove that you are correct. (c) show that the set {a, 2a, ....(p-1)a} is a complete system that you are correct. (d) show that a^(p-1) * (p-1)! ≡ (p-1)! (mod p) (e) show that a^(p-1) ≡ 1 (mod p) フェルマーの小定理の証明過程なんですが、小問(a)から敷居が高くてよくわかりません。 出来れば(a)から(e)までステップバイステップで教えてください。

  • フェルマの小定理と位数に関する質問です

    問題） pを素数とします。また、aをpで割り切ることのできない整数とします。 この時、a^n≡1(mod p)となる最小の正整数nをmとすると p≡1(mod m)であることを証明したいです。 証明) まず、フェルマの小定理より、 n=p-1のとき、a^n≡1(mod p)が成り立つことが分かります。 よって、n=p-1がa^n≡1(mod p)となる最小の正整数nの場合、 m=p-1なので、明らかにp-1をmで割り切ることができるため、 p≡1(mod m)である。 (ここからが分かりません。。。) 次に、n=p-1がa^n≡1(mod p)となる最小の正整数nでない場合、 つまり、m<p-1となるmが存在する場合、 そのmによって、p≡1(mod m)が成り立つことを証明したいのですが、よく分かりません。 どなたか詳しい方、ご教授お願いします。 途中までの証明も不適切(不要)でしたら指摘してください。 よろしくお願いします。

  • RSA暗号の中国剰余定理についておしえてください.

    RSA暗号の中国剰余定理についておしえてください． N=77 = 7×11, p1=7, p2=11 d1 = d mod (p1-1) = 43 mod (7-1) = 1 d2 = d mod (p2-1) = 43 mod (11-1) = 3 m1 = c^d1 mod p1 = 48^1 mod 7 = 6 m2 = c^d2 mod p2 = 48^3 mod 11 = 4^3 mod 11 = 9 連立方程式 m = 6 mod 7 m = 9 mod 11 となり p1=7とp2=11は共に素数であるので互いに素 q1=p2^-1 mod p1 = 11^-1mod 7=4^-1mod 7=2 /// q2=p1-^1 mod p2 = 7^-1mod 11=8 //// これを用いて m=(m1×p2×q1 + m2×p1×q2) mod p1p2 = (6×11×2 + 9×7×8) mod 77 = (132+504) mod 77 = 20 平文 m = 20 とあるのですが，q1=p2^-1 mod p1 = 11^-1mod 7=4^-1mod 7=2と q2=p1^-1 mod p2 = 7^-1mod 11=8の部分でどうして2と8になるのかがわかりません．1時間くらい悩んでいるのですが見当がつきません．教えて下さい．＞＜

  • フェルマの小定理の証明方法について

    フェルマの小定理の証明は、ふつうは、二項定理と数学的帰納法、または、オイラーの定理を使うようです。以下の証明で、（式ａ）から（式ｂ）に移るのは妥当なのか、よくわかりません。 [蛇足] フェルマの小定理より、オイラーの定理の証明のほうが簡単なのは違和感を感じるのですが・・・。フェルマの小定理の簡明な証明方法があったら、それも教えてほしいです。 ●オイラーの定理 (a,m)=1のとき　　　 a^(φ(m))≡1 (mod m) 【フェルマの小定理】 a^(p-1)≡1 (mod p) 　ただし、aは正の整数（←条件を、少し制約しました。）、pは素数、ａとｐは互いに素（(a,p)=1） とする。 ■証明 数学的帰納法を用いる。 (1)a=1 のときは明らか。 (2)a=k のとき成り立つと仮定して、a=k+1のとき成り立つことを証明する。 言い換えると、mod p において、 k^p≡k ⇒　(k+1)^p≡k+1 を証明すればよい。 以下、合同式は mod p の場合のことを指す。 仮定より、 (k)^p≡k (k)^p-1≡k-1 F(k)=k^(p-1)+k^(p-1)…+1 とおくと、 (k-1)・F(k)≡k-1 よって、 F(k)≡1 ところで、F(k)はp個の元から構成されており、 p-1 Σ(k^m)≡1　　　　　　　　　　（式ａ） m=0 と書き直せる。ここで、kをk+1に置き換えるが、加法+と乗法・を交換則、結合則、分配則をみたす演算子*とすると、 p-1 Σ((k)^m*(1)^m)≡1　　　　　（式ｂ） m=0 と書ける。これより、 　p-1 k・Σ((k)^m*(1)^m)≡k 　m=0 　　　　　p-1 (k*1-1)・Σ((k)^m*(1)^m)≡k 　　　　　m=0 よって、 (k*1)^p-1≡k 書き直して、 (k+1)^p≡k+1 　　　　<証明終>

  • 因数定理。後少しなんですが…

    いつもお世話になっています。 あと１週間で実力テストとなり勉強に追われているものです…;; 因数定理を使う問題で、 整式P(x)を(x+1)(x-2)で割ったときの余りは5x+7である。このときP(x)をx+1で割ったときの余りを求めよ。という問題なんですが・・・ まず、因数定理でP(x)=(x+1)(x-2)Q(x)+5x+7 P(-1)=2 P(2)=17　が分かり 次に、余りをax+bとおいて、P(x)=(x+1)Q(x)+ax+bとし、 この式に-1を代入し-a+b=2 という所まではいけたのですが…もうひとつ式が出ない限りaとbの値は出せないので困っています;;

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する