二項係数と剰余類の難問 – 2023年京大 特色入試 数学 第4問

2023年5月16日2023年5月29日

まとめ

　p を3以上の素数とします。 a を整数（負でも良い）に対し、自然数 1 \leqq \alpha \leqq p^3 を、

\alpha \equiv a (\mod p^3)

を満たすように選びます。

p ≧ 5 のとき

　命題10により、

{}_{ \alpha p^2 } \mathrm{C}_{p^2} \equiv a ( \mod p^3)

が成り立ちます。

p = 3 のとき

　 a \equiv 0 (\mod 3) または a \equiv 1 (\mod 3) のとき、命題11により、

{}_{9 \alpha } \mathrm{C}_{9} \equiv a ( \mod 27)

が成り立ちます。

　 a \equiv 2 (\mod 3) のとき、命題11により、

{}_{9( \alpha+9) } \mathrm{C}_{9} \equiv a ( \mod 27)

が成り立ちます。

　以上、 p が3以上の素数のとき、任意の整数 a に対し、自然数 n \geqq p^2 を適切に選べば、

{}_{n} \mathrm{C}_{p^2} \equiv a ( \mod p^3) 

が成り立つことが示せました。

解法のポイント

　本問は十分に時間をかければ、解けない問題ではありませんが、証明にちょっとした論文並みのボリュームが必要というのは、入試問題としどうなのかと思います（それとももっと簡単に解く方法があるのだろうか）。

　まず、 _ap²C_p² ≡ a ( mod p³) に気がつくのが至難の業です。何しろ、一番簡単な p =3,a=2 の場合に成り立ちません。

　本稿では以下の段取りで証明を進めていきます。

1. {}_{p^2+lp^2 } \mathrm{C}_{p^2} \equiv {}_{p+lp } \mathrm{C}_{p} ( \mod p^3)( 1\leqq l \leqq p-1) の証明
2. {}_{p+lp } \mathrm{C}_{p} \equiv l+1( \mod p^3) の証明
3. {}_{p^2+bp^3 } \mathrm{C}_{p^2} \equiv bp+1 ( \mod p^3) （ bは自然数）の証明
4. {}_{p^2+lp^2 } \mathrm{C}_{p^2} \equiv l+1 ( \mod p^3) （ l はp の倍数以外）の証明

　 _ap²C_p² ≡ a ( mod p³) があらかじめ予測できていれば、実は項番3と項番4だけで証明できます。しかし、筆者は項番1と項番2を経てはじめて_ap²C_p² ≡ a ( mod p³) に気がついたので、本稿ではその試行錯誤の経緯を記述してあります。このように本問は、方針の当たりを付けるだけでもひと仕事です。

　しかも一番大変なのは、項番2および項番4を証明するための命題7です。これだけでも、整数関連の入試問題としては超難問です。やはり、こんな証明をしなくて良い、もっと楽な方法があるのかも知れません。

　本問を解くにあたってのポイントは

1. \displaystyle\frac{ {}_{p^2+m-1} \mathrm {C}_{p^2}} {m} が自然数である（命題1）
2. 素数を法とする剰余類は積の逆演算としての割り算にも閉じている（命題3）
3. 0でない異なる p-1 個の剰余類の和が p の倍数である（命題2）

です。項番1は剰余類問題を解く際に非常に便利なロジックです。剰余類の問題が大抵素数を法としているのは、まさにこれが成り立つからと言えます。

　項番2も非常に重要です。素数を法とする剰余類が実生活でも役立つのは、この性質のおかげです。にもかかわらず学校では習わないので、これを使う際には証明を準備する必要が有ります。簡単なので証明を覚えておくようにしましょう。

　項番3は複数の値を足しあわせて p の倍数にできるというところが、剰余類の値を具体的に求めたい時に大変重宝します。たくさん項があっても、足しあわせて剰余類的にキャンセルできるのですから、本問のように素数のべき乗和を評価したい時には、ぜひ適用を検討してみてください。

　本問は証明に至るまでの道のりが異常に長いので、受験戦略的にはとっとと見切りをつけるのが唯一の正解としか思えませんが、剰余類の教材としてみると、これほどいろいろ考えさせられる問題は、そうそうありません。本問の解き方をマスターできれば、どのような剰余類の問題でも軽く解けるようになるでしょう。本稿の内容をじっくりと読み込んで、理解を深めるようにしてみてください。