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

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

2023年京大 特色入試 数学 第4問 は、二項係数の剰余類に関する問題です。問題文は以下のとおりです。

p を3以上の素数とし， a を整数とする．このとき， p² 以上の整数 n であって

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

を満たすものが存在することを示せ．

　剰余類の問題なのに、法が任意の素数 p の、しかも3乗というのがなかなか嫌げです。また、二項係数といったら二項定理で攻めるのがセオリーですが、次数 n が可変なので、きっとそのアプローチも無理筋でしょう。

　京大に特有の、ワンアイデアでスカッとアハ体験、と言ったわけには行きそうもありません。泥沼の予感もしますが、とりあえず見ていきましょう。

_nC_p² を _p²+mC_p² と表記する

　問題文を以下のように読み替えます。

p を3以上の素数とする。整数 0 \leqq a \leqq p^3 -1 が与えられたとき、ある整数 m \geqq 0 が存在して、

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

が成り立つ。

　このように読み替えることで、

\begin{aligned}

 {}_{p^2+m} \mathrm{C}_{p^2} & = \frac{p^2 +m}{m } {}_{p^2+m-1} \mathrm{C}_{p^2} \\
 & = (\frac{p^2}m +1) {}_{p^2+m-1} \mathrm{C}_{p^2} \\
& = \frac{ {}_{p^2+m-1} \mathrm{C}_{p^2} }m p^2+ {}_{p^2+m-1} \mathrm{C}_{p^2}

\end{aligned}

　と p2 のべき乗表記できます。

　しかも、 {}_{p^2+m} \mathrm{C}_{p^2} も {}_{p^2+m-1} \mathrm{C}_{p^2} も整数なのですから、\displaystyle\frac{{}_{p^2+m-1} \mathrm{C}_{p^2}}{m} p^2 も当然整数です。

　よって、m が p の倍数でないとき、 m は {}_{p^2+m-1} \mathrm{C}_{p^2} を割り切ります。すなわち、

\frac{ {}_{p^2+m-1} \mathrm{C}_{p^2} } m

は自然数です。剰余類を考えるにあたって、より取り扱いやすい表記になりました。

　この結果はあとで何度も利用するので、以下のように命題にまとめておきます。

命題１
p を素数とする。自然数 m が p の倍数でないとき、

　　　　　　 \displaystyle\frac{ {}_{p^2+m-1} \mathrm {C}_{p^2}} {m}

は自然数である。

p の具体的な値で実験してみる

　証明の方針を考えるため、 p に具体的な値を代入して、傾向をつかみます。

　 p = 3 で実験してみます。

　予想に反し、 mod 3³ で同じものが何度も現れます。これは何を意味しているかというと、問題文の命題が正しいとしても、 m の範囲を p³ 以上にしないと、　すべての整数 a を網羅することは出来ない、ということです。

　これはもう、時間内に何とかできる気がしませんが、ここで注目すべきは、剰余類を p 進表現した時の1桁目が常に１であることです。もしかしたら、 m が十分小さいときには、 {}_{p^2+ m} \mathrm{C}_{p^2} \equiv 1 ( \mod p) なのかもしれません。そこで、 m をだんだん大きくしていって、傾向を確認することにします。