合同法について

質問

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

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

回答No.3

yoikagari · ベストアンサー

http://aozoragakuen.sakura.ne.jp/suuron/node32.html
の定理 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

あ～, 「フェルマーの定理」って書いたけどあんまり意味ないなぁ....
最短は「オイラーの定理から」で終わり.

回答No.1

Tacosan

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

補足

はい！お願いします。