フェルマーの小定理

2017年07月03日(月)  List  Edit  New

命題
整数$n$が素数$p$と互いに素であるならば、
$$n^{p-1}\equiv1\pmod p$$
が成り立つ。
証明
$p$が素数のとき、集合$X = \{ 1,2,3,\ldots,p-1 \}$とおく。また$X_n = \{xn \bmod p \,|\,x \in S \}$としたとき、$X_n = X$が成り立つ(※1)。よって、$X$の要素をすべて乗じた結果と、$X_n$の要素をすべて乗じた結果は等しい。
$$
1\cdot2\cdots(p-1) = (1n \bmod p)\cdot(2n\bmod p)\cdots((p-1)n \bmod p)
$$
これから、
$$
1\cdot2\cdots(p-1) \equiv 1n\cdot2n\cdots(p-1)n \pmod p
$$
が成り立つ。式を整理して、
$$
(p-1)!\,n^{p-1} \equiv (p-1)! \pmod p
$$
$(p-1)!$は$p$と互いに素なので、
$$n^{p-1} \equiv 1 \pmod p$$
が示された。(証明終わり)

※1の証明
https://story.hyuki.net/20170703002408/