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

最強の素数問題！（Gerd AltmannによるPixabayからの画像）

2023年5月29日

m = p のとき

p2+p−1Cp2≡1(mod  p3){}_{p^2+p-1} \mathrm{C}_{p^2} \equiv 1( \mod p^3)

なので、

p2+pCp2=p2+ppp2+p−1Cp2=(p+1)p2+p−1Cp2≡p+1(mod  p3)\begin{aligned} {}_{p^2+p} \mathrm{C}_{p^2} & =\frac{p^2 +p}p {}_{p^2+p-1} \mathrm{C}_{p^2} \\ & = (p+1) {}_{p^2+p-1} \mathrm{C}_{p^2} \\ & \equiv p+1 ( \mod p^3) \end{aligned}

です。

m = 2p のとき

　m = 2p -1 のとき、 m = p-1 の時と同じようにして、

p2+2p−1Cp2=p2∑k=1p−1p2+p+k−1Cp2p+k+p2+pCp2\begin{aligned} {}_{p^2+2p-1} \mathrm{C}_{p^2} = & p^2 \sum_{k=1}^{p-1} \frac{ {}_{p^2+p+k-1} \mathrm{C}_{p^2}}{p+k} +{}_{p^2+p} \mathrm{C}_{p^2} \end{aligned}

ですが、系1により、

p2+2p−1Cp2≡p2+pCp2≡p+1(mod  p3)\begin{aligned} {}_{p^2+2p-1} \mathrm{C}_{p^2} & \equiv{}_{p^2+p} \mathrm{C}_{p^2} \\ & \equiv p+1 ( \mod p^3) \end{aligned}

です。

　したがって m =2p のとき、ある自然数 ζ \zeta が存在して、

p2+2pCp2=(p2+1)p2+p−1Cp2=(p2+1)(p+1+ζp3)=(p2+1)(p+1)+(p2+1)ζp3=p+2Cp+(p2+1)ζp3\begin{aligned} {}_{p^2+2p} \mathrm{C}_{p^2} & =( \frac{p}2 +1) {}_{p^2+p-1} \mathrm{C}_{p^2} \\ & =( \frac{p}2 +1)(p+1 +\zeta p^3) \\ & = (\frac{p}2 +1)(p+1) +(\frac{p}2 +1) \zeta p^3 \\ & = {}_{p+2} \mathrm{C}_{p} +(\frac{p}2 +1) \zeta p^3 \\ \end{aligned}

が成り立ちます。

　 p2+2p-1Cp2 も p+2Cp も自然数なので、 (p2+1)ζp3 (\frac{p}2 +1) \zeta p^3 も自然数です。ところが、 p は2で割り切れないので、 ζ \zeta が2で割り切れる必要が有ります。すなわち、 (p2+1)ζ (\frac{p}2 +1) \zeta は自然数です。

　よって、

p2+2pCp2≡p+2Cp(mod  p3){}_{p^2+2p} \mathrm{C}_{p^2} \equiv {}_{p+2} \mathrm{C}_{p} ( \mod p^3)

です。

m = lp (1 ≦ l ≦ p2-1 ) のとき

p2+pCp2≡p+1Cp(mod  p3)p2+2pCp2≡p+2Cp(mod  p3)\begin{aligned} {}_{p^2+p} \mathrm{C}_{p^2} & \equiv {}_{p+1} \mathrm{C}_{p} ( \mod p^3) \\ {}_{p^2+2p} \mathrm{C}_{p^2} & \equiv {}_{p+2} \mathrm{C}_{p} ( \mod p^3) \end{aligned}

であったので、

p2+lpCp2≡p+lCp(mod  p3){}_{p^2+lp} \mathrm{C}_{p^2} \equiv {}_{p+l} \mathrm{C}_{p} ( \mod p^3)

が成り立つのではないかと予想できます。以下、これを証明します。

　数学的帰納法で証明します。

　 l = 1 の場合は証明済みです。

　 1 ≦ l ≦ p2-2 の範囲で

p2+lpCp2≡p+lCp(mod  p3){}_{p^2+lp} \mathrm{C}_{p^2} \equiv {}_{p+l} \mathrm{C}_{p} ( \mod p^3)

が成り立つと仮定します。

　このとき、帰納法の仮定と系1により、

