13^(5^14)を19で割った余り

教科書にオイラーの定理を使用する例として
13^(5^14)を19で割った余りを求める問題が載っていて、

13^18≡1 mod 19である。
5^6≡1 mod 18である、よって5^14≡5^2≡7 mod 18。
13^2≡-2 mod 19である、よって13^7≡-104≡10 mod 19
よって余りは10

と解かれています。
13^18≡1 mod 19はオイラーの定理と分かるのですが、
5^6≡1 mod 18や13^2≡-2 mod 19はどこから分かるのでしょうか。

No.2 ベストアンサー 回答者： banakona 回答日時： 2009/06/17 15:24

＞5^6≡1 mod 18

これこそがオイラーの定理です。（13^18≡1 mod 19もオイラーの定理ですが、１９が素数なのでオイラー～の特殊形である「フェルマーの小定理」というべきものです。）１８と互いに素な１８より小さい自然数は１，５，７，１１，１３，１７なのでψ（１８）＝６。１８と５は互いに素ですからオイラーの定理により５＾６≡１　mod　１８。

あとは13^2≡-2 mod 19　なのですが、これは計算の便宜上、取り扱いやすい絶対値の小さな数－２が運よく出てきたということではないかと思います（できれば１か－１が出てきて欲しかったのですが、１３のべき乗には中々都合のいい数がでてきません。１３^9≡－１となるようですが７を通り過ぎてますｗ。）

この回答へのお礼

確かにψ(18)=18(1 - 1/2)(1 - 1/3)=6です。
気が付きませんでした(汗)。

ありがとうございました。

お礼日時：2009/06/17 16:42

No.1 回答者： Tacosan 回答日時： 2009/06/17 14:15

計算すればわかる.