合同法について

解決済

質問者：smileshower
質問日時：2010/11/27 23:09
回答数：3件

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

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

通報する

この質問への回答は締め切られました。

質問の本文を隠す

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

「n数」に関するQ&A： √n²+21が整数となるような自然数nをすべて答えなさい。答え分かるかた解説つきでお願いしますm(

さらに表示

「証明互いに素」に関するQ&A：多項式が互いに素であると証明したいのですが…

回答 (3件)

ベストアンサー優先
最新から表示
回答順に表示

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