今年の東工大で出題された整数問題は二項係数、特に「カタラン数」に関するものでした。同様の問題が海外の数学コンテストに出題されたこともあり、ひょっとすると東工大を受けるようなハイレベルな受験生の中には解いた経験のある数論マニアが居たかもしれません。
以下の問いに答えよ。
(1)正の整数に対して、二項係数に関する次の等式を示せ。また、これを用いては の倍数であることを示せ。
(2)正の整数に対して、とおく。このとき、 ならば であることを示せ。
(3)が素数となる正の整数をすべて求めよ。
(2021年東京工業大学 前期第3問)
考え方
(1)は示すべき式が明示されており、数学的帰納法で証明しようとした人がいたかもしれませんが、単純な式変形だけで済んでしまいます。数学的帰納法を使うべきなのは(2)の方です。(3)のポイントは のときにが の倍数になるという部分です。これと(2)の不等式からが素数となるようなを絞り込むことができます。
解答例
以下、二項係数が整数であることは既知として解答する。
(1)
となるので成り立つ。これと、とは互いに素であることから、はを割り切る。即ちは の倍数である。
□
(2)
命題 「 ならば である」を数学的帰納法によって示す。
のときとなるから、 が成り立つ。
(はより大きい整数)のとき が成立していると仮定する。このときとなるので のときも成り立つ。
以上より、数学的帰納法から命題 の成立が示された。
□
(3)
となり素数でないので は不適。、 は素数となるので は求める正の整数である。
以下、 のときを考える。
(2)の途中式よりとなる。(1)よりは の倍数であるからは任意の正の整数について整数である。よって は 、、のいずれかを割り切ることが必要である。
が正の整数のとき がを割り切ることは無い。また、より、 が で割り切れるときはも で割り切れる必要があるが、 のときこれは不可能。
よっては で割り切れることが必要である。また、(2)の結論より のとき となるから、ある整数 を用いてと表される。したがって、 のときは素数にならない。
以上より、求める正の整数はである。
本問はカタラン数が素数になる条件を求める問題でした。誘導設問の意図を上手く汲み取れればスムーズだったと思います。(3)で(2)を利用するところが難しかったかもしれません。 という漸化式を利用するところが本問のポイントです。なお、東工大では2016年に階乗の整除性に関する出題があります。
今年の東工大は確率分野の出題が無く、今年で3年連続のお休みとなりました。ここ数年は幾何色の濃いセットが続いています。整数分野も頻出なので論証問題を中心に鍛えておきましょう。