フェルマーの小定理とは、素数$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$の並べ替えである
といえます。
$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$をすべて掛け合わせると、合同式で
$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$を掛ければ
ただし、$(2)$の場合$a$は$p$と互いに素である必要はなく任意の整数となります。
\begin{equation}a^p\equiv a\pmod p\end{equation}
となります。
ただし、$(2)$の場合$a$は$p$と互いに素である必要はなく任意の整数となります。
整数$a$が$p$と互いに素でないとき、$a$は$p$の倍数となるので$a=kp$（$k:$整数）とおくことができます。
すると、
$(2)$が成り立つ$a$の条件、$p$と互いに素または互いに素でないは、$a$は任意の整数であるということなので、$(2)$は任意の整数$a$で成り立ちます。
\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$で成り立ちます。
Share:
