トップ› 東京大学› 2009年› 理系第1問

東京大学 2009年理系第1問解説

方針・初手

(1) は二項係数の定義式 $k! \cdot {}_m\text{C}_k = m(m-1)\cdots(m-k+1)$ に注目し、$m$ が素数の場合に左辺の素因数 $m$ が ${}_m\text{C}_k$ に含まれることを示す。
(2) は数学的帰納法を用いる。(1) の証明などで頻出の二項定理の展開式を用いて、$(n+1)^m - (n+1)$ を変形する。
(3) は (2) で示した「すべての自然数 $k$ で成立する」という事実を利用する。$m$ が偶数であること（$(-1)^m = 1$ となること）を活かすため、$k = d_m - 1$ を代入するという発想が鍵となる。

解法1

(1)

$m$ を素数とする。 $1 \leqq k \leqq m-1$ となる整数 $k$ について、二項係数 ${}_m\text{C}_k$ は

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

と表される。分母を払うと、

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

となる。右辺は $m$ の倍数であるため、左辺の $k! \cdot {}_m\text{C}_k$ も $m$ の倍数である。ここで、$m$ は素数であり、$1 \leqq k \leqq m-1$ であるから、$k!$ は素因数 $m$ を持たない。すなわち、$k!$ と $m$ は互いに素である。したがって、${}_m\text{C}_k$ は $m$ の倍数である。これより、$1 \leqq k \leqq m-1$ を満たすすべての $k$ について ${}_m\text{C}_k$ が $m$ の倍数となるため、それらをすべて割り切る最大の自然数（最大公約数）である $d_m$ も $m$ の倍数である。また、$d_m$ は ${}_m\text{C}_1 = m$ の約数でもあるため、$d_m \leqq m$ である。以上より、$d_m = m$ であることが示された。

(2)

$k$ に関する数学的帰納法を用いて、$k^m - k$ が $d_m$ で割り切れることを示す。

(i)

$k=1$ のとき

$1^m - 1 = 0$ となり、$0$ は任意の自然数の倍数であるから、$d_m$ で割り切れる。よって成立する。

(ii)

$k=n$ ($n$ は自然数) のとき

$n^m - n$ が $d_m$ で割り切れると仮定する。 $k=n+1$ のときを考えると、二項定理より

$$ (n+1)^m - (n+1) = \sum_{j=0}^{m} {}_m\text{C}_j n^{m-j} - (n+1) $$

$$ = \left( n^m + \sum_{j=1}^{m-1} {}_m\text{C}_j n^{m-j} + 1 \right) - (n+1) $$

$$ = (n^m - n) + \sum_{j=1}^{m-1} {}_m\text{C}_j n^{m-j} $$

と変形できる。帰納法の仮定より、$n^m - n$ は $d_m$ で割り切れる。また、$d_m$ の定義から、各 ${}_m\text{C}_j$ ($1 \leqq j \leqq m-1$) はすべて $d_m$ で割り切れる。したがって、その和である $\sum_{j=1}^{m-1} {}_m\text{C}_j n^{m-j}$ も $d_m$ で割り切れる。よって、これらの和である $(n+1)^m - (n+1)$ も $d_m$ で割り切れる。

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

(3)

（2）の結果から、任意の自然数 $k$ に対して $k^m - k$ は $d_m$ の倍数である。 $d_m = 1$ の場合は題意を満たすので、$d_m \geqq 2$ の場合を考える。 $k = d_m - 1$ は自然数であり、これを代入すると、$(d_m - 1)^m - (d_m - 1)$ は $d_m$ の倍数となる。二項定理を用いて展開すると、

$$ (d_m - 1)^m - (d_m - 1) = \sum_{j=0}^{m} {}_m\text{C}_j d_m^{m-j} (-1)^j - d_m + 1 $$

$$ = \left( \sum_{j=0}^{m-1} {}_m\text{C}_j d_m^{m-j} (-1)^j + (-1)^m \right) - d_m + 1 $$

ここで、シグマ記号内の項はすべて $d_m$ を因数に持つため、$d_m$ の倍数である。これを $M d_m$ ($M$ は整数) とおく。また、$m$ は偶数であるから $(-1)^m = 1$ である。したがって、

$$ (d_m - 1)^m - (d_m - 1) = M d_m + 1 - d_m + 1 = d_m(M - 1) + 2 $$

となる。これが $d_m$ の倍数であるためには、$2$ が $d_m$ の倍数でなければならない。 $d_m \geqq 2$ の自然数であるから、$d_m = 2$ となる。以上より、$m$ が偶数のとき、$d_m$ は 1 または 2 であることが示された。

解法2

（3）の別解（合同式を用いた証明）

（2）より、すべての自然数 $k$ において

$$ k^m - k \equiv 0 \pmod{d_m} $$

が成り立つ。 $d_m = 1$ の場合は題意を満たすため、$d_m \geqq 2$ とする。自然数 $k$ として $k = d_m - 1$ を代入すると、

$$ (d_m - 1)^m - (d_m - 1) \equiv 0 \pmod{d_m} $$

ここで、$d_m - 1 \equiv -1 \pmod{d_m}$ であるから、

$$ (-1)^m - (-1) \equiv 0 \pmod{d_m} $$

となる。$m$ は偶数なので $(-1)^m = 1$ であるから、

$$ 1 + 1 \equiv 0 \pmod{d_m} $$

$$ 2 \equiv 0 \pmod{d_m} $$

これは $d_m$ が $2$ を割り切ることを意味する。 $d_m \geqq 2$ の自然数であるから、$d_m = 2$ である。よって、$m$ が偶数のとき、$d_m$ は 1 または 2 である。

解説

(1) は、二項係数が素数 $p$ で割り切れるという有名な性質（フェルマーの小定理の証明などにも用いられる）の証明である。分子に素因数 $p$ が残り、分母の階乗では $p$ が現れないことを記述できればよい。
(2) もフェルマーの小定理の一般化の証明と同様の帰納法である。二項定理を用いた展開において、両端以外の項が $d_m$ の倍数になることを利用する。
(3) は (2) の結果「すべての自然数 $k$ で成立する」ことをどう活かすかが鍵となる。偶数乗の性質 $(-1)^m = 1$ を活かすために、合同式上で $-1$ と合同になる $k = d_m - 1$ を代入するという発想ができると簡潔に示せる。