質問: 合同法について a, bを自然数とする。(a,b)=1 (aとbの最大公約数が1) のとき、a^n=1 mod b をみたす 自然数nが存在することを示せ。 わかりません。。教えてください!
回答: 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である。