合同法について

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

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

No.3 ベストアンサー 回答者： yoikagari 回答日時： 2010/11/28 05:06

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である。

No.2 回答者： Tacosan 回答日時： 2010/11/28 02:13

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

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

No.1 回答者： Tacosan 回答日時： 2010/11/27 23:29

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

この回答への補足

はい！お願いします。

補足日時：2010/11/27 23:32