p2+(l+1)p−1Cp2=p2∑k=1p−1p2+lp+k−1Cp2lp+k+p2+lpCp2≡p+lCp(mod  p3)\begin{aligned} & {}_{p^2+(l+1)p-1} \mathrm{C}_{p^2} \\ & =p^2 \sum_{k=1}^{p-1} \frac{ {}_{p^2+lp+k-1} \mathrm{C}_{p^2}}{lp+k } + {}_{p^2+lp} \mathrm{C}_{p^2} \\ & \equiv {}_{p+l} \mathrm{C}_{p} ( \mod p^3) \\ \end{aligned}

なので、ある自然数 ζ \zeta が存在して、

p2+(l+1)p−1Cp2=ζp3+p+lCp\begin{aligned} & {}_{p^2+(l+1)p-1} \mathrm{C}_{p^2} = \zeta p^3 + {}_{p+l} \mathrm{C}_{p} \\ \end{aligned}

が成り立ちます。

　よって、

p2+(l+1)pCp2=(pl+1+1)p2+(l+1)p−1Cp2=(pl+1+1)(ζp3+p+lCp)=(pl+1+1)ζp3+(pl+1+1)p+lCp=(pl+1+1)ζp3+p+l+1Cp\begin{aligned} & {}_{p^2+(l+1)p} \mathrm{C}_{p^2} \\ & =(\frac{p}{l +1}+ 1){}_{p^2+(l+1)p -1} \mathrm{C}_{p^2} \\ & =(\frac{p}{l+1} + 1) ( \zeta p^3 + {}_{p+l} \mathrm{C}_{p} ) \\ & = (\frac{p}{l +1}+ 1) \zeta p^3 + (\frac{p}{l +1}+ 1){}_{p+l} \mathrm{C}_{p} \\ & = (\frac{p}{l +1}+ 1) \zeta p^3 + {}_{p+l+1} \mathrm{C}_{p} \\ \end{aligned}

が成り立ちますが、左辺と右辺第2項は自然数なので、右辺第1項も自然数です。

　したがって l + 1 が p の倍数でないとき、l+1 は ζ \zeta を割り切る必要が有ります。すなわち、右辺第1項の p3 の係数は自然数です。

　また、 l +1 が p の倍数のとき、 l +1 = kp と置くと、 l ≦ p2-2 なので、 k ≦ p-1 です。このとき

(pl+1+1)ζp3=(1k+1)ζp3( \frac{p}{l+1}+1) \zeta p^3 = (\frac{1}k+1) \zeta p^3

ですが k は p と素なので、 k は ζ \zeta を割り切ります。すなわち、右辺第1項の p3 の係数は自然数です。

　ゆえに右辺第1項は p3 の倍数であり、

p2+(l+1)pCp2≡p+l+1Cp(mod  p3)\begin{aligned} & {}_{p^2+(l+1)p} \mathrm{C}_{p^2} \equiv {}_{p+l+1} \mathrm{C}_{p} ( \mod p^3) \\ \end{aligned}

が成り立ちます。すなわち、1 ≦ l ≦ p2-1 の範囲で

p2+lpCp2≡p+lCp(mod  p3)\begin{aligned} & {}_{p^2+lp} \mathrm{C}_{p^2} \equiv {}_{p+l} \mathrm{C}_{p} ( \mod p^3) \\ \end{aligned}

が証明できました。

ここまででわかったこと

1 ≦ l ≦ p2-1であるとします。 m=lp+k(k=1,2,⋯p−1) m = lp +k (k=1,2,\cdots p-1) と置くとき、

p2+mCp2=p2∑j=1kp2+lp+j−1Cp2lp+j+p2+lpCp2≡p2+lpCp2(mod  p2)≡p+lCp(mod  p2)\begin{aligned} {}_{p^2+m} \mathrm {C} _{p^2} = & p^2 \sum_{j=1}^{k} \frac{{}_{p^2+lp+j-1}\mathrm{C}_{p^2}}{lp+j} +{}_{p^2+lp}\mathrm{C}_{p^2} \\ \equiv & {}_{p^2+lp}\mathrm{C}_{p^2} ( \mod p^2) \\ \equiv & {}_{p+l}\mathrm{C}_{p} ( \mod p^2) \end{aligned}

