【東京大学入試】二項係数の最大公約数と帰納法(2009)

(1) \({}_m \mathrm{C}_1=m\)で, \(m\)は素数であることから, \(d_m\)は\(1\)または\(m\)のいずれかであることがわかる.

次に, \(1\leq k\leq m-1\)を満たす自然数\(k\)に関して,$$
{}_m \mathrm{C}_k=\frac{m!}{k!(m-k)!}=\frac{m\cdot(m-1)!}{k!(m-k)!}
$$であり, \(m>k\), \(m>m-k\)であるから, この分母は\(m\)未満の自然数の積となっている. よって, 分母の素因数はいずれも\(m\)未満となり, 分子の素数\(m\)が約分されることはなく, \({}_m \mathrm{C}_k\)は\(m\)の倍数となる.

これから, \(m\)は\({}_m \mathrm{C}_1,\cdots,{}_m \mathrm{C}{m-1}\)の公約数となっており, 最大公約数\(d_m\)は\(d_m\geq m\)を満たす. 先の条件で, \(d_m=1\), または\(d_m=m\)であったから, \(d_m=m\)がわかる.

(2) すべての自然数\(k\)に対して, \(k^m-k\)が\(d_m\)で割り切れること\(k\)に関する数学的帰納法で証明する.
① \(k=1\)のとき, \(k^m-k=1^m-1=0\)となり, これは\(d_m\)で割り切れるから成り立つ.

② \(k=l\)のとき成り立つと仮定して, \(k=l+1\)のときも成り立つことを示す.
\(k=l\)のとき成り立つので, \(l^m-l\)は\(d_m\)で割り切れるから, 整数\(A\)が存在して, \(l^m-l=d_m\times A\)と表せる.

\(k=l+1\)のとき, $$
\begin{align}
(l+1)^m-(l+1)&=\sum_{n=0}^m {}_m \mathrm{C}_n l^n-l-1\\[1.5ex]
&=l^m+1+\sum_{n=1}^{m-1} {}_m \mathrm{C}_n l^n-l-1\\[1.5ex]
&=d_m\times A+\sum_{n=1}^{m-1} {}_m \mathrm{C}_n l^n\\[1.5ex]
\end{align}
$$となる. ここで, \(1\geq n\geq m-1\)のとき, \({}_m \mathrm{C}_n\)は\(d_m\)で割り切れるので, 自然数\(a_n\)が存在して\({}_m \mathrm{C}_n=d_m\times a_n\)とかけるから, $$
\begin{align}
(l+1)^m-(l+1)&=d_m\times A+\sum_{n=1}^{m-1} d_m\times a_n l^n\\[1.5ex]
&=d_m\times A+d_m\sum_{n=1}^{m-1} a_n l^n\\[1.5ex]
&=d_m\left(A+\sum_{n=1}^{m-1} a_n l^n\right)
\end{align}
$$となり, \((l+1)^m-(l+1)\)が\(d_m\)で割り切れることがわかる. よって, \(k=l+1\)のときも成り立つ.

①, ②から数学的帰納法により, すべての自然数\(k\)に対して, \(k^m-k\)が\(d_m\)で割り切れることが示された.