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

・ m=pを素数とする。1$\le$ r$\le$ p-1に対して $$\displaystyle r\binom{p}{r}=p\binom{p-1}{r-1}$$ であり、p$\nmid$ rだからp$\mid$$\displaystyle \binom{p}{r}$である。特に$\displaystyle \binom{p}{1}=p$なので、これらの最大公約数はpである。

・ $P(k): d_m\mid k^m-k$とおく。k=0では成立する。P(k)が成立するとき、二項定理から $$\displaystyle (k+1)^m-(k+1)-(k^m-k)=\sum\limits _{r=1}^{m-1}\binom{m}{r}k^r.$$ 右辺の各項は$d_m$で割り切れる。よってP(k+1)も成立し、数学的帰納法によりすべての自然数kで成立する（自然数を正の整数とする場合も、k=1から同じ帰納法が使える）。

・ mを偶数とする。まず、奇素数pが$d_m$を割ると仮定する。$\displaystyle d_m\mid\binom{m}{1}=m$より$p\mid m$と書けるので、$m=p^a n$（$a\ge1,\ p\nmid n$）とおく。mは偶数、pは奇数だからnは偶数であり、$n\ge2$、従って$1\le p^a\le m-1$である。(1)の証明より、法pで$(1+x)^p\equiv1+x^p$であり、これを繰り返すと$(1+x)^{p^a}\equiv1+x^{p^a}$となる。ゆえに $$(1+x)^m\equiv(1+x^{p^a})^n\pmod p.$$ 両辺の$x^{p^a}$の係数を比べると$\displaystyle \binom{m}{p^a}\equiv n\not\equiv0\pmod p$。これは$p\mid d_m$なら$\displaystyle p\mid\binom{m}{p^a}$となることに矛盾する。よって$d_m$に奇素因数はない。

・ 次に$4\mid d_m$と仮定する。$d_m\mid m$より$m=2^a n$（$a\ge2$、nは奇数）と書ける。n>1なら、法2で$(1+x)^{2^a}\equiv1+x^{2^a}$だから、 $$(1+x)^m\equiv(1+x^{2^a})^n\pmod2,$$ 従って$\displaystyle \binom{m}{2^a}\equiv n\equiv1\pmod2$。ここで$2^a$は1以上m-1以下なので、これは$2\mid d_m$に矛盾する。よってn=1、すなわち$m=2^a$である。$s=2^{a-1}$とおくと、法2で$(1+x)^s\equiv1+x^s$だから、ある整数係数多項式Rを用いて$(1+x)^s=1+x^s+2R$と書ける。これを二乗して法4で $$(1+x)^{2^a}\equiv(1+x^s)^2\equiv1+2x^s+x^{2s}\pmod4.$$ 従って$\displaystyle \binom{2^a}{2^{a-1}}\equiv2\pmod4$。これは$4\mid d_m$に矛盾する。以上より$d_m$は奇素因数を持たず、4でも割り切れない。従って$d_m=1$または2である。