2009年東大理系問題1

2009 東京大学前期MathJax
東大理科 2009前期 1

(1)略
(2)
以下、合同式の法は $d_m$ とする。
すべての整数kに対しこの命題を示せば十分である。k=0のとき確かに成り立つので、 $k^m-k\equiv0$ ⇔ $(k+1)^m-(k+1)\equiv0$ を示せばよい。
$(k+1)^m-(k+1)-(k^m-k)=\displaystyle\sum_{j=1}^{m-1}\binom mjk^j\equiv0$ であるから示された。

(3)
(2)の結果に $k=-1$ を代入して、2が $d_m$ で割り切れるので $d_m=1, 2$

「1または2であることを示せ」と言われた場合にそれぞれの値をとるmの存在までは示す必要はないだろう。最初に解いたとき*1からこのかた、(3)は(2)に固執しても大変なだけで $0=(1-1)^m=2+\displaystyle\sum_{j=1}^{m-1}\binom mj(-1)^j$ から2が $d_m$ で割り切れることを言うのがよいと思っていたのだが、(2)が使えることに十数年越しに気づいた。問題文が「整数」ではなく「自然数」になっているのはニクい。
なお、 $d_m$ はmが素数pの累乗のときp、それ以外のとき1となる。

(i)mが素数の累乗でないとき
$m=qp^k$ （p:素数、q≧2、pとqは互いに素）とおく。 $\displaystyle\binom m{p^k}$ はpの倍数ではないことがルジャンドルの公式*2 よりわかるので、 $d_m$ はpで割り切れない。他の素因数についても同様にいえるので $d_m$ は $m$ と互いに素であるが、 $\displaystyle\binom{m}{1}=m$ も $d_m$ で割り切れるので $d_m=1$ である。
(ii)mが素数の累乗のとき
$m=p^{k+1}$ （p:素数）とおく。 $k=0$ のときは(1)で求めたのでk≧1の場合を考える。
(i)と同様にして $\displaystyle\binom m{p^k}$ は $p^2$ の倍数ではないことがわかり、 $\displaystyle\binom{m}{1}=m$ はp以外の素因数をもたない。
$1\leq n< m$ を満たす $n$ に対し、 $\displaystyle\binom mn=\dfrac mn\binom{m-1}{n-1}$ で $\dfrac mn$ はpの倍数なので、 $\displaystyle\binom mn$ はpの倍数。
以上より $d_m=p$ となる。