定理
定理1. Fermatの小定理
\[ \forall p\in\mathbb{P}\ \ \forall a\in\mathbb{Z}^+ \quad a^p\equiv a\pmod{p} \]証明
補題1.
\[ \forall p\in\mathbb{P}\ \ \forall m\in\mathbb{Z}^+ \quad(m+1)^p\equiv m^p+1\pmod{p} \]定理1の証明
\(a\) に関する数学的帰納法によって示す.
-
\(a=0\) のとき明らかに成立する.
-
\(a=k\in\mathbb{Z}^+\) のとき成立すると仮定する.
補題1より
\[ (k+1)^p\equiv k^p+1\equiv k+1\pmod{p} \]よって \(a=k+1\) のときも成立する.
以上より定理1は示された.
補題1の証明
任意の \(p\in\mathbb{P}\) および \(k\in[1, p-1]\subset\mathbb{N}\) について
\[ p>k\ \wedge\ p>p-k \]より, 二項係数
\[ \binom{p}{k}=\frac{p!}{k!(p-k)!} \]は \(p\) の倍数である.
よって
\begin{align} \quad(m+1)^p&=\sum_{k=0}^p\binom{p}{k}m^k\\ &=m^p+1+\sum_{k=1}^{p-1}\binom{p}{k}m^k\\[5pt] &\equiv m^p+1\pmod{p} \end{align}以上より補題1は示された.