フェルマーの小定理

今回は,以下のフェルマーの小定理を学びます.

$pを素数とし,a\in \mathbb{Z}でaとp$が互いに素のとき,

$$a^{p-1}\equiv 1(mod\  p)$$

が成り立ちます.

$(証明)1, 2, \cdots, p-1を一斉にa倍し,それらをpで割った余りを考える.$

$ここで,a\cdot 1,\ a\cdot 2,\ \cdots , \ a\cdot(p-1)をpで割った余りは全て異なる$

$すると,全体の個数がp-1で余りは0にはならないから$

$それらは1,2,\cdots,p-1を並べかえたものに等しい.$

したがってそれらの積について,

$$a\cdot1\cdot a\cdot2\cdots a\cdot(p-1)\equiv1\cdot2\cdots(p-1)\    (mod\  p)$$

すなわち$$a^{p-1}(p-1)!\equiv(p-1)!\   (mod\  p)$$

よって両辺の差をとって整理すると,

$$(a^{p-1}-1)(p-1)!\equiv0\   (mod \  p)$$

すなわち,

$$p|(a^{p-1}-1)(p-1)!$$

$ここで,(p-1)!はpで割り切れないので,p|a^{p-1}-1$

$$\therefore\  a^{p-1}\equiv1\  (mod\  p)$$