フェルマの小定理の証明方法について

質問

フェルマの小定理の証明は、ふつうは、二項定理と数学的帰納法、または、オイラーの定理を使うようです。以下の証明で、（式ａ）から（式ｂ）に移るのは妥当なのか、よくわかりません。

[蛇足]
フェルマの小定理より、オイラーの定理の証明のほうが簡単なのは違和感を感じるのですが・・・。フェルマの小定理の簡明な証明方法があったら、それも教えてほしいです。

●オイラーの定理
(a,m)=1のとき　　　 a^(φ(m))≡1 (mod m)

【フェルマの小定理】

a^(p-1)≡1 (mod p)
　ただし、aは正の整数（←条件を、少し制約しました。）、pは素数、ａとｐは互いに素（(a,p)=1） とする。

■証明

数学的帰納法を用いる。
(1)a=1 のときは明らか。
(2)a=k のとき成り立つと仮定して、a=k+1のとき成り立つことを証明する。
言い換えると、mod p において、
k^p≡k ⇒　(k+1)^p≡k+1
を証明すればよい。

以下、合同式は mod p の場合のことを指す。

仮定より、
(k)^p≡k
(k)^p-1≡k-1

F(k)=k^(p-1)+k^(p-1)…+1
とおくと、
(k-1)・F(k)≡k-1
よって、
F(k)≡1

ところで、F(k)はp個の元から構成されており、
p-1
Σ(k^m)≡1　　　　　　　　　　（式ａ）
m=0
と書き直せる。ここで、kをk+1に置き換えるが、加法+と乗法・を交換則、結合則、分配則をみたす演算子*とすると、
p-1
Σ((k)^m*(1)^m)≡1　　　　　（式ｂ）
m=0
と書ける。これより、
　p-1
k・Σ((k)^m*(1)^m)≡k
　m=0
　　　　　p-1
(k*1-1)・Σ((k)^m*(1)^m)≡k
　　　　　m=0
よって、
(k*1)^p-1≡k
書き直して、
(k+1)^p≡k+1

　　　　<証明終>

回答No.1

sunflower-san · ベストアンサー

一通り読んでみましたが、

>ここで、kをk+1に置き換えるが、加法+と乗法・を交換則、結合則、分配則をみたす演算子*とすると、

↑の箇所、この演算子の定義がよくわからなかったため、その続きの部分も分かりませんでした。

それと、

>F(k)=k^(p-1)+k^(p-1)…+1
とおくと、

↑の箇所、F(k)=k^(p-1)+k^(p-2)+…+1の間違いですね？

また、

>(k-1)・F(k)≡k-1
よって、
F(k)≡1

↑の議論はk≠1 mod pのときしか成り立ちません。k≡1 mod pなら定義から明らかにF(k)≡0 mod pですよね？

以上、この証明はイマイチよくわからなかったので、以下に別の簡単な証明を紹介します↓

pを素数とし、
いまaをpと互いに素な整数とします。

このとき、p-1個の整数
a, 2a, 3a, ..., (p-1)a
は mod pでいずれも0でなく(←pの倍数になるものがないから)、
どの２つも mod pで等しくない(←どの２つの差もpの倍数にならないから)

よってmod pで、
1, 2, 3, ..., p-1
を並べ替えたものに他ならない。

従って、全て掛けた積は等しい：
a×2a×3a×・・×(p-1)a ≡1×2×3×・・×(p-1) mod p

両辺を整理すると、
a^(p-1)×(p-1)! ≡(p-1)! mod p
移項すると、
(a^(p-1)-1)×(p-1)! ≡0 mod p

ここで、(p-1)! はpで割り切れないので、(a^(p-1)-1)がpで割り切れることになる。
つまり、a^(p-1)-1≡0 mod p

フェルマーの定理の証明終わり。

お礼

ウィキペディアに記載されている証明を短くする方法を考えていたのですが、読み返すと記載ミスがちょこちょこありました（汗）
すみませんでした。

簡単な証明の紹介ありがとうございます！
目からウロコが落ちました。オイラーの定理の証明方法を応用すれば良かったんですね！

思いつかなかった・・・
素晴らしいです！！