【最大10000ポイント】当たる!!質問投稿キャンペーン!

a, bを自然数とする。(a,b)=1 (aとbの最大公約数が1) のとき、a^n=1 mod b をみたす
自然数nが存在することを示せ。

わかりません。。教えてください!

このQ&Aに関連する最新のQ&A

A 回答 (3件)

http://aozoragakuen.sakura.ne.jp/suuron/node32.h …
の定理 23(オイラーの定理)を使ってよいなら
オイラーの定理より、a^{φ(b)}≡1 (mod b)がいえる。
φ(b)が求める整数nである。

・・・・・・・・・・・・・・・証明終わり・・・・・・・・・・・・

余りにもあっけないのでオイラーの定理を使わない場合も

b+1個の整数1(=a^0),a,a^2,…,a^bを考える。
bで割ったときの余りは0,1,…b-1だからb通りの値が考えられる。
したがってb+1個の数1(=a^0),a,a^2,…,a^bの中にはbで割ったときの余りが等しくなる2数が必ず存在する。
それをa^i,a^jとする(ただし、i,jは0≦i<j≦bをみたす整数)
このとき、a^j-a^i=a^i{a^(j-i)-1}はbで割り切れる。
a,bは互いに素だからa^iとbも互いに素である。
したがってa^(j-i)-1がbで割り切れることがわかる
よって、a^(j-i)≡1 (mod b)がいえる。j-iが求める整数nである。
    • good
    • 0

あ~, 「フェルマーの定理」って書いたけどあんまり意味ないなぁ....


最短は「オイラーの定理から」で終わり.
    • good
    • 0

フェルマーの定理は使っていい?

この回答への補足

はい!お願いします。

補足日時:2010/11/27 23:32
    • good
    • 0

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!


人気Q&Aランキング