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

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

前回の証明を少し変更します。

フェルマーの小定理

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

二項定理

今回は $\displaystyle \binom{n}{k}$ を
$\displaystyle (x + 1)^n = \sum_{i=0}^{n} \binom{n}{i} x^i$
$\displaystyle = \binom{n}{n} x^n + \binom{n}{n-1} x^{n-1} + \cdots + \binom{n}{1} x + \binom{n}{0}$
が成り立つものとします。

$f_n(x) = (x + 1)^n$ の $k$ 階導関数
$\displaystyle f_n^{(k)}(x) = \frac{n!}{(n-k)!} (x + 1)^{n-k} = \sum_{i=k}^{n} \binom{n}{i} \frac{i!}{(i-k)!} x^{i-k}$
で $x = 0$ のとき
$\displaystyle f_n^{(k)}(0) = \frac{n!}{(n-k)!} = \binom{n}{k} \cdot k!$
よって
$\displaystyle \binom{n}{k} = \frac{n!}{k! \ (n-k)!}$
が成り立ちます。

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

$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$ で割り切れます。

よって二項定理より
$(x + 1)^{p} \equiv x^p + 1 \pmod p$
が成り立ちます。

帰納法により
$\begin{eqnarray*} n^p & \equiv & ( \underbrace{1+\cdots+1}_n)^{p} \\ & \equiv & ( \underbrace{1+\cdots+1}_{n-1} + 1)^{p} \\ & \equiv & ( \underbrace{1+\cdots+1}_{n-1})^{p} + 1 \\ & \equiv & ( \underbrace{1+\cdots+1}_{n-2} + 1)^{p} + 1 \\ & \equiv & ( \underbrace{1+\cdots+1}_{n-2})^{p} + \underbrace{1+\cdots+1}_{2} \\ & \equiv & ( \underbrace{1+\cdots+1}_{n-3} + 1)^{p} + 1 \\ & \equiv & ( \underbrace{1+\cdots+1}_{n-3})^{p} + \underbrace{1+\cdots+1}_{3} \\ & \vdots & \\ & \equiv & ( \underbrace{1+\cdots+1}_{0})^{p} + \underbrace{1+\cdots+1}_{n} \\ & \equiv & n \pmod p \\ \end{eqnarray*}$
が成り立ちます。