Fermatの小定理を使ったのですが・・・

質問

(1)『2^r≡1 (mod13)となる最小の正整数rを求めよ。』
という問題で、Fermatの小定理を使って
r=13-1=12
と回答しました。

同じような問題で、
(2)『5^s≡1 (mod11)となる最小の正整数ｓを求めなさい。』
では、(1)の解き方では解答が合いませんでした。
(1)と(2)では何が違うのですか？

詳しい解説お願いします！

回答No.2

zk43 · ベストアンサー

2^r≡1（mod 13）となる最小のrを求めるということは、2のmod 13での
位数を求めるということです。
つまり、mod 13での乗法群{1,2,3,4,5,6,7,8,9,10,11,12}における2の
位数を求めるということです。
確かにどの元も、群の位数の12乗すれば、必ず単位元である1になります。
しかし、それが必ずしも最小のものではありません。
元の位数は、群の位数の約数から探すことになります。
ですから、2を12の約数である1,2,3,4,6乗して、1にならなければ、
2の位数は12ということになります。

5^s≡1（mod 11）となる最小のsを求めるには、10の約数の中から探す
ことになります。
その候補は1,2,5,10です。
まず、当然、1,2はだめです。
5乗について考えてみると、
5^2≡25≡3（mod 11）
両辺を2乗すると、
5^4≡9（mod 11）
両辺に5を掛けると、
5^5≡45≡1（mod 11）
よって、5^s≡1（mod 11）となる最小のsは5です。
または、mod 11での乗法群{1,2,3,4,5,6,7,8,9,10}における5の位数は
5である、ともいえます。

一般的な話としては、有限群のどの元も、群の位数乗すれば、必ず、
単位元になります。しかし、それが最小のものであるとは限らず、
最小のものは、群の位数の約数の中から探すことになります。

お礼

ありがとうございます！
大変参考になりました。

回答No.1

Tacosan

確かに Fermat の定理から
素数 p 及び p と互いに素な a に対し a^(p-1) ≡ 1 (mod p)
ですが, これは「a^r ≡ 1 (mod p) となる＊最小の＊ r = p-1」と言っているわけではありません. p-1 より小さい正整数 r に対して a^r ≡ 1 となることはありえます... まあ, p-1乗して 1 になるわけだからそのようなr は p-1 の約数に限られるんですが.
というか, そもそもからして
「1^r ≡ 1 (mod 13) となる最小の正整数 r を求めよ」
という問題に対しても r = 13-1 = 12 と答えますか?