今年も2次試験のシーズンになりました。今回は東大の整数問題を扱います。論証が難しい問題でした。
以下の問いに答えよ。
（１）正の奇数$K$、$L$と正の整数$A$、$B$が $KA=LB$ を満たしているとする。$K$を$4$で割った余りが$L$を$4$で割った余りと等しいならば、$A$を$4$で割った余りは$B$を$4$で割った余りと等しいことを示せ。
（２）正の整数$a$、$b$が $a>b$ を満たしているとする。このとき、$A={ }_{4 a+1} \mathrm{C}_{4 b+1}$、$B={ }_{a} \mathrm{C}_{b}$に対して $KA=LB$ となるような正の奇数$K$、$L$が存在することを示せ。
（３）$a$、$b$は（２）の通りとし、さらに $a-b$ が$2$で割り切れるとする。${ }_{4 a+1} \mathrm{C}_{4 b+1}$を$4$で割った余りは${ }_{a} \mathrm{C}_{b}$を$4$で割った余りと等しいことを示せ。
（４）${ }_{2021} \mathrm{C}_{37}$を$4$で割った余りを求めよ。
（2021年東京大学 前期共通 第4問）
考え方
二項係数に関連する整数問題は3年ぶりで、2015年や2018年の問題と同様に分子と分母の偶奇性に着目させる出題でした。本問は誘導設問が３つも付いています。（２）と（３）の論証が難しいでしょうか。論証の際は二項係数を書き下して考えるのが肝です。$4$で割った余りに注目して${ }_{4 a+1} \mathrm{C}_{4 b+1}$の中から${ }_{a} \mathrm{C}_{b}$を炙り出すことができるかがポイントになります。先回りして（４）だけ解答することも一応可能ですが…。
解答例
（１）
$k$、$l$を整数とし、$K$、$L$を$4$で割った余りを $r$（$=1,3$）として $K=4k+r$、$L=4l+r$ と置く。
$KA=LB$ が成り立つとき、$$(4k+r)A=(4l+r)B$$ $$\therefore 4(kA-lB)=r(B-A)$$となるが、$r$は$4$の倍数でないので、$B-A$ が$4$の倍数であることが必要である。これより、$A$を$4$で割った余りは$B$を$4$で割った余りと等しい。
□
（２）
$A$の分子･分母を書き下したときに、分子･分母に$4$の倍数が現れる項とそれ以外を分けて表すと$$\small \begin{align} A &={ }_{4 a+1} \mathrm{C}_{4 b+1} \\ &=\dfrac{4 a+1}{4 b+1} \cdot \dfrac{4 a}{4 b} \cdot \dfrac{4 a-1}{4 b-1} \cdots \dfrac{4(a-b)+2}{2} \cdot \dfrac{4(a-b)+1}{1} \\ &= \color{red}{\dfrac{4 a}{4 b} \cdot \dfrac{4(a-1)}{4(b-1)} \cdot \dfrac{4(a-2)}{4(b-2)} \cdots \dfrac{4(a-b+1)}{4}} \\
& \quad \cdot \color{blue}{\dfrac{4 a+1}{4 b+1} \cdot \dfrac{4 a-1}{4 b-1} \cdot \dfrac{2 a-1}{2 b-1} \cdot \dfrac{4 a-3}{4 b-3} \cdot \dfrac{4 a-5}{4 b-5} \cdot \dfrac{2 a-3}{2 b-3}} \\
& \quad \quad \color{blue}{\cdots \dfrac{2(a-b)+1}{1} \cdot \dfrac{4(a-b)+1}{1}} \end{align}$$となる。
ここで$$\small \begin{align} & \quad \color{red}{\dfrac{4 a}{4 b} \cdot \dfrac{4(a-1)}{4(b-1)} \cdot \dfrac{4(a-2)}{4(b-2)} \cdots \dfrac{4(a-b+1)}{4}} \\ &= \dfrac{a}{b} \cdot \dfrac{a-1}{b-1} \cdot \dfrac{a-2}{b-2} \cdots \dfrac{a-b+1}{1} \\ &= { }_{a} \mathrm{C}_{b} \ (=B) \end{align}$$である。また、$$\small \begin{align} & \quad \color{blue}{\dfrac{4 a+1}{4 b+1} \cdot \dfrac{4 a-1}{4 b-1} \cdot \dfrac{2 a-1}{2 b-1} \cdot \dfrac{4 a-3}{4 b-3} \cdot \dfrac{4 a-5}{4 b-5} \cdot \dfrac{2 a-3}{2 b-3}} \\
& \quad \quad \color{blue}{\cdots \dfrac{2(a-b)+1}{1} \cdot \dfrac{4(a-b)+1}{1}} \\ &=\dfrac{(4 a+1)(4 a-1)(2a-1) \cdots \{4(a-b)+1\}}{(4 b+1)(4 b-1)(2b-1) \cdots 1}\end{align}$$について分母を$K$、分子を$L$と置くと、$K$、$L$はともに奇数であり、$${ }_{4 a+1} \mathrm{C}_{4 b+1}={ }_{a} \mathrm{C}_{b} \cdot \dfrac{L}{K}$$となるから、$A={ }_{4 a+1} \mathrm{C}_{4 b+1}$、$B={ }_{a} \mathrm{C}_{b}$に対して $KA=LB$ となるような正の奇数$K$、$L$が存在することが示される。
□
（３）
まず、$$\small \begin{aligned} L=&\,\quad (4 a+1)(4 a-1)(2 a-1) \\ & \times(4 a-3)(4 a-5)(2 a-3) \\ & \ldots \ldots \\ & \times(4 a-4 b+5)(4 a-4 b+3)(2 a-2 b+1) \\ & \times(4 a-4 b+1) \\ \\ K=&\,\quad (4 b+1)(4 b-1)(2 b-1) \\ & \times(4 b-3)(4 b-5)(2 b-3) \\ & \quad \quad \vdots \\ & \times 5 \times 3 \times 1 \\ & \times 1 \end{aligned}$$と表せることに注意する。
任意の整数$r$について $4a+r$ を$4$で割った余りと $4b+r$ を$4$で割った余りは等しい。
また、正の整数$a$、$b$について $a-b$ が$2$で割り切れるとき、$$(2a+r)-(2b+r)=2(a-b)$$は$4$の倍数となるから、$2a+r$ を$4$で割った余りと $2b+r$ を$4$で割った余りは等しい。
以上のことから、$K$、$L$の各項を比較することにより、$K$を$4$で割った余りと$L$を$4$で割った余りは等しいことが分かる。
これと、（２）より$$K \cdot { }_{4 a+1} \mathrm{C}_{4 b+1}=L \cdot { }_{a} \mathrm{C}_{b} $$が成り立つこと、および$K$、$L$がともに正の奇数であることから（１）の結果を用いて、${ }_{4 a+1} \mathrm{C}_{4 b+1}$を$4$で割った余りは${ }_{a} \mathrm{C}_{b}$を$4$で割った余りに等しいことが示される。
□
（４）
（３）の結果を利用して、$$\begin{aligned} { }_{2021} \mathrm{C}_{37} & \equiv {}_{505}\mathrm{C}_{9}\pmod{4} \\ & \equiv {}_{126}\mathrm{C}_{2}\pmod{4} \\ &=63 \cdot 125 \\ & \equiv 3 \cdot 1 \pmod{4} \\ & = 3 \end{aligned}$$となるから、${ }_{2021} \mathrm{C}_{37}$を$4$で割った余りは$$\color{red}{3}$$である。
本問は論証の手掛かりが掴みにくく、試験場で取り組むには難しい問題だったのではないかと思います。ポイントとなるのは${ }_{4 a+1} \mathrm{C}_{4 b+1}$の分子･分母を書き下して考える部分です。「$A={ }_{4 a+1} \mathrm{C}_{4 b+1}$、$B={ }_{a} \mathrm{C}_{b}$に対して $KA=LB$ となるような正の奇数$K$、$L$が存在する」ということは、$A$が$$A=\dfrac{L}{K}\times B$$という形で表せることに相当します。ここから、$A$を書き下して$B$を炙り出し、$\dfrac{L}{K}$に当たる分子･分母が奇数の分数を発見できるのではないか、というのが（２）の式変形のモチベーションです。この奇数のペアは積の形で取り出せるので、各要素を$4$で割った余りについて比較すれば$K$を$4$で割った余りと$L$を$4$で割った余りは等しいことが言えます。これが（３）の方針です。（４）は前問の結果を利用して計算するだけなので特に問題は無いでしょう。
今年の東大理系数学は特に解析色の強いセットでした。今年も確率の問題が出題されず、理系数学は4年連続で確率分野からの出題がありませんでした。これは東大数学の歴史の中でも異例のことです。
最近の東大数学では二項係数を題材にした問題が頻繁に出題されています。関連して、2018年の問題や2015年の問題をさらっておくと良いでしょう。整数問題ではありませんが2020年の問題も参考になると思います。