二項係数が素数になる条件(2021年九州大学前期理系数学第5問)

東大、東工大だけでなく九州大でも二項係数に関する整数問題が出題されました。二項係数がちょっとしたブームになっています。


 

以下の問いに答えよ。

(1)自然数$n$、$k$が $2 \leqq k \leqq n-2$ をみたすとき、${ }_{n} \mathrm{C}_{k}>n$ であることを示せ。

(2)$p$を素数とする。$k \leqq n$ をみたす自然数の組$(n,k)$で ${ }_{n} \mathrm{C}_{k}=p$ となるものをすべて求めよ。

(2021年九州大学 前期理系第5問)

 

 考え方

二項係数が素数になる条件を求めるのが本問の主眼です。問題文に$n$の範囲の指定がありませんが、問題文中に与えられている不等式から$n$は$4$以上だと考えて良いでしょう。(1)を示すには、①差を取って$0$より大きいことを示す、②比を取って$1$より大きいことを示す、という2つの方針があります。解答例では①の方針を取っていますが、どちらの方針でも同程度の手間で解答可能です。(1)を考えれば(2)で求めるべき組はほとんど自明です。


解答例

 

(1)

$$\small \begin{aligned}
{ }_{n} \mathrm{C}_{k}-n &=\frac{n(n-1) \cdots(n-k+1)}{k !}-n \\
&=n\left\{\frac{(n-1) \cdots(n-k+1)}{k !}-1\right\}
\end{aligned}$$より、${ }_{n} \mathrm{C}_{k}>n$ であることを示すには$$(*):\small \frac{(n-1) \cdots(n-k+1)}{k !}-1>0$$を示せばよい。自然数$n$、$k$が $2 \leqq k \leqq n-2$ を満たすとき、この左辺について、$$\small \frac{n-1}{k}>1, \frac{n-2}{k-1}>1, \cdots, \frac{n-k+1}{2}>1$$が成り立つから $\small \dfrac{(n-1) \cdots(n-k+1)}{k !}$ は$1$より大きく、不等式$(*)$が成立する。したがって、${ }_{n} \mathrm{C}_{k}>n$ であることが示された。

 

 

(2)

$k=n$ のとき ${ }_{n} \mathrm{C}_{k}=1$ であるから、${ }_{n} \mathrm{C}_{k}=p$ を満たすような素数$p$は存在しない。

 

$k=1$ または $k=n-1$ のとき、${ }_{n} \mathrm{C}_{k}=n$ であるから $p=n$ となり、$(n,k)=(p,1),(p,p-1)$ を得る。

 

$2 \leqq k \leqq n-2$ のとき、${ }_{n} \mathrm{C}_{k}=p$ は$$n!=p \cdot k! \cdot (n-k)!$$と式変形できるから、左辺は$p$の倍数となる。ところが(1)より ${ }_{n} \mathrm{C}_{k}=p>n$ が成り立つから、左辺の素因数に$p$が現れることは無く不合理である。よってこのとき ${ }_{n} \mathrm{C}_{k}=p$ を満たす素数$p$は存在しない。

 

以上より、求める自然数の組は$$(n,k)=\color{red}{(p,1),(p,p-1)}$$である。

 


 

二項係数${ }_{n} \mathrm{C}_{k}$が素数になるのは$n$が素数の場合に限る、という事実の証明問題です。誘導設問が付いているので幾分易しくなっています。今年の東大の問題でもそうでしたが、二項係数を書き下して分子と分母を比較する方法に思い至れば比較的取り組みやすかったのではないでしょうか。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です