ヒントを見逃したら二項係数の力ずく計算 – 2009年東大 数学 第１問

　2009年東大 数学 第１問 は、二項係数に関する問題です。問題文は以下のとおりです。

自然数 m ≧ 2 に対し、 m-1 個の二項係数
_m \mathrm{C} _1, _m \mathrm{C} _1, \cdots, _m \mathrm{C} _{m-1}
を考え、これらすべての最大公約数を d_m とする。すなわち d_m はこれらすべてを割り切る最大の自然数である。
(1) mが素数ならば、d_m = m であることを示せ。
(2) すべての自然数 k に対し、 k^m-k が d_m で割り切れることを、 k に関する数学的帰納法によって示せ。
(3) m が偶数のとき d_m は1または2であることを示せ。

　ぱっと見、割と何とかなりそうな感じです。早速見ていきましょう。

小問１および小問２の解法

　実際、小問１および小問２は簡単に解けます。

小問１の証明

　まず小問１ですが、自然数 1 \leqq l \leqq m-1 に対し、

_m \mathrm{C} _l = \frac{m!}{l!(m-l)!}

ですが、 m は素数なので、 分母のどれかの数字で割られることはありません。したがって m は _m \mathrm{C}_l, l=1,2, \cdots, m-1 の公約数です。

　一方、 _m \mathrm{C} _1 = m なので、最大公約数は m 以下でなければなりません。よって m は最大公約数です。

小問２の証明

　次に小問２です。わざわざ解き方まで指定してくれているので、しっかり押さえておきたいところです。

　まず k=1 のときは、k^m – k = 0 なので、 d_m に限らずどんな数字でも割り切れます。これを帰納法の初期前提とするのはあんまりな気がするので、 k=2 のときも確認します。

\begin{aligned}

2^m-2 &= (1+1)^m-2 \\
 & = \sum_{i=0}^{m}  {_m \mathrm{C}_i}-2 \\
& = 1 + \sum_{i=1}^{m-1}  {_m \mathrm{C}_i}+1 -2 \\
& = \sum_{i=1}^{m-1}  {_m \mathrm{C}_i}

\end{aligned}

なので、d_m の定義から明らかに、 d_m は 2^m-2 の約数であり、これを割り切ります。

　次に、 k ≧ 2 に対し、 k^m-k が d_m を割り切ると仮定します。

　このとき、

\begin{aligned}
& (k+1)^m -(k+1) \\
= &\sum_{i=0}^m {_m \mathrm{C}_i} k^i -(k+1) \\
=& k^m + \sum_{i=1}^{m-1} {_m \mathrm{C}_i} k^i +1-(k+1) \\
= & k^m - k +  \sum_{i=1}^{m-1} {_m \mathrm{C}_i} k^i 

\end{aligned}

なので、帰納法の仮定と d_m の定義から明らかに、 (k+1)^m – (k+1) は d_m で割り切れます。

　ゆえに、すべての自然数 k に対し、 k^m-k が d_m で割り切れることが証明できました。