数学A フェルマーの小定理 問題 8 解説

方針・初手

まず二項係数 $_p C_r$ が $p$ で割り切れることを示し、それを二項展開に利用する。

(2) は $(n+1)^p$ を二項展開すれば、両端以外の項に $_p C_r$ が現れる。(3) は (2) を使って数学的帰納法で示す。(4) は (3) の結果を合同式で読み替える。

解法1

(1)

$r=1,2,\dots,p-1$ とする。

$$ {}_p C_r=\frac{p!}{r!(p-r)!} $$

である。ここで $1\leqq r\leqq p-1$ より、$r!$ にも $(p-r)!$ にも素数 $p$ は因数として含まれない。

一方、$p!$ には因数 $p$ がちょうど $1$ 個含まれる。したがって、分母 $r!(p-r)!$ ではこの因数 $p$ は消えない。

よって $_p C_r$ は $p$ の倍数である。

(2)

二項定理より、

$$ (n+1)^p=\sum_{r=0}^{p} {}_p C_r n^{p-r} $$

である。両端の項を取り出すと、

$$ (n+1)^p=n^p+{}_p C_1n^{p-1}+{}_p C_2n^{p-2}+\cdots+{}*p C*{p-1}n+1 $$

となる。

したがって、

$$ (n+1)^p-(n^p+1) ={}_p C_1n^{p-1}+{}_p C_2n^{p-2}+\cdots+{}*p C*{p-1}n $$

である。

(1) より、$r=1,2,\dots,p-1$ に対して $_p C_r$ はすべて $p$ の倍数である。よって右辺の各項は $p$ の倍数である。

したがって、

$$ (n+1)^p-(n^p+1) $$

は $p$ の倍数である。

(3)

$n$ に関する数学的帰納法で示す。

$n=1$ のとき、

$$ 1^p-1=0 $$

であり、これは $p$ の倍数である。

次に、ある自然数 $n$ について

$$ n^p-n $$

が $p$ の倍数であると仮定する。

このとき、

$$ \begin{aligned} (n+1)^p-(n+1) &={(n+1)^p-(n^p+1)}+(n^p-n) \end{aligned} $$

である。

(2) より、$(n+1)^p-(n^p+1)$ は $p$ の倍数である。また、帰納法の仮定より、$n^p-n$ も $p$ の倍数である。

したがって、

$$ (n+1)^p-(n+1) $$

も $p$ の倍数である。

よって数学的帰納法により、すべての自然数 $n$ について

$$ n^p-n $$

は $p$ の倍数である。

(4)

(3) より、

$$ n^p-n\equiv 0 \pmod p $$

である。すなわち、

$$ n(n^{p-1}-1)\equiv 0 \pmod p $$

である。

ここで、$n$ が $p$ の倍数である場合とそうでない場合に分ける。

(i)

$n$ が $p$ の倍数であるとき

$n\equiv 0\pmod p$ であるから、

$$ n^{p-1}\equiv 0 \pmod p $$

である。

したがって、$n^{p-1}$ を $p$ で割った余りは $0$ である。

(ii)

$n$ が $p$ の倍数でないとき

$p$ は素数であり、$n$ は $p$ の倍数でないから、$n$ と $p$ は互いに素である。

$$ n(n^{p-1}-1)\equiv 0 \pmod p $$

において、$p$ は $n$ を割らないので、$p$ は $n^{p-1}-1$ を割る。

したがって、

$$ n^{p-1}\equiv 1 \pmod p $$

である。

よって、$n^{p-1}$ を $p$ で割った余りは $1$ である。

解説

この問題は、二項定理からフェルマーの小定理を導く標準的な流れである。

中心になるのは、素数 $p$ に対して中間の二項係数 $_p C_1,{}_p C_2,\dots,{}*p C*{p-1}$ がすべて $p$ の倍数になる点である。これにより、二項展開したときに両端以外の項がすべて $p$ の倍数として処理できる。

(3) は (2) を使った数学的帰納法で処理するのが自然である。(4) では、$n$ が $p$ の倍数かどうかで余りが変わるため、場合分けを省略してはいけない。

答え

(1)

$r=1,2,\dots,p-1$ に対して、$_p C_r$ は $p$ の倍数である。

(2)

$(n+1)^p-(n^p+1)$ は $p$ の倍数である。

(3)

$n^p-n$ は $p$ の倍数である。

(4)

$$ n^{p-1}\text{ を }p\text{ で割った余り} = \begin{cases} 0 & (p\mid n)\\ 1 & (p\nmid n) \end{cases} $$