ヒントを見逃したら二項係数の力ずく計算 – 2009年東大 数学 第１問
目次
小問３の解法その２：小問２の結果を活用する
小問２の結果を活用する解法も、もちろん存在します。以下の解法は赤本を参考にしています。
小問２の結果より、すべての自然数 k に対して、 km – k は dm で割り切れます。したがって、 k = dm – 1 の時も割り切れます。
\begin{aligned}
& (d_m -1 )^m - (d_m -1) \\
= & (d_m-1) \{(d_m -1)^{m-1} -1 \}
\end{aligned}ですが、ここで dm -1 が dm と互いに素であることに着目します。
一般に、隣り合う自然数 n と n-1 は互いに素です。それらの最大公約数を c と置き、
\begin{aligned}
n & = a c \\
n-1 & = bc
\end{aligned}と表記します。ここに a,b は自然数です。このとき、
ac-1 = bc
なので、
(a-b)c = 1
ですが、 a – b も c も自然数なので、
c= 1
すなわち、 n と n – 1 は互いに素です。
dm と dm– 1 が互いに素なので、 (dm -1)m-1 – 1 は dm で割り切れます。ところが、
\begin{aligned}
& (d_m -1)^{m-1} - 1 \\
= & \sum_{i=0}^{m-1} {_{m-1} \mathrm{C}_i}(d_m)^i (-1)^{m-1-i} -1 \\
= & d_m \left \{ \sum_{i=1}^{m-1} {_{m-1} \mathrm{C}_i} (d_m)^{i-1}(-1)^{m-1-i} \right\} \\
&+(-1)^{m-1}-1
\end{aligned}であり、かつ m が偶数であることから (-1)^{m-1} = -1 なので、
\begin{aligned}
& (d_m -1)^{m-1} - 1 \\
= & d_m \left \{ \sum_{i=1}^{m-1} {_{m-1} \mathrm{C}_i} (d_m)^{i-1}(-1)^{m-1-i} \right\} -2
\end{aligned}が成り立ちます。
(dm -1)m-1 – 1 は dm で割り切れるので、 -2 も dm で割り切れるはずです。したがって、 dm は１か２のいずれかです。