東京大学理系 2021 年・第 4 問

以下の問いに答えよ。

(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 で割った余りを求めよ。

奇数は 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) が示せました。

奇数の積を 4 で割った余り

(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 から 126 へ落とす

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 です。

2026
2025
2024
2023
2022
2021
2003