数学ゲーム(24) - 非専門的シンギュラリティー研究所

フェルマーの小定理パズル(1)

フェルマーの小定理は「平方剰余の相互法則(8) - 非専門的シンギュラリティー研究所」でも取り上げましたが、ここでは「中国の剰余定理パズル」を改造してフェルマーの小定理を証明するプログラムを完成させるパズル作りたいと思います。

ユークリッドの互除法を使ってできるのではないかと思ったのですが、Wikipedia を見るとそうではないやり方の方が良いようです。まず二項定理を使った方法を見てみます。

フェルマーの小定理

$p$ を素数、 $a$ を整数とすると、 $a^{p} \equiv a \pmod p$

また

$p$ を素数、 $a$ を $p$ の倍数でない整数( $a$ と $p$ は互いに素)とすると、 $a^{p-1} \equiv 1 \pmod p$

二項係数

$\displaystyle \binom{k}{i} = \frac{k!}{i!(k-i)!}$ という記法を使います。

二項定理

$k = 1, 2, \cdots$ に対して
$\displaystyle (m+n)^{k} = \sum_{i=0}^{k}\binom{k}{i}m^{k-i}n^i$

二項定理の帰納法による証明

$k = 1$ のとき

$左辺 = (m + n)^1 = m + n$ 、
$右辺 = m^1n^0 + m^0n^1 = m + n$

であるから成り立っています。

$k$ のときに成り立つと仮定すると
$\begin{eqnarray*} (m+n)^{k+1} &=& \sum_{i=0}^{k}\binom{k}{i}m^{k-i}n^im + \sum_{i=0}^{k}\binom{k}{i}m^{k-i}n^in \\ &=& \sum_{i=0}^{k}\binom{k}{i}m^{k+1-i}n^i + \sum_{i=0}^{k}\binom{k}{i}m^{k-i}n^{i+1} \\ &=& \sum_{i=0}^{k}\binom{k}{i}m^{k+1-i}n^i + \sum_{i=1}^{k+1}\binom{k}{i-1}m^{k+1-i}n^{i} \\ &=& m^{k+1} + \sum_{i=1}^{k} \left[ \binom{k}{i} + \binom{k}{i-1} \right] m^{k+1-i}n^i + n^{k+1} \\ \end{eqnarray*}$
ここで
$\begin{eqnarray*} \binom{k}{i} + \binom{k}{i-1} &=& \frac{k!}{i!(k-i)!} + \frac{k!}{(i-1)!(k+1-i)!} \\ &=& \frac{k!(k+1-i)}{i!(k+1-i)!} + \frac{k!i}{i!(k+1-i)!} \\ &=& \frac{(k+1)!}{i!(k+1-i)!} \\ &=& \binom{k+1}{i} \end{eqnarray*}$
であるから
$\begin{eqnarray*} (m+n)^{k+1} &=& m^{k+1} + \sum_{i=1}^{k} \binom{k+1}{i} m^{k+1-i}n^i + n^{k+1} \\ &=& \sum_{i=0}^{k+1} \binom{k+1}{i} m^{k+1-i}n^i \\ \end{eqnarray*}$
となって、 $k+1$ のときにも成り立っています。

フェルマーの小定理の二項定理を使った帰納法による証明

$p$ が素数、 $i = 1, 2, \cdots, p-1$ のとき
$\displaystyle \binom{p}{i} = \frac{p!}{i!(p-i)!} = \frac{p (p-1) \cdots (p-i+1)}{i (i-1) \cdots 1}$
の分子は $p$ の倍数、分母は $p$ の倍数ではないので $\displaystyle \binom{p}{i}$ は $p$ で割り切れます。