ですが、既に見てきたように、上式は l = 0 の時も成り立ちます。また、明らかに p2Cp2=pCp=1 {}_{p^2 } \mathrm{C}_{p^2} = {}_{p} \mathrm{C}_p = 1 です。よって、

  • 0 ≦ l ≦ p2-1 かつ1 ≦ j ≦ p-1 のとき、 m = lp+j に対し p2+mCp2≡p+lCp(mod  p2) \bm{ {}_{p^2+m } \mathrm{C}_{p^2} \equiv {}_{p+l} \mathrm{C}_p ( \mod p^2) }
  • 特に0 ≦ l ≦ p2-1 かつ m = lp+p-1 のとき、 p2+lp+p−1Cp2≡p+lCp(mod  p3) \bm { {}_{p^2+lp+p-1 } \mathrm{C}_{p^2} \equiv {}_{p+l} \mathrm{C}_p ( \mod p^3) }
  • 0 ≦ l ≦ p2-1 のとき、 p2+lpCp2≡p+lCp(mod  p3) \bm{ {}_{p^2+lp } \mathrm{C}_{p^2} \equiv {}_{p+l} \mathrm{C}_p ( \mod p^3) }

m = lp (p2 ≦ l) の場合は同じやり方が使えない

　ところで、 l≦p2−1 l \leqq p^2-1 と l に制限があるのは、たとえば l = p2 であったとすると、

p2+p3Cp2=(p2p3+1)p2+p3−1Cp2=(1p+1)p2+p3−1Cp2\begin{aligned} & {}_{p^2+p^3} \mathrm{C}_{p^2} \\ & =(\frac{p^2}{p^3}+ 1){}_{p^2+p^3 -1} \mathrm{C}_{p^2} \\ & =(\frac{1}{p}+ 1){}_{p^2+p^3 -1} \mathrm{C}_{p^2} \\ \end{aligned}

であり、かつ系1とここまでの議論により、

p2+p3−1Cp2=p2∑k=1p−1p2+p3−p+k−1Cp2p3−p+k+p2+p3−pCp2≡p+p2−1Cp(mod  p3)\begin{aligned} & {}_{p^2+p^3-1} \mathrm{C}_{p^2} \\ & =p^2 \sum_{k=1}^{p-1} \frac{ {}_{p^2+p^3-p+k-1} \mathrm{C}_{p^2}}{p^3-p+k } + {}_{p^2+p^3-p} \mathrm{C}_{p^2} \\ & \equiv {}_{p+p^2-1} \mathrm{C}_{p} ( \mod p^3) \\ \end{aligned}

なので、ある自然数 ζ \zeta が存在して、

p2+p3Cp2=(1p+1)p2+p3−1Cp2=(1p+1)(ζp3+p+p2−1Cp)=(1p+1)ζp3+(1p+1)p+p2−1Cp=(1p+1)ζp3+(p+p2p2)p+p2−1Cp=ζp2+ζp3+p+p2Cp≡p+p2Cp(mod  p2)\begin{aligned} & {}_{p^2+p^3} \mathrm{C}_{p^2} \\ & =(\frac{1}{p}+ 1){}_{p^2+p^3 -1} \mathrm{C}_{p^2} \\ & =(\frac{1}{p}+ 1)(\zeta p^3+{}_{p+p^2 -1} \mathrm{C}_{p} )\\ & =(\frac{1}{p}+ 1)\zeta p^3+(\frac{1}{p}+ 1){}_{p+p^2 -1} \mathrm{C}_{p} \\ & =(\frac{1}{p}+ 1)\zeta p^3+(\frac{p+p^2}{p^2}){}_{p+p^2 -1} \mathrm{C}_{p} \\ & = \zeta p^2 +\zeta p^3+{}_{p+p^2 } \mathrm{C}_{p} \\ & \equiv {}_{p+p^2 } \mathrm{C}_{p} ( \mod p^2) \end{aligned}

すなわち mod p2 までしか評価できず、 mod p3 でどうなのかわからないからです。 l≧p2 l \geqq p^2 すなわち m=lp≧p3 m = lp \geqq p^3 の場合は別のアプローチが必要です。

　ここはひとまず、 m の範囲を大きくしていくのは後回しにして、 m ≦ p3 – 1 の範囲で m が p2 の倍数の場合にフィーチャーします。 なにか面白いことが言えるかも知れません。

次ページ→ m が p2 の倍数の場合です

京大2023年

Posted by mine_kikaku