- ベストアンサー
フェルマーの小定理
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 が互いに素でなければ成り立たないはずなのにそこに言及していないのが気になります．なぜ成り立つのでしょうか？
- みんなの回答 （3）
- 専門家の回答
質問者が選んだベストアンサー
その他の回答 (2)
- R_Earl
- ベストアンサー率55% (473/849)
ANo.1ですが、訂正です。 質問の意図を勘違いしていました。 mはpの整数倍で、mとqは互いに素の時(m = spと置きます。sはq未満の整数です)、 m^(n') = 1 (mod q)だけが成り立ちます。 つまりm^(n') = tq + 1となります（tは整数）。 ここで、 m^(ed) = m^(1 + fn') = m・{ m^(n') }^f を考えます。 m・{ m^(n') }^fの左側の『m』にm = sp、右側の『m^(n')』にm^(n') = tq + 1を代入します。 すると m^(ed) = m・{ m^(n') }^f = sp・{tq + 1}^f {tq + 1}^fを二項定理で展開することを考えて下さい。 そうすれば、『m^(ed) = sp・{tq + 1}^fをn = pqで割ると、sp余る』 ということが分かります。 つまりm^(ed) = sp (mod n)です。 最初にm = spと置いたので、結局m^(ed) = m (mod n)となり、 『平文mを、nを法とする合同式でe乗してd乗すると、元の平文mに戻る』 となります。 mがqの整数倍で、mとpが互いに素の場合も同様になります。 mがpとq両方の整数倍の時は、 nを法とする合同式では、mもm^(ed)も0になるので、 m^(ed) = m (mod n)が成り立つのは自明となります(左辺も右辺も0なので)。
補足
返信ありがとうございます >mがpとq両方の整数倍の時は、 >nを法とする合同式では、mもm^(ed)も0になるので、 >m^(ed) = m (mod n)が成り立つのは自明となります(左辺も右辺も0なので)。 この部分ですが，なぜmもm^(ed)も0になるのでしょうか？ あと，mがpとq両方に対して互いに素の場合はどう考えればよいのでしょうか？
- R_Earl
- ベストアンサー率55% (473/849)
関連するQ&A
- フェルマの小定理について
次の主張（フェルマの小定理）の証明を与えよ。 「ｐが素数のとき、aがpと互いに素な整数ならば、a^(p-1) ≡ 1 (mod p) が成立する。」 フェルマの小定理についてあまり詳しくないので分かりやすく教えていただけると嬉しいです。 宜しくお願い致します。
- 締切済み
- 数学・算数
- フェルマの小定理と位数に関する質問です
問題） 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)が成り立つことを証明したいのですが、よく分かりません。 どなたか詳しい方、ご教授お願いします。 途中までの証明も不適切(不要)でしたら指摘してください。 よろしくお願いします。
- ベストアンサー
- 数学・算数
- フェルマーの定理の公式の解き方について
秘密鍵と公開鍵について勉強していますが、フェルマーの定理が使われていると聞いたのですが、このフェルマーの定理というのは大学とかで習うものなのでしょうか？x ≡ 0 (mod p) でなければ x^(p-1) ≡ 1 (mod p) という式をみても計算方法がよくわからず困っています。よくわかる参考書等をご存知の方がいらっしゃればご教授お願いします。
- 締切済み
- ネットワーク
- フェルマの小定理の証明方法について
フェルマの小定理の証明は、ふつうは、二項定理と数学的帰納法、または、オイラーの定理を使うようです。以下の証明で、（式ａ）から（式ｂ）に移るのは妥当なのか、よくわかりません。 [蛇足] フェルマの小定理より、オイラーの定理の証明のほうが簡単なのは違和感を感じるのですが・・・。フェルマの小定理の簡明な証明方法があったら、それも教えてほしいです。 ●オイラーの定理 (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 <証明終>
- ベストアンサー
- 数学・算数
- 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時間くらい悩んでいるのですが見当がつきません．教えて下さい．＞＜
- 締切済み
- その他([技術者向] コンピューター)
- オイラーの定理(整数)
nは自然数、aは整数とする。aとnが互いに素な時、a^{φ(n)}≡1( mod n)が成り立つ。 ここでφ(n)は「n以下の自然数でnと互いに素なものの個数を表す」"オイラーの関数"である。 この定理の例証で、例えばn=45=3^(2)*5のときa=7として考えます。 φ(45)=φ(3^2)*φ(5)となり、φ(3^2)=6、φ(5)=4です。 フェルマーの小定理よりmod 5 で、7^φ(45)={7^φ(5)}^φ(3^2)は {7^φ(5)}≡1 (mod 5)より、7^φ(45)≡1 (mod 5 )・・・(1)になり。 次に7^φ(3^2)≡1(mod 3^2)をしるします。フェルマーの小定理より mod 3 で 7^(3-1)≡1なので7^(3-1)＝3k+1、 7^φ(3^2)={7^(3-1)}^3＝(3k+1)^3=(3k)^3+3C1(3k)^2+3C2(3k)+1 3C1、3C2は３の倍数なので、7^φ(3^2)≡1(mod 3^2)・・・(2)です。 よって、7^φ(45)={7^φ(3^2)}^φ(5)≡1(mod 3^2)となります。 ここからが分からない箇所なのですが、中国の剰余定理から、 (1)かつ(2)⇔7^φ(45)≡■(mod 3^(2)*5)となる■が、1つだけ存在します。と書いてありますが、自分は中国の剰余定理は、m、nを互いに素な自然数とする。 x≡a(mod m)かつ x≡b(mod n)を満たす整数xはmnを法として、ただ1つ存在する。と書いてあることから、割る数が違えば、a,bのように余りもちがう場合に、整数xはmnを法として、ただ1つ存在する。と思っていたのですが、 この例証では、■≡7^φ(45) (mod 5)かつ■≡7^φ(45) (mod 3^2)のような余りが 一緒の場合を同時に満たす■を求めているような気がして、中国の剰余定理があてはまるか不安です。 自分の考えの間違いや、余りが一緒の場合でも中国の剰余定理が使えるかを教えてください。お願いします。 本では、■＝1のとき(1)、(2)が成り立つので、■＝1だとわかります。 よって7^φ(45)≡1(mod 45 )となることがしるされました。としめくくっています。
- ベストアンサー
- 数学・算数
- フェルマー小定理の特殊形？
高校受験の娘から整数問題の質問をされ、答えたついでに類題を 出してやろうとあれこれ考えていたところ、以下のような規則を みつけました。 ｎ＾(4m+1)≡n (mod 10) : n,mは 整数 恥ずかしながら自分で証明できなかったので、娘に出題することは やめましたが、それ以前この式は本当に正しいのだろうかという疑問が あります。 フェルマー小定理の特殊形のような、そうでないような・・・。 ●すでに知られた一般的な規則で、正しいものでしょうか？ ●証明はかなり難しいものでしょうか？ （中学レベル、高校レベル、それ以上、程度で結構です） 注）私自身は数学に興味はもっていますがほとんど素人の人間です。 あまり難しい説明は理解の範囲を超えると思いますが、この規則の 原型となる公式や、成立する範囲、条件などについてお教えいただ ければ幸いです。 （もし証明可能であればヒントをいただければ一度チャレンジして みようかなとも考えております） よろしくお願いします。
- ベストアンサー
- 数学・算数
- フェルマーの定理を使った問題
こんにちは。 最近フェルマーの定理を習って家で復習しているのですが、 使い方がいまいち分かりません。 例えば以下の２題はどのようにこの定理を利用すればよいのでしょうか？ 最近数学に興味が湧いたのですが、 まだまだまともについていくことができません。。。 早く劣等生を卒業したいものです。 (1)p,q,rを異なる整数とし、(a,pqr）=1とすると、 a^(p-1)(q-1)(r-1)はpqrで割り切れることを証明しなさい。 (2)561=3*11*7に対し、(a,561)=1とすると、（a^560）-1は561で割り切れることを証明しなさい。 数学と聞くと拒否反応を起こしてしまうレベルです。 数学好きのみなさんには何だと思う問題かもしれませんが、よろしくご教授お願いいたします。
- ベストアンサー
- 数学・算数
- p,qが素数のときn^{(p-1)(q-1)+1}≡n (mod pq
p,qが素数のときn^{(p-1)(q-1)+1}≡n (mod pq)になりますか? nがpともqとも互いに素であるときは、 Fermatの小定理を使えばn^{(p-1)(q-1)}≡1 (mod pq) が言えるので、標記の命題は言えると思うのですが pまたはqのいずれか一方がnと互いに素でないとき n^{(p-1)(q-1)}≡1 (mod pq)は言えないものの n^{(p-1)(q-1)+1}≡n (mod pq)は言えてしまっているように思えます (私がやったケースはp=3,q=11の場合です)。 これは正しいのでしょうか? 正しいとしたら何故ですか?
- ベストアンサー
- 数学・算数
- 中国の剰余定理と原始根
アドバイスよろしくおねがいします。 p,ｑを素数としたときに mod p と mod q において 原始根になる値gが存在する。それは中国剰余定理からいえる。 という記述があったのですが、原始根と中国剰余定理が結びつきません。 mod p,mod q において原始根ということは gを法pにおいてp-１乗してはじめて１になり、かつ法qにおいてもq-1乗してはじめて１になるわけだと思います。（ほかにも条件がありますが…） で、中国剰余定理は 簡単に言うと 複数の法が違い、法の数が互いに素な連立合同式に対して、解が一意に定まるということだと思います。 この二つが結びつきません。 ご教授お願いします
- ベストアンサー
- 数学・算数
お礼
なるほど！ わかりやすい解説ありがとうございました．