ヒントを見逃したら二項係数の力ずく計算 – 2009年東大 数学 第１問
小問３の解法その１：二項係数の素因数評価
問題の建付けから見て、小問３は小問２を活用すると考えるのが自然ですが、筆者はそれを思いつけませんでした。そこで、二項係数が３以上の公約数を持たないことを、ある意味力ずくで証明します。
方針ぎめ
m= 2n (n は自然数）と置くとき、
_{2n} \mathrm{C}_1 = 2nなので、すべての二項係数 _{2n} \mathrm{C}_l, l=1,2, \cdots, 2n-1 が n のすべての素因数を公約数に持たないことを示せれば、二項係数は互いに素である（最大公約数が１）か、最大公約数が２であるかのいずれかである、すなわち dmが１か２のいずれかであることを証明できたことになります。
ところが、
_{2n} \mathrm{C}_l = {_{2n} \mathrm{C}_{2n-l }}なので、 _{2n} \mathrm{C}_l, l=1,2, \cdots, n が n の素因数を公約数に持たないことを示せば良いことがわかります。
記号の準備
そこで n の素因数分解を、
n= \prod_{i=1}^I p_i^{ \alpha_i}と表記します。ここに p_i は n の素因数、 \alpha_i はその次数です。
添字が煩雑なので、 p を p_i のいずれか、 \alpha をその次数とします。このとき、
_{2n} \mathrm{C} _{p^{\alpha}}=\frac{\prod\limits_{j=0}^{p^\alpha -1} (2n - j)}{\prod\limits_{j=0}^{p^\alpha -1} (p^\alpha - j)}
=\prod\limits_{j=0}^{p^\alpha -1} \frac{2n-j}{p^\alpha-j}ですが、ここで j を p のべき乗表記します。すなわち、
j= \sum_{l=0}^{\alpha-1} a_{jl }p^lと表記します。ここに 0 \leqq a_{jl }\leqq p-1 は自然数です。
d_m が１か２であることの証明
以上の準備のもとに、すべての j に対して、
\frac{2n -j}{p^\alpha - j}は分母と分子の p の次数が同じになって、分子の p がすべて約分できることを示します。
a _{j l_0} を、０でない a_{jl} のうち、最も若番のものとします。すなわち、
\begin{aligned}
a_{jl_0} &\ne 0 \\
a_{jl} &= 0(0 \leqq l < l_0)
\end{aligned}です。また、
2n = a p^{\alpha_0}と表記します。ここに a は p と素な自然数です。また \alpha_0 は p の次数です。
\begin{aligned}
& \frac{2n -j}{p^\alpha - j}\\
=& \frac{a p^{\alpha_0} -j}{p^\alpha - j} \\
= & \frac{a p^{\alpha_0} -\sum\limits_{l=l_0}^{\alpha-1} a_{jl }p^l}{p^\alpha - \sum\limits_{l=l_0}^{\alpha-1} a_{jl }p^l} \\
= & \frac{ p^{l_0}(a p^{\alpha_0-l_0 }-\sum\limits_{l=l_0}^{\alpha-1} a_{jl }p^{l-l_0 })}{ p^{l_0}(p^{\alpha-l_0} - \sum\limits_{l=l_0}^{\alpha-1} a_{jl }p^{l-l_0 })} \\
= & \frac{ a p^{\alpha_0-l_0 }-\sum\limits_{l=l_0}^{\alpha-1} a_{jl }p^{l-l_0 }}{ p^{\alpha-l_0} - \sum\limits_{l=l_0}^{\alpha-1} a_{jl }p^{l-l_0 }} \\
= & \frac{ p(a p^{\alpha_0-l_0 -1 }-\sum\limits_{l=l_0+1}^{\alpha-1} a_{jl }p^{l-l_0-1 } )-a_{jl_0}}{ p(p^{\alpha-l_0-1} - \sum\limits_{l=l_0+1}^{\alpha-1} a_{jl }p^{l-l_0 -1 } )- a_{jl_0}} \\
\end{aligned}ですが、分母も分子も、 p で割った余りが -a_{jl_0} で、 p では割りきれません。すなわち、 {2n} \mathrm{C} {p^{\alpha}} は分子の p を分母の p が割りきってしまって、 p を素因数に持ちません。
n のすべての素因数 piに対し、二項係数 _{2n} \mathrm{C}_l, l=1,2, \cdots, 2n-1 の少なくとも１つがこれを素因数に持たないので、n のすべての素因数が二項係数の公約数でないことが示せました。ゆえに dm は１か２のいずれかです。