はじめに
本記事では, 競プロや数論において題材となる「フェルマーの小定理」についてまとめたいと思います.
フェルマーの小定理とは
整数 ${\it a}$ と素数 ${\it p}$ に対して, 以下の合同式が成り立つことをフェルマーの小定理という.
a^{p-1} \equiv 1 ~ (\mathrm{mod ~p})
この式の意味は 「$a^{p-1}$ を ${\it p}$で割った余りは, 1 を ${\it p}$ で割った余りに等しい」である.
このフェルマーの小定理を用いることで, とても大きな数を素数で割ったときの余りをすぐに求めることができる.
フェルマーの小定理の証明
まず準備として, 二項定理を考える. 二項定理から以下の式が成り立つことがわかる.
(x+y)^p = \sum_{k=0}^{p} \binom{p}{k} x^{p-k} y^k
上記において, 二項係数は以下のように書き下すことができる.
\binom{p}{k} = \frac{p(p-1)(p-2)\cdots(p-k+1)}{k!}
ここで ${\it p}$ が素数のとき, $1 \leq k \leq p-1$ とすると, ${\it k}!$ と ${\it p}$ に共通の約数は存在しないので, 二項係数の分母は ${\it p}$ で割り切れず, 分子は ${\it p}$ で割り切れることがわかる. よって, 二項係数全体は ${\it p}$ で割り切れる.
ここからは ${\it n}$ についての数学的帰納法を用いて, $a^{p-1} \equiv 1 ~ (\mathrm{mod ~p})$ が成り立つことを示す.
( i ) ${\it a}$ = 2 のとき
二項定理から,
\begin{align}
(1+1)^p
&= \sum_{k=0}^{p} \binom{p}{k} 1^{p-k} 1^k \\
&= \sum_{k=0}^{p} \binom{p}{k} \\
&= 1 + \binom{p}{1} + \binom{p}{2} + \cdots + \binom{p}{p-1} + 1 \\
&\equiv 1 + 1 ~ (\mathrm{mod ~p}) \\
&= 2 ~ (\mathrm{mod ~p})
\end{align}
( iI ) ${\it a}$ = ${\it n}$ のとき
${\it a}$ = ${\it n} - 1$ のときは仮定が成り立つものとする. 二項定理より,
\begin{align}
a^p
&= (a - 1 + 1)^{p} \\
&= \sum_{k=0}^{p} \binom{p}{k} (a-1)^{p-k} 1^k \\
&= \binom{p}{0} (a-1)^{p} + \binom{p}{1} (a-1)^{p-1} + \cdots + \binom{p}{p-1} (a-1)^{1} + \binom{p}{p} (a-1)^{0} \\
&= (a-1)^{p} + \binom{p}{1} (a-1)^{p-1} + \cdots + \binom{p}{p-1} (a-1) + 1 \\
&= (a-1)^{p} + \binom{p}{1} (a-1)^{p-1} + \cdots + (a-1) + 1 \\
&\equiv (a - 1)^{p} + 1 ~ (\mathrm{mod ~p}) \\
&\equiv (a - 1) + 1 ~ (\mathrm{mod ~p}) \\
&= a ~ (\mathrm{mod ~p})
\end{align}
以上より, 数学的帰納法から, フェルマーの小定理が成り立つことが示された.
おわりに
本記事ではフェルマーの小定理についてまとめました. この記事を読んで気になった方はぜひPythonで学ぶアルゴリズムとデータ構造を手にとって見てください.