フェルマーの小定理は、素数の性質に関する定理で、冪乗(巾乗、べき乗)の剰余の定理です。
かの有名なフェルマーの最終定理*1
フェルマーの小定理
素数、任意の整数
に対して
\begin{equation}
a^p \equiv a \mod p
\end{equation}が成り立つ。
特に、が互いに素である場合は、
\begin{equation}
a^{p -1} \equiv 1 \mod p
\end{equation}が成り立つ。
本稿では、フェルマーの小定理の簡便な証明について述べていきます。
なお、式が長くなる場合はを省略します。
まず、
\begin{equation}
(x + y)^p \equiv x^n + y^n \mod p \tag{1}
\end{equation}を証明します。
式を展開すると、二項定理により、
を除く全ての項は
を因数に持ちます。
二項定理 - 数式で独楽する
したがって、
\begin{equation}
(x + y)^p \equiv x^n + y^n \mod p \tag{1}
\end{equation}が成り立ちます。
次に、
\begin{equation}
a^p \equiv a \mod p \tag{2}
\end{equation}を、数学的帰納法を用いて証明します。
の場合、
なので、式(2)は明らかに成り立ちます。
の場合、
式(1)により、
\begin{eqnarray}
2^p &=& (1+1)^p \\
& \equiv & 1^p + 1^p \\
&=& 1+1 \\
&=& 2
\end{eqnarray}なので、式(2)は成り立ちます。
の場合に式(2)が成り立つと仮定します。
\begin{equation}
k^p \equiv k \mod p \tag{2'}
\end{equation}です。
式(1), (2')により、
\begin{eqnarray}
(k +1)^p & \equiv & k^p + 1^p & \quad (\because \mbox{equation} (1)) \\
& \equiv & k + 1 & \quad (\because \mbox{equation} (2'))
\end{eqnarray}となります。
つまり、の場合も式(2)が成り立ちます。
したがって、数学的帰納法により、
\begin{equation}
a^p \equiv a \mod p \tag{2}
\end{equation}が成り立ちます。
特にが互いに素の場合は両辺を
で割ることができ、
\begin{equation}
a^{p -1} \equiv 1 \mod p \tag{3}
\end{equation}が成り立ちます。
ちなみに、式(2)は次のようにも書けます。
\begin{eqnarray}
a^p &=& (\underbrace{1+1+\cdots +1}_{a個})^p \\
& \equiv & \underbrace{1^p + 1^p + \cdots + 1^p}_{a個} \mod p \\
&=& \underbrace{1+1+\cdots +1}_{a個} \\
&=& a
\end{eqnarray}
