トップ› 東京大学› 2009年› 文系第2問

東京大学 2009年文系第2問解説

方針・初手

(1) は二項係数 $_m\text{C}_k$ の定義式（階乗を用いた式）を書き下し、$m$ が素数であることと分母が $m$ と互いに素であることを用いて、各二項係数が $m$ の倍数になることを示す。また、$_m\text{C}_1 = m$ であることから最大公約数を特定する。
(2) は指定通り $k$ についての数学的帰納法を用いる。$(k+1)^m$ を二項定理で展開し、$k^m - k$ の形と残りの二項係数の和を作り出すことがポイントである。

解法1

(1)

$m$ は素数である。以下、$m=p$（$p$ は素数）とおく。 $k$ を $1 \leqq k \leqq p-1$ を満たす自然数とする。二項係数 $_p\text{C}_k$ は以下のように表される。

$$ _p\text{C}_k = \frac{p!}{k!(p-k)!} = \frac{p(p-1)\cdots(p-k+1)}{k!} $$

分母を払うと、次の等式が得られる。

$$ k! \cdot _p\text{C}_k = p(p-1)\cdots(p-k+1) $$

右辺は $p$ の倍数であるから、左辺の $k! \cdot _p\text{C}_k$ も $p$ の倍数である。ここで、$p$ は素数であり、$1 \leqq k \leqq p-1$ であるから、$k!$ の素因数はすべて $p$ より小さい。したがって、$k!$ と $p$ は互いに素である。ゆえに、$_p\text{C}_k$ は $p$ の倍数である。これが $k=1, 2, \cdots, p-1$ のすべてについて成り立つ。

一方で、$k=1$ のとき、$_p\text{C}_1 = p$ である。 $d_p$ は $_p\text{C}_1, _p\text{C}_2, \cdots, _p\text{C}_{p-1}$ の最大公約数であるから、$d_p$ は $_p\text{C}_1 = p$ の約数である。 $p$ は素数なのでその約数は $1$ と $p$ のみであるが、上で示したようにこれらの二項係数はすべて $p$ の倍数であるから、最大公約数は $p$ となる。よって、$m$ が素数のとき、$d_m = m$ であることが示された。

(2)

自然数 $k$ に対する命題「$k^m - k$ は $d_m$ で割り切れる」を、数学的帰納法を用いて示す。

(i)

$k=1$ のとき

$$ 1^m - 1 = 0 $$

$0$ は任意の自然数の倍数であるから、$d_m$ で割り切れる。よって、$k=1$ のとき命題は成り立つ。

(ii)

$k=l$ （$l$ は自然数）のとき、命題が成り立つと仮定する。すなわち、$l^m - l$ は $d_m$ の倍数であると仮定する。

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

$$ \begin{aligned} (l+1)^m - (l+1) &= \sum_{j=0}^{m} {}_m\text{C}_j l^{m-j} - (l+1) \\ &= \left( {}_m\text{C}_0 l^m + \sum_{j=1}^{m-1} {}_m\text{C}_j l^{m-j} + {}_m\text{C}_m l^0 \right) - l - 1 \\ &= \left( l^m + \sum_{j=1}^{m-1} {}_m\text{C}_j l^{m-j} + 1 \right) - l - 1 \\ &= (l^m - l) + \sum_{j=1}^{m-1} {}_m\text{C}_j l^{m-j} \end{aligned} $$

帰納法の仮定より、$l^m - l$ は $d_m$ の倍数である。また、$d_m$ の定義により、$d_m$ は $_m\text{C}_1, _m\text{C}_2, \cdots, _m\text{C}_{m-1}$ の最大公約数であるから、すべての $j$ ($1 \leqq j \leqq m-1$) について $_m\text{C}_j$ は $d_m$ の倍数である。したがって、整数 $l^{m-j}$ を掛けた和 $\sum_{j=1}^{m-1} {}_m\text{C}_j l^{m-j}$ も $d_m$ の倍数である。

ゆえに、これらの和である $(l+1)^m - (l+1)$ も $d_m$ の倍数となり、$k=l+1$ のときも命題は成り立つ。

（i）, （ii）より、すべての自然数 $k$ に対して、$k^m - k$ は $d_m$ で割り切れることが示された。

解説

本問は「フェルマーの小定理」の証明の背景にある論理を、一般の自然数 $m$ について考察させる教育的な問題である。（1）は $p$ が素数であるときに $_p\text{C}_k$ ($1 \leqq k \leqq p-1$) が $p$ の倍数になるという、整数問題において極めて頻出かつ重要な性質の証明である。階乗の式に直して分母を払い「互いに素」を利用する論証の流れは確実におさえておきたい。（2）は（1）の事実と二項定理を組み合わせることで、差分 $(k+1)^m - (k+1) - (k^m - k)$ が二項係数の和として表されることを利用する。これはフェルマーの小定理 $k^p \equiv k \pmod p$ を帰納法で証明する際の標準的な手法そのものである。