東京大学 2009年度理系数学第1問解答・解説

問題

自然数 $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$ に関する数学的帰納法によって示せ。

(3) $m$ が偶数のとき $d_{m}$ は1または2であることを示せ。

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

方針

(1)(2)は文系第2問と同じ構造で，素数の場合は $r_{m} C_{r} = m_{m - 1} C_{r - 1}$ ，帰納法では二項定理を使う。(3)では $d_{m}$ に含まれ得る素因数を調べる。奇素数 $p$ については $m = p^{q} v$ と書き，特定の二項係数 $_{m} C_{p^{q}}$ が $p$ で割り切れないことを，分子と分母に現れる $p$ の個数を比較して示す。さらに2について， $m = 2^{q} v$ で $v > 1$ なら奇数の二項係数を作り， $m = 2^{q}$ なら4で割り切れない二項係数を作る。

解答

(1)

$m$ を素数とする。 $1 ≦ r ≦ m - 1$ では $r$ と $m$ は互いに素である。二項係数には $r_{m} C_{r} = m_{m - 1} C_{r - 1}$ という関係があるので， $r_{m} C_{r}$ は $m$ で割り切れる。 $r$ と $m$ が互いに素であるから， $_{m} C_{r}$ が $m$ で割り切れる。

よって $_{m} C_{1},_{m} C_{2}, \dots,_{m} C_{m - 1}$ はすべて $m$ の倍数である。一方で $_{m} C_{1} = m$ であるから，これらの最大公約数は $m$ を超えられない。したがって $d_{m} = m$ である。

(2)

$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項は帰納法の仮定により $d_{m}$ で割り切れる。また， $d_{m}$ の定義により各 $_{m} C_{r}$ は $d_{m}$ で割り切れる。したがって右辺全体が $d_{m}$ で割り切れる。

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

(3)

$m$ を偶数とする。まず， $d_{m}$ が奇素数を約数にもたないことを示す。 $p$ を $m$ を割る奇素数とし， $m$ を割る $p$ の最大の累乗を $p^{q}$ とする。すなわち $m = p^{q} v$ と書き， $v$ は $p$ で割り切れないとする。 $m$ は偶数で $p$ は奇素数なので， $p^{q} < m$ であり， $_{m} C_{p^{q}}$ は $d_{m}$ を考える並びの中に含まれる。

この二項係数を

_{m} C_{p^{q}} = \frac{m ( m - 1 ) ( m - 2 ) \dots ( m - p ^{q} + 1 )}{p ^{q} ( p ^{q} - 1 ) ( p ^{q} - 2 ) \dots 1}

と書き，先頭の $m / p^{q} = v$ を外すと

_{m} C_{p^{q}} = v \cdot \frac{( m - 1 ) ( m - 2 ) \dots ( m - p ^{q} + 1 )}{( p ^{q} - 1 ) ( p ^{q} - 2 ) \dots 1}

である。

$1 ≦ j ≦ p^{q} - 1$ について， $j$ が $p$ でちょうど $e$ 回割り切れるとする。このとき $e < q$ であり， $m - j = p^{q} v - j$ も $p$ でちょうど $e$ 回割り切れる。したがって積 $(m - 1) (m - 2) \dots (m - p^{q} + 1)$ に含まれる $p$ の個数は， $(p^{q} - 1) (p^{q} - 2) \dots 1$ に含まれる $p$ の個数と等しい。さらに $v$ は $p$ で割り切れない。よって $_{m} C_{p^{q}}$ は $p$ で割り切れない。したがって $d_{m}$ は奇素数を約数にもたない。

次に2の因数を調べる。 $m = 2^{q} v$ と書き， $v$ を奇数とする。 $v > 1$ の場合， $_{m} C_{2^{q}}$ を考えると，同様に

_{m} C_{2^{q}} = v \cdot \frac{( m - 1 ) ( m - 2 ) \dots ( m - 2 ^{q} + 1 )}{( 2 ^{q} - 1 ) ( 2 ^{q} - 2 ) \dots 1}

である。 $1 ≦ j ≦ 2^{q} - 1$ について $m - j$ と $j$ に含まれる2の個数は等しく， $v$ は奇数である。したがって $_{m} C_{2^{q}}$ は奇数である。この場合， $d_{m}$ は奇素数も2も約数にもたないので $d_{m} = 1$ である。

残るのは $m = 2^{q}$ の場合である。このとき $m$ は偶数なので $q ≧ 1$ である。 $m = 2$ なら並びは $_{2} C_{1} = 2$ だけなので $d_{2} = 2$ である。以下 $m ≧ 4$ とする。 $_{m} C_{m /2}$ を考えると

_{m} C_{m /2} = 2 \cdot \frac{( m - 1 ) ( m - 2 ) \dots ( m /2 + 1 )}{( m /2 - 1 ) ( m /2 - 2 ) \dots 1}

である。ここでも $1 ≦ j ≦ m /2 - 1$ について $m - j$ と $j$ に含まれる2の個数は等しいので，分数部分は奇数である。したがって $_{m} C_{m /2}$ は2で割り切れるが4では割り切れない。

以上より， $m$ が偶数のとき $d_{m}$ は奇素数を約数にもたず，また4でも割り切れない。したがって $d_{m} は 1 または 2$ である。

東京大学 2009年度理系数学 第1問

問題

方針

解答

(1)

(2)

(3)

東京大学 2009年度
理系数学第1問