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

方針・初手

(1) は二項係数を階乗で表し、$k!$ と $(p-k)!$ が $p$ を因数にもたないことを使う。

(2) は $(n+1)^p$ を二項展開し、(1) によって途中の二項係数がすべて $p$ の倍数であることを使う。

(3) は (2) で得た $p \mid n^p-n$ から、$n$ が $p$ の倍数でないことを利用して結論を出す。

解法1

（1）

$1 \leqq k \leqq p-1$ とする。

二項係数は

$$ {}_{p}\mathrm{C}_{k}=\frac{p!}{k!(p-k)!} $$

であるから、

$$ p!={}_{p}\mathrm{C}_{k}k!(p-k)! $$

が成り立つ。

ここで、$1 \leqq k \leqq p-1$ より、$k!$ に含まれる因数はすべて $p$ より小さい。また、$1 \leqq p-k \leqq p-1$ であるから、$(p-k)!$ に含まれる因数もすべて $p$ より小さい。

したがって、$p$ は素数なので、

$$ p \nmid k!, \qquad p \nmid (p-k)! $$

である。

一方、$p!$ は明らかに $p$ で割り切れる。等式

$$ p!={}_{p}\mathrm{C}_{k}k!(p-k)! $$

において、$k!(p-k)!$ は $p$ で割り切れないので、$p$ の因数は ${}_{p}\mathrm{C}_{k}$ に含まれるしかない。

よって、

$$ p \mid {}_{p}\mathrm{C}_{k} $$

である。

したがって、$1 \leqq k \leqq p-1$ のとき、${}_{p}\mathrm{C}_{k}$ は $p$ で割り切れる。

（2）

自然数 $n$ に関して、命題

$$ P(n):\quad p \mid n^p-n $$

を数学的帰納法で示す。

まず $n=1$ のとき、

$$ 1^p-1=0 $$

であるから、$p$ で割り切れる。よって $P(1)$ は成り立つ。

次に、ある自然数 $n$ について $P(n)$ が成り立つ、すなわち

$$ p \mid n^p-n $$

と仮定する。

このとき、二項定理より

$$ \begin{aligned} (n+1)^p &= n^p+{}_{p}\mathrm{C}_{1}n^{p-1}+{}_{p}\mathrm{C}_{2}n^{p-2}+\cdots+{}_{p}\mathrm{C}_{p-1}n+1 \end{aligned} $$

である。したがって、

$$ \begin{aligned} (n+1)^p-(n+1) &= n^p-n+{}_{p}\mathrm{C}_{1}n^{p-1}+{}_{p}\mathrm{C}_{2}n^{p-2}+\cdots+{}_{p}\mathrm{C}_{p-1}n \end{aligned} $$

となる。

帰納法の仮定より、$n^p-n$ は $p$ で割り切れる。

また、(1) より、$1 \leqq k \leqq p-1$ に対して ${}_{p}\mathrm{C}_{k}$ は $p$ で割り切れる。よって、

$$ {}_{p}\mathrm{C}_{1}n^{p-1},\ {}_{p}\mathrm{C}_{2}n^{p-2},\ \ldots,\ {}_{p}\mathrm{C}_{p-1}n $$

はいずれも $p$ で割り切れる。

したがって、

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

も $p$ で割り切れる。つまり $P(n+1)$ が成り立つ。

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

$$ p \mid n^p-n $$

が成り立つ。

（3）

$n$ が $p$ の倍数でないとする。

(2) より、任意の自然数 $n$ に対して

$$ p \mid n^p-n $$

が成り立つ。

ここで、

$$ n^p-n=n(n^{p-1}-1) $$

であるから、

$$ p \mid n(n^{p-1}-1) $$

である。

一方、仮定より $n$ は $p$ の倍数でないので、

$$ p \nmid n $$

である。

$p$ は素数であるから、積 $n(n^{p-1}-1)$ が $p$ で割り切れ、かつ $n$ が $p$ で割り切れないならば、もう一方の因数 $n^{p-1}-1$ が $p$ で割り切れる。

したがって、

$$ p \mid n^{p-1}-1 $$

である。

解説

この問題の中心は、二項定理において

$$ {}_{p}\mathrm{C}_{1},{}_{p}\mathrm{C}_{2},\ldots,{}_{p}\mathrm{C}_{p-1} $$

がすべて $p$ の倍数になることである。

(2) では、$(n+1)^p$ を展開したとき、中間項の係数がすべて $p$ の倍数になるため、帰納法の仮定 $p \mid n^p-n$ をそのまま次の段階に引き継げる。

(3) はフェルマーの小定理の形であり、(2) の

$$ p \mid n^p-n $$

を

$$ p \mid n(n^{p-1}-1) $$

と因数分解して使う。ただし、$n$ が $p$ の倍数でないという条件がなければ、$n$ の因数を取り除くことはできない。この条件が重要である。

答え

(1)

$1 \leqq k \leqq p-1$ のとき、

$$ p \mid {}_{p}\mathrm{C}_{k} $$

である。

(2)

すべての自然数 $n$ について、

$$ p \mid n^p-n $$

である。

(3)

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

$$ p \mid n^{p-1}-1 $$

である。