フェルマの小定理と位数に関する質問
- フェルマの小定理によれば、整数pを素数、aをpで割り切ることのできない整数とすると、a^n≡1(mod p)となる最小の正整数nをmとすると、p≡1(mod m)が成り立つ。
- 証明において、n=p-1の場合はフェルマの小定理から明らかに成り立つことが分かる。また、n=p-1でない場合の証明についてはまだ途中で詳細が分かっていない。
- 質問者は、n=p-1でない場合の証明について助言を求めている。
- ベストアンサー
フェルマの小定理と位数に関する質問です
問題） 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)が成り立つことを証明したいのですが、よく分かりません。 どなたか詳しい方、ご教授お願いします。 途中までの証明も不適切(不要)でしたら指摘してください。 よろしくお願いします。
- jysuper
- お礼率57% (27/47)
- 数学・算数
- 回答数2
- ありがとう数1
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
正直にp-1がmで割り切れないとして矛盾を示せばよいです。 このとき p-1 = mq + r, 1≦r<mなるrがあって、 1≡a^(p-1) = a^(mq+r) = (a^m)^q * a^r = a^r(mod p)であって、 mが「a^n≡1(mod p)となる最小の正整数」というのに矛盾します。 あるいは体Z/pZの乗法群Gは位数p-1の群で、<a>は Gの部分群であるから、aの位数はGの位数p-1の約数です。
その他の回答 (1)
- koko_u_u
- ベストアンサー率18% (216/1139)
タイトルにある「位数に関する質問」とはどこからきたのですか？
補足
pを素数とします。また、aをpで割り切ることのできない整数とします。 この時、a^n≡1(mod p)となる最小の正整数nをmとするとこのmをmod pにおけるaの位数というと理解しています。 で、 ord_p(a)=m と書くと。 で、その位数mにおいて、 p≡1(mod m)であることを 証明する問題なので、そう記載した次第です。 参考：http://akademeia.info/index.php?%B8%B5%A4%CE%B0%CC%BF%F4
関連するQ&A
- フェルマの小定理について
次の主張（フェルマの小定理）の証明を与えよ。 「ｐが素数のとき、aがpと互いに素な整数ならば、a^(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 <証明終>
- ベストアンサー
- 数学・算数
- フェルマー小定理の特殊形？
高校受験の娘から整数問題の質問をされ、答えたついでに類題を 出してやろうとあれこれ考えていたところ、以下のような規則を みつけました。 ｎ＾(4m+1)≡n (mod 10) : n,mは 整数 恥ずかしながら自分で証明できなかったので、娘に出題することは やめましたが、それ以前この式は本当に正しいのだろうかという疑問が あります。 フェルマー小定理の特殊形のような、そうでないような・・・。 ●すでに知られた一般的な規則で、正しいものでしょうか？ ●証明はかなり難しいものでしょうか？ （中学レベル、高校レベル、それ以上、程度で結構です） 注）私自身は数学に興味はもっていますがほとんど素人の人間です。 あまり難しい説明は理解の範囲を超えると思いますが、この規則の 原型となる公式や、成立する範囲、条件などについてお教えいただ ければ幸いです。 （もし証明可能であればヒントをいただければ一度チャレンジして みようかなとも考えております） よろしくお願いします。
- ベストアンサー
- 数学・算数
- オイラーの定理(整数)
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 )となることがしるされました。としめくくっています。
- ベストアンサー
- 数学・算数
- フェルマーの最終定理について
フェルマーの最終定理について質問をします． フェルマーは、この定理を発見したときに、ｎ＝４の場合だけは証明したと本に書かれてあったのですが、その証明がよく分からないのです。というか、どのような証明をしたのかが分かりません。 この証明の仕方を、詳しく知っている方がいましたら、教えてください。 よろしくお願い致します。
- 締切済み
- 数学・算数
- フェルマーの定理の公式の解き方について
秘密鍵と公開鍵について勉強していますが、フェルマーの定理が使われていると聞いたのですが、このフェルマーの定理というのは大学とかで習うものなのでしょうか？x ≡ 0 (mod p) でなければ x^(p-1) ≡ 1 (mod p) という式をみても計算方法がよくわからず困っています。よくわかる参考書等をご存知の方がいらっしゃればご教授お願いします。
- 締切済み
- ネットワーク
- フェルマーのやらなかったこと
おなじみのフェルマの定理： n を正の整数とすれば、 2<n のとき x^n + y^n ＝ z^n をみたす整数の組（x,y,z）は存在しない。 ですけども、 ここで、n を整数全体にに拡張して、 n=1 のときは、いくらでも整数解があります。 n=0 のときは、無意味です。（整数解は無い） n=-1 のときは、たとえば、（x,y,z）=（4,4,2）はひとつの解ですよね。 さて、n=-2,-3,-4,-5,・・・ などのときを調査するのは、数学的に意味のある営みでしょうか？ 忌憚なきご意見・見通しをお願いいたします。 必要ならば、高額のため、「ガウス整数」なども俎上にあげていただくことも期待しています「。
- ベストアンサー
- 数学・算数
- フェルマーの最終定理
フェルマーの最終定理ってありますよね?Ｘのｎ乗＋Ｙのｎ乗＝Ｚのｎ乗 これに３以上の整数解は(ｎの)ないってやつですよね? これの証明ってどんなのですか?
- ベストアンサー
- 数学・算数
- フェルマーの定理を使った問題
こんにちは。 最近フェルマーの定理を習って家で復習しているのですが、 使い方がいまいち分かりません。 例えば以下の２題はどのようにこの定理を利用すればよいのでしょうか？ 最近数学に興味が湧いたのですが、 まだまだまともについていくことができません。。。 早く劣等生を卒業したいものです。 (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で割り切れることを証明しなさい。 数学と聞くと拒否反応を起こしてしまうレベルです。 数学好きのみなさんには何だと思う問題かもしれませんが、よろしくご教授お願いいたします。
- ベストアンサー
- 数学・算数
お礼
ありがとうございます。 前半の部分で理解しました。