京都大学 1977年 文系 第5問 解説

方針・初手

問題の指示通り、自然数 $n$ についての数学的帰納法を用いて証明を行う。帰納法のステップで $n=k+1$ の場合を考える際、$(k+1)^p$ の展開が必要になるため、二項定理を利用する。その過程で現れる二項係数 ${}_p\mathrm{C}_r$ ($1 \leqq r \leqq p-1$) が、素数 $p$ の倍数になるという性質を示すことが証明の要となる。

解法1

$p$ は素数である。 「どんな自然数 $n$ についても $n^p - n$ は $p$ で割り切れる」という命題を (A) とする。 自然数 $n$ についての数学的帰納法で (A) を証明する。

(i) $n=1$ のとき

$$1^p - 1 = 0$$

$0$ は $p$ で割り切れる（$0 = p \cdot 0$）ので、$n=1$ のとき (A) は成り立つ。

(ii) $n=k$ ($k$ は自然数) のとき、(A) が成り立つと仮定する。

すなわち、$k^p - k$ は $p$ で割り切れるので、ある整数 $m$ を用いて次のように表せる。

$$k^p - k = pm$$

$n=k+1$ のときを考える。 $(k+1)^p - (k+1)$ を二項定理を用いて展開すると、

$$\begin{aligned} (k+1)^p - (k+1) &= \sum_{r=0}^{p} {}_p\mathrm{C}_r k^{p-r} 1^r - (k+1) \\ &= \left( k^p + {}_p\mathrm{C}_1 k^{p-1} + \cdots + {}_p\mathrm{C}_{p-1} k + 1 \right) - k - 1 \\ &= (k^p - k) + \sum_{r=1}^{p-1} {}_p\mathrm{C}_r k^{p-r} \end{aligned}$$

ここで、和の記号の中にある二項係数 ${}_p\mathrm{C}_r$ について考察する。 $1 \leqq r \leqq p-1$ を満たす整数 $r$ において、

$${}_p\mathrm{C}_r = \frac{p!}{r!(p-r)!}$$

分母を払うと、

$$r!(p-r)! {}_p\mathrm{C}_r = p! = p(p-1)!$$

右辺は $p$ の倍数であるから、左辺の $r!(p-r)! {}_p\mathrm{C}_r$ も $p$ の倍数である。 $p$ は素数であり、$1 \leqq r \leqq p-1$ の範囲において、$r!$ および $(p-r)!$ は $p$ より小さい自然数の積であるから、素因数 $p$ を持たない。 したがって、$r!(p-r)!$ と $p$ は互いに素である。 ゆえに、${}_p\mathrm{C}_r$ は $p$ の倍数でなければならない。

よって、$1 \leqq r \leqq p-1$ を満たす各 $r$ に対して、${}_p\mathrm{C}_r = p a_r$ ($a_r$ は整数) とおける。 これを先ほどの式に代入し、帰納法の仮定 $k^p - k = pm$ を用いると、

$$\begin{aligned} (k+1)^p - (k+1) &= pm + \sum_{r=1}^{p-1} p a_r k^{p-r} \\ &= p \left( m + \sum_{r=1}^{p-1} a_r k^{p-r} \right) \end{aligned}$$

$m + \sum_{r=1}^{p-1} a_r k^{p-r}$ は整数であるから、$(k+1)^p - (k+1)$ は $p$ で割り切れる。 したがって、$n=k+1$ のときも (A) は成り立つ。

(i), (ii) より、すべての自然数 $n$ について $n^p - n$ は $p$ で割り切れる。

解説

「フェルマーの小定理」として広く知られている命題の、数学的帰納法を用いた標準的な証明問題である。 証明の中で最も重要なポイントは、「$p$ が素数のとき、$1 \leqq r \leqq p-1$ において二項係数 ${}_p\mathrm{C}_r$ は $p$ の倍数になる」という性質をきちんと示せるかどうかにある。 階乗を用いた定義式から、分子に素因数 $p$ が含まれ、分母には素因数 $p$ が含まれない（$p$ と互いに素である）という論理展開を丁寧に記述することが、採点者に対するアピールポイントとなる。

答え

題意の通り、すべての自然数 $n$ について $n^p - n$ が $p$ で割り切れることが示された。