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

2023年5月16日2023年5月29日

_p+lpC_p ≡ l+1 (mod p³) の証明

\begin{aligned} {}_{p+lp-1} \mathrm{C}_{lp} & = \prod_{k=1}^{p-1} \frac{lp+k}{k}\\ & = \frac{\sum\limits_{k=1}^{p-1} c_k (lp)^k + (p-1)!}{(p-1)!} \\ & = \frac{\sum\limits_{k=1}^{p-1} c_k (lp)^k }{(p-1)!} +1\\ \end{aligned}

と、分子を p のべき乗展開します。ここに $c_1,c_2,\cdots ,c_{p-1}$ は自然数で、

\begin{aligned} c_1 & = \sum_{k=1}^{p-1} \prod_{\substack{1 \leqq i \leqq p-1 \\ i \ne k} } i \\ c_2 & = \sum_{1 \leqq j< k \leqq p-1}\prod_{\substack{1 \leqq i \leqq p-1 \\ i \ne j \\i \ne k} }i \\ \end{aligned}

です。

　c₁ が p² の倍数、 c₂ が p の倍数であることが言えれば、 $\displaystyle\sum_{k=1}^{p-1} c_k (lp)^k$ は　p³ の倍数になり、ある自然数 $\xi$ が存在して、

\begin{aligned} {}_{p+lp-1} \mathrm{C}_{lp} = \frac{ \xi p^3 }{(p-1)!} +1\\ \end{aligned}

です。 $\displaystyle\frac{ \xi p^3 }{(p-1)!}$ は自然数でかつ、 (p-1)! は p³ と素であることから、 (p-1)! は $\xi$ を割り切ります。

　よって

\begin{aligned} {}_{p+lp-1} \mathrm{C}_{lp} \equiv 1 ( \mod p^3)\\ \end{aligned}

であり、

\begin{aligned} {}_{p+lp} \mathrm{C}_{p} \equiv l+1 ( \mod p^3)\\ \end{aligned}

が成り立ちます。

　以下、c₁ が p² の倍数、 c₂ が p の倍数であることを証明していきますが、それに必要な命題を準備します。

命題の準備

命題3
p を素数とする。任意の自然数 $1\leqq a \leqq p-1$ に対し、 $ab \equiv ( \mod p)$ を満たす自然数 $1 \leqq b \leqq p-1$ がただ1つ存在する

証明
　p-1 以下の自然数 j,k が等しくないとき、明らかに $aj -ak = a(j-k) \not\equiv 0 ( \mod p )$ すなわち

　　　　 $aj \not\equiv ak ( \mod p)$

です。
　よって、 p-1 個の自然数 $a,2a,3a,\cdots ,(p-1)a$ はそれぞれ、別の剰余類に属します。0でない剰余類の個数が p-1 であることから、これら p-1 個の自然数のうちただ1つだけが、1と同じ剰余類になります。したがって命題が証明できました。

　このような b を積に関する逆元と呼び、 $a^{-1}$ と表記することにします。

命題4
p を５以上の素数とする。自然数 $2 \leqq a \leqq p-2$ に対し、 $a$ の積に関する逆元 $a^{-1}$ は、 $a^{-1} \ne a$ かつ $a^{-1} \ne 1$ かつ $a^{-1} \ne p-1$ である。

証明
　背理法で証明します。命題3より、積に関する逆元 $a^{-1}$ がただ１つ存在します。
　もし $a^{-1}=a$ であったとすると、 $a^2 \equiv 1 ( \mod p)$ です。すなわち、ある自然数 $\zeta$ が存在して、

　　　 $a^2 -1 =(a+1)(a-1) = \zeta p$

が成り立つはずです。
　ところが、 p が素数であることから、 $a+1,a-1$ の少なくとも一方は p または p の倍数である必要が有ります。これは $2 \leqq a \leqq p-2$ であることに矛盾するので、　 $a^{-1} \ne a$ であることが証明できました。
　 $a^{-1} \ne 1$ であることは明らかです（もし $a^{-1} = 1$ なら $a \equiv 1 ( \mod p)$ になってしまう）
　また、 $a^{-1} = p-1$ であるとすると、 $(a^{-1})^2 = (p-1)^2 = p^2 -2p +1 \equiv 1 ( \mod p )$ であることから、 $a^{-1}= a$ となり、先に示したとおり、これは仮定条件に矛盾します。

命題5
　p を５以上の素数とする。このとき、 $\prod\limits_{i=2}^{p-2} i \equiv 1 ( \mod p )$ が成り立つ

証明
　命題4により、 $2,3,\cdots , p-2$ の p-3 個の自然数は、 $a\cdot a^{-1} \equiv 1 ( \mod p)$ となる $\frac{p-3}2$ 個の対に、余さず分けられます。したがって、 $\prod\limits_{i=2}^{p-2} i \equiv 1 ( \mod p )$ が成り立ちます。

命題6
　 p を素数とする。任意の自然数 $1\leqq a \leqq p-1$ に対し、

　　 $(p-a)^{-1} \equiv p - a^{-1} ( \mod p)$

が成り立つ。

証明

$(p-a)(p-a^{-1}) = p^2 -(a + a^{-1})p +a \cdot a^{-1} \equiv 1 ( \mod p)$

より明らかです。

次メージ→c₁ が p² の倍数であることの証明です