京都大学 理学部特色入試 2023年度 第4問 解説
（2022年11月に行われた特色入試の問題です。2023年に行われた特色入試の問題はこちら）
問題編
問題
$p$ を $3$ 以上の素数とし、 $a$ を整数とする。このとき、 $p^2$ 以上の整数 $n$ であって\[ {}_n\mathrm{C}_{p^2} \equiv a \pmod {p^3} \]を満たすものが存在することを示せ。
考え方
ヒントがなく、答えの予測も難しく、 $p^3$ が大きいので実験もしづらく、 $\mod {p^3}$ というあまり見ない問題ということもあり、かなり考えづらいです。
答えを予測しても確信を持ちづらく、考える方向性もなかなか定まらないので、非常に難しいです。
二項係数にはいろんな表し方・性質がありますが、余りに関する問題なので、積に関する表現を使って考えだすのが王道でしょう。ただ、いろんな難題をクリアしないといけないので、簡単に示すことは厳しそうです。
解答編
問題
$p$ を $3$ 以上の素数とし、 $a$ を整数とする。このとき、 $p^2$ 以上の整数 $n$ であって\[ {}_n\mathrm{C}_{p^2} \equiv a \pmod {p^3} \]を満たすものが存在することを示せ。
解答
一般に、自然数 $a,b$ が互いに素の場合、\[ a, 2a, 3a, \cdots, (b-1)a \]を $b$ で割ったときの余りは互いに異なる。なぜなら、もし $ax$ と $ay$ を $b$ で割ったときの余りが等しいなら、 $a(x-y)$ は $b$ で割り切れることになり、「互いに素」の条件から $x-y$ が $b$ で割り切れることになるが、 $x,y$ が $b-1$ 以下の互いに異なる自然数の場合にはそういうことは起こらないためである。
上の $b-1$ 個の自然数の中に余りが $0$ であるものはないので、\[ ax \equiv 1 \pmod b \]となる $b-1$ 以下の自然数 $x$ が存在する。このような $x$ を $\mathrm{inv}_b (a)$ で表すことにする。なお、文脈上 $b$ が明らかなときは、略して $\mathrm{inv} (a)$ とも書く。
ここで、 $\dfrac{A}{a}$ が整数で $\dfrac{A}{a}=qb+r$ と表せることができるとき
\begin{eqnarray}
A &=& a(qb+r) \\[5pt]
A \cdot \mathrm{inv}_b (a) &=& a\cdot \mathrm{inv}_b(a) \cdot (qb+r) \\[5pt]
A \cdot \mathrm{inv}_b(a) &\equiv& a\cdot \mathrm{inv}_b(a) \cdot r \equiv r \pmod b \\[5pt]
\end{eqnarray}が成り立つ。つまり、整数 $\dfrac{A}{a}$ を $b$ で割った余りは $A\cdot \mathrm{inv}_b(a)$ を $b$ で割った余りと等しくなる。
以下では、 ${}_{mp^2}\mathrm{C}_{p^2}$ について考える（ $m=1,2,3,\cdots, p^3$ ）。
(i) $p=3$ の場合
\begin{eqnarray} {}_{mp^2}\mathrm{C}_{p^2} &=& {}_{9m}\mathrm{C}_{9} \\[5pt] &=& \frac{\displaystyle \prod_{k=0}^{8} (9m-k)} {\displaystyle \prod_{k=1}^{9} k} \\[5pt] &=& \frac{9m}{9} \cdot \frac{\displaystyle \prod_{k=1}^{8} (9m-k)} {\displaystyle \prod_{k=1}^{8} k} \\[5pt] &=& m\cdot \frac{\displaystyle \frac{1}{9}\prod_{k=1}^{8} (9m-k)} {\displaystyle \frac{1}{9}\prod_{k=1}^{8} k} \\[5pt] \end{eqnarray}が成り立つ。ここで、 $1,2,3,\cdots,8$ の中に $3$ の倍数は $2$ 個あり、 $3^2$ で割り切れるものはないので、最後の式の分母は $3$ と互いに素な自然数となる。具体的に計算すると
\begin{eqnarray}
& &
\frac{1}{9}\cdot \prod_{k=1}^{8} k \\[5pt]
&=&
\frac{1}{9}\cdot 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7 \cdot 8 \\[5pt]
&=&
1 \cdot 2 \cdot 1 \cdot 4 \cdot 5 \cdot 2 \cdot 7 \cdot 8 \\[5pt]
&=&
8 \cdot 10 \cdot 56 \\[5pt]
&\equiv&
80 \cdot 2 \pmod {27} \\[5pt]
&\equiv&
-2 \pmod {27} \\[5pt]
\end{eqnarray}である。
一方、分子については
\begin{eqnarray}
& &
m\cdot \frac{1}{9}\cdot \prod_{k=1}^{8} (9m-k) \\[5pt]
&=&
m\cdot (9m-1) \cdot (9m-2) \cdot (3m-1) \\
& & \cdot (9m-4) \cdot (9m-5) \cdot (3m-2) \\
& & \cdot (9m-7) \cdot (9m-8) \\[5pt]
\end{eqnarray}となる。
\begin{eqnarray}
(9m-1) \cdot (9m-2)
&=&
9^2m^2 -3\cdot 9m+2 \\[5pt]
&\equiv&
2 \pmod {27} \\[5pt]
\end{eqnarray}であり、他も同様に計算すると
\begin{eqnarray}
(9m-4) \cdot (9m-5)
&\equiv&
20 \pmod {27} \\[5pt]
&\equiv&
-7 \pmod {27} \\[5pt]
(9m-7) \cdot (9m-8)
&\equiv&
56 \pmod {27} \\[5pt]
&\equiv&
2 \pmod {27} \\[5pt]
\end{eqnarray}となるので
\begin{eqnarray}
& &
m\cdot \frac{1}{9}\cdot \prod_{k=1}^{8} (9m-k) \\[5pt]
&\equiv&
m\cdot 2\cdot(-7)\cdot2\cdot(3m-1)(3m-2) \pmod{27} \\[5pt]
&\equiv&
-28m\cdot(9m^2-9m+2) \pmod{27} \\[5pt]
&\equiv&
-9m^2(m-1)-2m \pmod{27} \\[5pt]
\end{eqnarray}となる。
よって、 ${}_{9m}\mathrm{C}_{9}$ を $27$ で割ったときの余りを $r_m$ とすると、これは\[ m\cdot \frac{1}{9}\prod_{k=1}^{8} (9m-k) \]に $\mathrm{inv}_{27} (-2)=-14$ を掛けたものを $27$ で割った余りに等しいので
\begin{eqnarray}
r_m
&\equiv&
(-14) \cdot m\cdot \frac{1}{9}\prod_{k=1}^{8} (9m-k)
\pmod {27}
\\[5pt]
&\equiv&
(-14) \cdot \{-9m^2(m-1)-2m\}
\pmod {27}
\\[5pt]
&\equiv&
126m^2(m-1)+28m
\pmod {27}
\\[5pt]
&\equiv&
18m^2(m-1)+m
\pmod {27}
\end{eqnarray}となる。
このことから、 $m \equiv 0,1 \pmod 3$ のときは\[ r_m=m \pmod {27} \]となることがわかる。また、 $m=3q+2$ のときは
\begin{eqnarray}
& &
18m^2(m-1)+m \\[5pt]
& \equiv &
18 (3q+2)^2(3q+1)+m \pmod {27} \\[5pt]
& \equiv &
18 (3q+2) (9q^2+9q+2) +m \pmod {27} \\[5pt]
& \equiv &
18 (3q+2) \cdot 2 +m \pmod {27} \\[5pt]
& \equiv &
72+(3q+2) \pmod {27} \\[5pt]
& \equiv &
3q+20 \pmod {27} \\[5pt]
\end{eqnarray}となるので
\begin{eqnarray}
r_{2} \equiv 20,\
r_{5} \equiv 23,\
r_{8} \equiv 26, \\[5pt]
r_{11} \equiv 2,\
r_{14} \equiv 5,\
r_{17} \equiv 8, \\[5pt]
r_{20} \equiv 11,\
r_{23} \equiv 14,\
r_{26} \equiv 17
\end{eqnarray}となり、 $3$ で割って $2$ 余る、 $27$ 以下の自然数が1つずつ出てくる。
以上から、 ${}_{9m}\mathrm{C}_{9}$ （ $m=1,2,3,\cdots, 27$ ）を $27$ で割った余りの集合には、 $0$ から $26$ までの整数がすべて現れる。
(ii) $p$ が $5$ 以上の素数の場合
\begin{eqnarray} {}_{mp^2}\mathrm{C}_{p^2} &=& \frac{\displaystyle \prod_{k=0}^{p^2-1} (mp^2-k)} {\displaystyle \prod_{k=1}^{p^2} k} \\[5pt] &=& \frac{mp^2}{p^2} \cdot \frac{\displaystyle \prod_{k=1}^{p^2-1} (mp^2-k)} {\displaystyle \prod_{k=1}^{p^2-1} k} \\[5pt] &=& m \cdot \frac{\displaystyle \prod_{k=1}^{p^2-1} (mp^2-k)} {\displaystyle \prod_{k=1}^{p^2-1} k} \\[5pt] \end{eqnarray}ここで、 $1,2,\cdots,p^2-1$ の中に $p$ の倍数は $p-1$ 個あり、 $p^2$ の倍数はない。また、 $mp^2-k$ $(k=1,2,\cdots,p^2-1)$ たちの中にも $p$ の倍数は $p-1$ 個あり、 $p^2$ の倍数はない。よって、分母・分子を $p^{p-1}$ で割ると、どちらも割り切れて、商は $p$ と互いに素な値となる。また、分母・分子に $2^{p^2-1}$ を掛けても、 $p$ と互いに素であることには変わらないので、次のように変形する。（式に出てくる $c_n$ の定義は後で述べる。） \begin{eqnarray} {}_{mp^2}\mathrm{C}_{p^2} &=& m \cdot \frac{\displaystyle \frac{2^{p^2-1}}{p^{p-1}}\prod_{k=1}^{p^2-1} (mp^2-k)} {\displaystyle \frac{2^{p^2-1}}{p^{p-1}}\prod_{k=1}^{p^2-1} k} \\[5pt] &=& m \cdot \frac{\displaystyle \prod_{k=1}^{p^2-1} c_{k}(2mp^2-2k)} {\displaystyle \prod_{k=1}^{p^2-1} 2c_{k}k} \\[5pt] \end{eqnarray}ここで、 $c_n$ は次のような数列とする。 $n$ が $p$ の倍数でないとき、 $c_n=1$
$n$ が $p$ の倍数のとき、 $c_n=\dfrac{1}{p}$
つまり、 $c_{k}(2mp^2-2k)$ や $2c_{k}k$ が $p$ と互いに素な自然数になるように変形したことになる。
最後の式の分母を $N$ とおくと、これは $p$ と互いに素な整数であり、 $m$ に依存しない値であることがわかる。
次に、分子について考える。分子のうち、 $c_k$ 以外の部分は
\begin{eqnarray}
2mp^2-2, 2mp^2-4,\cdots,2(m-1)p^2+4,2(m-1)p^2+2
\end{eqnarray}というように、 $2(m-1)p^2+2$ 以上 $2mp^2-2$ 以下の偶数をすべて掛け合わせたものである。この平均は $(2m-1)p^2$ であり、これとの差を計算すると
\begin{eqnarray}
p^2-2, p^2-4,\cdots,1,-1,\cdots, -p^2+4, -p^2+2
\end{eqnarray}というように、 $-p^2+2$ 以上 $p^2-2$ までの奇数が1つずつ登場する。 $p^2-2$ 以下で正の奇数 $t$ をとると、差が $-t$ のものが必ずあり、
\begin{eqnarray}
& &
\{ (2m-1)p^2 -t \} \{ (2m-1)p^2 +t \} \\[5pt]
&=&
(2m-1)^2p^4 -t^2
\end{eqnarray}という変形ができる。また、もとの数が $p$ の倍数であることと $(2m-1)p^2$ との差の絶対値が $p$ の倍数であることは同値だから
\begin{eqnarray}
& &
\displaystyle \prod_{k=1}^{p^2-1} c_{k}(2mp^2-2k) \\[5pt]
&=&
\displaystyle \prod_{k=1}^{(p^2-1)/2} c_{2k-1}^2 \{ (2m-1)^2p^4 -(2k-1)^2 \} \\[5pt]
\end{eqnarray}となる（つまり、平均値から同じだけ離れているものをペアにして掛ける、という式変形を行った）。
これを展開したときに、 $p^3$ で割り切れない部分を考える。 $c_{2k-1}^2$ は $1$ か $\dfrac{1}{p^2}$ であることを考えれば、2つ以上の波かっこから $p$ を含む項を選ぶと、少なくとも $p^4$ の倍数になってしまう。そのため、 $p^3$ で割り切れない項が出てくるのは、次の2つのケースしかない。
- すべての波かっこについて、 $p$ を含まない側を選ぶ
- $2k-1$ が $p$ の倍数になっているような波かっこから $p$ のついている側を選び、他の波かっこからは $p$ を含まない側を選ぶ
なお、1つ目のケースは、\[ \prod_{k=1}^{(p^2-1)/2} c_{2k-1}^2 \{ -(2k-1)^2 \} \]のことであり、 $m$ によらない、 $p$ と互いに素な値である。これを $K$ とおくことにする。
2つ目のケースに関し、 $2k-1$ が $p$ の倍数であるような\[ c_{2k-1}^2 \{ (2m-1)^2p^4 -(2k-1)^2 \} \]を考える。展開するときに $p$ を含む方を選ぶと
\begin{eqnarray}
& &
c_{2k-1}^2(2m-1)^2p^4 \\[5pt]
&=& (2m-1)^2p^2
\end{eqnarray}が出てくる。他の波かっこからは $p$ の倍数でないほうを選ぶので、それらをすべて掛け合わせると
\begin{eqnarray}
& &
\frac{K}{-c_{2k-1}^2 (2k-1)^2} \\[5pt]
&=&
\frac{K}{-\frac{1}{p^2} (2k-1)^2} \\[5pt]
\end{eqnarray}となる（すべての波かっこから $p$ を含まない方を選んだときの積が $K$ なので）。この値は分数の形をしているが整数である。また、 $p^2-2$ 以下の正の奇数で $p$ の倍数は\[ p,3p,\cdots,p^2-2p \]なので、2つ目のケースで出てくる項をすべて足すと
\begin{eqnarray}
& &
(2m-1)^2p^2 \cdot \frac{K}{-\frac{1}{p^2}} \left\{ \frac{1}{p^2}+\frac{1}{(3p)^2}+\cdots+\frac{1}{(p^2-2p)^2} \right\} \\[5pt]
&=&
-(2m-1)^2 p^2 K \left\{ \frac{1}{1^2}+\frac{1}{3^2}+\cdots+\frac{1}{(p-2)^2} \right\}
\end{eqnarray}となる。これを $p^3$ で割った余りを考えるが、 $p^2$ が掛かっていることを踏まえて\[ K \left\{ \frac{1}{1^2}+\frac{1}{3^2}+\cdots+\frac{1}{(p-2)^2} \right\} \]を $p$ で割った余りを考える。
冒頭で述べたことより、 $K$ に\[ \mathrm{inv}(1)^2+\mathrm{inv}(3)^2+\cdots+\mathrm{inv}(p-2)^2 \]を掛けて $p$ で割った余りを求めればよい（以下では、 $\mathrm{inv}$ は $\mathrm{inv}_p$ の意味で用いる。また、 $\mathrm{inv}(a)^2$ は $\mathrm{inv}(a)$ を2乗したものを表す）。
$\mathrm{inv}(a)$ は $p$ で割り切れない整数なので\[ \mathrm{inv}(1)^2, \mathrm{inv}(3)^2, \cdots, \mathrm{inv}(p-2)^2 \]を $p$ で割った余りは、それぞれ\[ 1^2,2^2,3^2, \cdots, (p-1)^2 \]を $p$ で割った余りのどれかと一致する。また、\[ (p-a)^2 \equiv a^2 \pmod p \]が成り立つことから、上のリストのうち $\left(\dfrac{p-1}{2}\right)^2$ より大きいものはダブっているので考えなくてもいいため\[ 1^2,2^2,3^2, \cdots, \left(\frac{p-1}{2}\right)^2 \]を $p^2$ で割った余りのどれかと一致することがわかる。特に、 $p$ と互いに素な整数を 2乗して $p$ で割った余りは、高々 $\dfrac{p-1}{2}$ 種類だとわかる。
また、 $p-2$ 以下の相異なる正の奇数 $a,b$ が\[ \mathrm{inv}(a)^2 \equiv \mathrm{inv}(b)^2 \pmod p \]を満たしているとすると、両辺に $a^2b^2$ を掛けて\[ a^2 \equiv b^2 \pmod p \]となり、 $(a-b)(a+b)$ が $p$ で割り切れることになる。しかし $a-b$ が $p$ で割り切れることはなく、 $a+b$ も $2p$ 未満の偶数なので $p$ で割り切れないので、\[ \mathrm{inv}(a)^2 \equiv \mathrm{inv}(b)^2 \pmod p \]が成り立たないことがわかる。以上のことから、\[ \mathrm{inv}(1)^2, \mathrm{inv}(3)^2, \cdots, \mathrm{inv}(p-2)^2 \]を $p$ で割った余りは $\dfrac{p-1}{2}$ 種類あるので、\[ 1^2,2^2,3^2, \cdots, \left(\frac{p-1}{2}\right)^2 \]を $p$ で割った余りは互いに異なることがわかり、2つの余りの集合は一致する。
このことから
\begin{eqnarray}
& &
\mathrm{inv}(1)^2+\mathrm{inv}(3)^2+\cdots+\mathrm{inv}(p-2)^2 \\[5pt]
&\equiv&
1^2+2^2+3^2+\cdots+\left(\frac{p-1}{2}\right)^2 \pmod p \\[5pt]
&\equiv&
\frac{\frac{p-1}{2}\cdot \frac{p+1}{2} \cdot p}{6} \pmod p \\[5pt]
&\equiv&
p\cdot \frac{p^2-1}{24} \pmod p \\[5pt]
\end{eqnarray}となる。最後の値は整数であり、 $p$ と $24$ は互いに素なので、最後の値は $p$ の倍数になることがわかる。
このことから、2つ目のケースで出てくる項をすべて足したもの\[ -(2m-1)^2 p^2 K \left\{ \frac{1}{1^2}+\frac{1}{3^2}+\cdots+\frac{1}{(p-2)^2} \right\} \]は $p^3$ で割り切れることがわかる。
こうして、
\begin{eqnarray}
{}_{mp^2}\mathrm{C}_{p^2}
&=&
m \cdot
\frac{\displaystyle \prod_{k=1}^{p^2-1} c_{k}(2mp^2-2k)}
{\displaystyle \prod_{k=1}^{p^2-1} 2c_{k}k} \\[5pt]
&\equiv&
m \cdot K \cdot \mathrm{inv}_{p^3}(N) \pmod {p^3} \\[5pt]
\end{eqnarray}となることがわかる。ここで、 $K,\mathrm{inv}_{p^3}(N)$ は $p$ と互いに素である。よって、この積を $M$ とおくと、 ${}_{mp^2}\mathrm{C}_{p^2}$ （ $m=1,2,3,\cdots, 27$ ）を $p^3$ で割った余りは、 $M, 2M, \cdots, p^3M$ を $p^3$ で割った余りに等しく、これらは互いに異なるので、 $0$ から $p^3-1$ までの整数がすべて現れることがわかる。
(i)(ii)より、 ${}_{mp^2}\mathrm{C}_{p^2}$ （ $m=1,2,3,\cdots, p^3$ ）を考えればよいので、 ${}_n\mathrm{C}_{p^2} \equiv a {p^3}$ を満たす、 $p^2$ 以上の整数 $n$ が存在することが示せた。
（終）
解説
何が想定解なのかわかりませんが、答えのきれいさでいえば、 ${}_{mp^2}\mathrm{C}_{p^2}$ が一番思いつきやすいでしょう。一応、式変形をすれば、 $m\times$ (整数) の形にできます。この「整数」の部分が、 $p^3$ で割った余りが $m$ によらずに固定であり、 $p$ と互いに素であれば、それで証明終わりです。なので、それを示そうとしているのが上の解答です。
分数の形の $\mod p$ は高校数学ではほとんど扱わないため考えづらいかもしれませんが、分母は $m$ によらずにいつも同じ形なので、よく考えればそんなに面倒ではありません。
一方、分子を $\mod p^3$ で考えるのは大変です。展開すると、 $p^2$ のついた項がいくつか出てくるので、これをなんとかしないといけません。1つ1つはわかりませんが、和が $p$ で割れることがいえる（ $p\geqq 5$ のとき）のですが、これをいうのもすごく大変です。しかも、 $p=3$ のときには成り立たないので、これは個別で考えないといけません。
上の解答では、 $p\geqq 5$ の場合、 ${}_{mp^2}\mathrm{C}_{p^2}$ を $m\times$ (整数) の形にしたとき、この整数の部分は $p^3$ で割った余りが $m$ に寄らずに一定であることを示しました。実はこの値は具体的に求めることができ、 $1$ になります。つまり、 $p\geqq 5$ の場合は\[ {}_{mp^2}\mathrm{C}_{p^2} \equiv m \pmod {p^3} \]となります。これを示すには、さらに細かい議論が必要です。
$p=3$ のときも見てみると、結局、 $p=3$, $m\equiv 2 \pmod {3}$ のときだけが例外だとわかります。
なお、途中で、分母・分子に $2^{p^2-1}$ 倍していますが、これはその後で「平均からの差」を考えるときに分数がでないようにするために行っています。また、平均からの差を考える理由は、こうすると $c_{k}(2mp^2-2k)$ を考えるよりも、 $c_{2k-1}^2 \{ (2m-1)^2p^4 -(2k-1)^2 \}$ を考えたほうが、 $p$ の次数が上がって、余りを計算しやすくなるからです。
