東京大学 2009年度文系数学第2問解答・解説

問題

自然数 $m ≧ 2$ に対し， $m - 1$ 個の二項係数

_{m} C_{1},_{m} C_{2}, \dots,_{m} C_{m - 1}

を考え，これらすべての最大公約数を $d_{m}$ とする。すなわち $d_{m}$ はこれらすべてを割り切る最大の自然数である。

(1) $m$ が素数ならば， $d_{m} = m$ であることを示せ。

(2) すべての自然数 $k$ に対し， $k^{m} - k$ が $d_{m}$ で割り切れることを， $k$ に関する数学的帰納法によって示せ。

出典：東京大学 2009年度前期日程第2次学力試験文系第2問

方針

(1)は $m$ が素数であることから， $1 ≦ r ≦ m - 1$ では $r$ と $m$ が互いに素である点を使う。恒等式 $r_{m} C_{r} = m_{m - 1} C_{r - 1}$ により各二項係数が $m$ の倍数であることを示し， $_{m} C_{1} = m$ で最大公約数が $m$ を超えないことを押さえる。(2)は問題の指定通り $k$ に関する帰納法で進め， $(k + 1)^{m} - (k + 1)$ を二項定理で展開して，帰納法の仮定と $d_{m}$ の定義を同時に使う。

解答

(1)

$m$ を素数とする。 $1 ≦ r ≦ m - 1$ を任意にとる。このとき $r$ は $m$ で割り切れないので， $r$ と $m$ は互いに素である。

二項係数について $r_{m} C_{r} = m_{m - 1} C_{r - 1}$ が成り立つ。右辺は $m$ の倍数であるから，左辺 $r_{m} C_{r}$ は $m$ の倍数である。いま $r$ と $m$ は互いに素なので， $_{m} C_{r}$ 自身が $m$ の倍数でなければならない。

したがって

_{m} C_{1},_{m} C_{2}, \dots,_{m} C_{m - 1}

はいずれも $m$ で割り切れる。よって，これらの最大公約数 $d_{m}$ も $m$ の倍数である。一方で $_{m} C_{1} = m$ がこの並びの中に含まれているので， $d_{m}$ は $m$ を超えることはできず，また $m$ を割り切る。以上より $d_{m} = m$ である。

(2)

すべての自然数 $k$ について， $k^{m} - k$ が $d_{m}$ で割り切れることを帰納法で示す。

まず $k = 1$ のとき $1^{m} - 1 = 0$ であり，これは $d_{m}$ で割り切れる。

次に，ある自然数 $k$ について $k^{m} - k$ が $d_{m}$ で割り切れると仮定する。二項定理より

(k + 1)^{m} = k^{m} +_{m} C_{1} k +_{m} C_{2} k^{2} + \dots +_{m} C_{m - 1} k^{m - 1} + 1

である。したがって

(k + 1)^{m} - (k + 1) = k^{m} - k +_{m} C_{1} k +_{m} C_{2} k^{2} + \dots +_{m} C_{m - 1} k^{m - 1}

となる。

右辺の第1項 $k^{m} - k$ は帰納法の仮定により $d_{m}$ で割り切れる。また $d_{m}$ は $_{m} C_{1},_{m} C_{2}, \dots,_{m} C_{m - 1}$ の最大公約数なので，和に現れる各二項係数はすべて $d_{m}$ で割り切れる。よって右辺全体が $d_{m}$ で割り切れる。

したがって $(k + 1)^{m} - (k + 1)$ も $d_{m}$ で割り切れる。数学的帰納法により，すべての自然数 $k$ に対して $k^{m} - k は d_{m} で割り切れる$ ことが示された。

東京大学 2009年度文系数学 第2問

問題

方針

解答

(1)

(2)

東京大学 2009年度
文系数学第2問