フェルマーの小定理

　フェルマーの小定理とは、素数$p$と$p$と互いに素な整数$a$について

$$\begin{equation}\large a^{p-1}\equiv1\pmod p\end{equation}$$

が成り立つという定理のことです。

これが成り立つことを確かめてみます。

　まず、「倍数を互いに素な整数で割ったときの余りの性質」より、

素数$p$と互いに素な整数$a$について
$a,2a,\cdots,(p-1)a,pa$をそれぞれ$p$で割ったときの余りを一列に並べたものは$0,1,\cdots,p-2,p-1$の並べ替えである

といえます。

ここで、必ず$pa$を$p$で割ったときの余りが$0$であることに着目すれば、

$a,2a,\cdots,(p-2)a,(p-1)a$をそれぞれ$p$で割ったときの余りを一列に並べたものは$,1,\cdots,p-2,p-1$の並べ替えである

ということができます。
このことから、$a,2a,\cdots,(p-2)a,(p-1)a$をすべて掛け合わせると、合同式で

$$\begin{align*}a\cdot2a\cdot\ldots\cdot(p-2)a\cdots(p-1)a&\equiv1\cdot2\cdot\ldots(p-2)(p-1)\pmod p\\[0.5em]\Rightarrow(p-1)!a^{p-1}&\equiv(p-1)!\pmod p\end{align*}$$

と書くことができます。

ウィルソンの定理より$(p-1)!\equiv-1\pmod p$なので

$$-a^{p-1}\equiv-1\pmod p$$

となり、両辺に$-1$を掛ければ

$$a^{p-1}\equiv1\pmod p$$

となります。

したがって、フェルマーの小定理が成り立つことがわかります。

　また、両辺に$a$を掛ければ

$$\begin{equation}a^p\equiv a\pmod p\end{equation}$$

となります。
ただし、$(2)$の場合$a$は$p$と互いに素である必要はなく任意の整数となります。

整数$a$が$p$と互いに素でないとき、$a$は$p$の倍数となるので$a=kp$（$k:$整数）とおくことができます。

関連：互いに素でない2数に関する命題の真偽は？

すると、

$$\begin{align*}a^p&=(kp)^p\\[0.5em]&=k^pp^p\\[0.5em]&=k^pp^{p-1}\cdot p\equiv0\pmod p\\[1em]a&=kp\equiv0\pmod p\end{align*}$$

となり、$a$が$p$と互いに素でないときも$(2)$が成り立つことがわかります。
$(2)$が成り立つ$a$の条件、$p$と互いに素または互いに素でないは、$a$は任意の整数であるということなので、$(2)$は任意の整数$a$で成り立ちます。

関連：倍数を互いに素な整数で割ったときの余りの性質

関連：ウィルソンの定理とその逆