以下の問いに答えよ。
(1) 正の奇数 K, L と正の整数 A, B が KA = LB を満たしているとする。K を 4 で割った余りが L を 4 で割った余りと等しいならば，A を 4 で割った余りは B を 4 で割った余りと等しいことを示せ。
(2) 正の整数 a, b が a > b を満たしているとする。このとき，A = _{4a+1}\mathrm{C}_{4b+1}, B = _a\mathrm{C}_b に対して KA = LB となるような正の奇数 K, L が存在することを示せ。
(3) a, b は (2) の通りとし，さらに a-b が 2 で割り切れるとする。_{4a+1}\mathrm{C}_{4b+1} を 4 で割った余りは _a\mathrm{C}_b を 4 で割った余りと等しいことを示せ。
(4) _{2021}\mathrm{C}_{37} を 4 で割った余りを求めよ。
K と L は 4 で割った余りが同じですから L = K+4m と書けます。KA = LB に入れると KA = KB+4mB、つまり K(A-B) = 4mB です。
左辺は 4 の倍数です。K は奇数で 4 と互いに素ですから、4 が割り切るのは A-B のほうです。
よって A \equiv B \pmod 4 です。これで (1) が示せました。
奇数を掛けても 4 で割った余りの情報は消えない、というのがこの小問の中身です。あとは、うまい奇数を見つける話になります。
KA = LB を奇数 K, L で作れるのは、A と B が持つ 2 の個数が同じときです。そのとき K を B の奇数部分、L を A の奇数部分に取れば足ります。
n! を、n 以下の奇数の積 O(n) と偶数の積に分けます。偶数の積は 2^{\lfloor n/2 \rfloor}\lfloor n/2 \rfloor! です。
これを _{4a+1}\mathrm{C}_{4b+1} の 3 つの階乗に当てると、O の部分は奇数どうしの比になり、残りが _{2a}\mathrm{C}_{2b} になります。
同じことをもう 1 度すると _a\mathrm{C}_b に落ちます。2 の個数は A と B で等しく、奇数 K, L が取れます。これで (2) が示せました。
(3) では、その K と L が 4 で割って同じ余りを持つことを見ます。どちらも O どうしの積で書けています。
奇数 1, 3, 5, 7, \ldots は 4 で割った余りが 1, 3, 1, 3 と交互です。だから最初の m 個の積は 3^{\lfloor m/2 \rfloor} と同じ余りになります。
O(4a+1) は 3^a、O(2a) は 3^{\lfloor a/2 \rfloor} と同じ余りです。L 側の指数は a+\lfloor a/2 \rfloor、K 側は a+\lfloor b/2 \rfloor+\lfloor (a-b)/2 \rfloor になります。
a-b が偶数なら a と b の偶奇がそろい、\lfloor a/2 \rfloor = \lfloor b/2 \rfloor+\dfrac{a-b}{2} が成り立ちます。指数が一致するので K \equiv L、(1) から (3) が出ます。
2021 = 4 \cdot 505+1、37 = 4 \cdot 9+1 です。505-9 = 496 は偶数ですから (3) が使えます。
よって _{2021}\mathrm{C}_{37} \equiv {}_{505}\mathrm{C}_9 \pmod 4 です。添字が一気に小さくなりました。
もう 1 度使います。505 = 4 \cdot 126+1、9 = 4 \cdot 2+1 で 126-2 = 124 も偶数ですから、_{505}\mathrm{C}_9 \equiv {}_{126}\mathrm{C}_2 \pmod 4 です。
_{126}\mathrm{C}_2 = \dfrac{126 \cdot 125}{2} = 7875 = 4 \cdot 1968+3 です。答えは 3 です。