トップ› 東京大学› 2021年› 理系第4問

東京大学 2021年理系第4問解説

方針・初手

(1) は合同式 $K \equiv L \pmod 4$ を用いて、$KA=LB$ から $A \equiv B \pmod 4$ を導く。$K, L$ が奇数であることから、奇数の2乗が 4 を法として 1 に合同になる性質を利用する。 (2) は二項係数 ${}_{4a+1}\mathrm{C}_{4b+1}$ と ${}_a\mathrm{C}_{b}$ の階乗による定義式から両者の比を計算し、階乗を 4 の倍数とそれ以外に分けることで、関係式を導き出す。 (3) は (2) で構成した $K, L$ について mod 4 を計算し、(1) を適用する。 (4) は (3) の関係を繰り返し用いて、二項係数の値を小さくして直接計算する。

解法1

(1) $K, L$ は正の奇数であるから、整数 $k, l$ を用いて $K=2k+1, L=2l+1$ と表せる。 $K^2 = 4k^2+4k+1 = 4k(k+1)+1$ であり、$k(k+1)$ は偶数であるため $K^2 \equiv 1 \pmod 8$ も成り立つが、ここでは $K^2 \equiv 1 \pmod 4$ が言えれば十分である。同様に $L^2 \equiv 1 \pmod 4$ である。

$KA = LB$ の両辺に $K$ を掛けると、

$$ K^2 A = KL B $$

仮定より $K \equiv L \pmod 4$ であるから、

$$ KL \equiv K^2 \equiv 1 \pmod 4 $$

よって、合同式において $K^2 A \equiv KL B \pmod 4$ が成り立つから、

$$ 1 \cdot A \equiv 1 \cdot B \pmod 4 $$

すなわち、

$$ A \equiv B \pmod 4 $$

が示された。

(2) $A = {}_{4a+1}\mathrm{C}_{4b+1} = \frac{(4a+1)!}{(4b+1)!(4a-4b)!}$、 $B = {}_a\mathrm{C}_{b} = \frac{a!}{b!(a-b)!}$ であるから、

$$ \frac{A}{B} = \frac{(4a+1)!}{(4b+1)!(4a-4b)!} \cdot \frac{b!(a-b)!}{a!} $$

ここで、$(4n)!$ について考える。$1$ から $4n$ までの整数の積を、次のように分類する。

$$ (4n)! = \prod_{k=1}^n (4k) \times \prod_{k=1}^n (4k-1) \times \prod_{k=1}^n (4k-2) \times \prod_{k=1}^n (4k-3) $$

ここで、

$$ \prod_{k=1}^n (4k) = 4^n n! $$

$$ \prod_{k=1}^n (4k-2) = \prod_{k=1}^n 2(2k-1) = 2^n \prod_{k=1}^n (2k-1) $$

であるから、これらをまとめると、

$$ (4n)! = 4^n n! \cdot 2^n \prod_{k=1}^n (4k-1)(2k-1)(4k-3) = 2^{3n} n! M(n) $$

となる。ただし、$M(n) = \prod_{k=1}^n (4k-1)(2k-1)(4k-3)$ とおいた。$M(n)$ はすべて奇数の積であるため、正の奇数である。

この式を用いて $\frac{A}{B}$ を変形すると、

$$ \begin{aligned} \frac{A}{B} &= \frac{(4a+1)(4a)!}{(4b+1)(4b)!(4a-4b)!} \cdot \frac{b!(a-b)!}{a!} \\ &= \frac{4a+1}{4b+1} \cdot \frac{2^{3a} a! M(a)}{2^{3b} b! M(b) \cdot 2^{3(a-b)} (a-b)! M(a-b)} \cdot \frac{b!(a-b)!}{a!} \\ &= \frac{4a+1}{4b+1} \cdot \frac{2^{3a}}{2^{3a}} \cdot \frac{M(a)}{M(b)M(a-b)} \cdot \frac{a! b! (a-b)!}{b! (a-b)! a!} \\ &= \frac{(4a+1)M(a)}{(4b+1)M(b)M(a-b)} \end{aligned} $$

したがって、分母を払うと、

$$ (4b+1)M(b)M(a-b) A = (4a+1)M(a) B $$

となる。ここで、

$$ K = (4b+1)M(b)M(a-b), \quad L = (4a+1)M(a) $$

とおくと、$M(n)$ が正の奇数であることと $a > b \ge 1$ より、$K, L$ はともに正の奇数であり、$KA = LB$ を満たす。よって、題意を満たす $K, L$ が存在することが示された。

(3) (2) で定めた $K, L$ に対して、$K \equiv L \pmod 4$ を示す。

$M(n) = \prod_{k=1}^n (4k-1)(2k-1)(4k-3)$ の各項について 4 を法として考える。 $4k-1 \equiv -1 \pmod 4$ $4k-3 \equiv 1 \pmod 4$ また、$2k-1$ は $k$ が奇数のとき $1 \pmod 4$、$k$ が偶数のとき $-1 \pmod 4$ であるから、$2k-1 \equiv (-1)^{k-1} \pmod 4$ となる。

したがって、

$$ (4k-1)(2k-1)(4k-3) \equiv (-1) \cdot (-1)^{k-1} \cdot 1 = (-1)^k \pmod 4 $$

ゆえに、

$$ M(n) \equiv \prod_{k=1}^n (-1)^k = (-1)^{\sum_{k=1}^n k} = (-1)^{\frac{n(n+1)}{2}} \pmod 4 $$

これより、$K, L$ を 4 で割った余りを調べると、

$$ L = (4a+1)M(a) \equiv 1 \cdot (-1)^{\frac{a(a+1)}{2}} = (-1)^{\frac{a(a+1)}{2}} \pmod 4 $$

$$ K = (4b+1)M(b)M(a-b) \equiv 1 \cdot (-1)^{\frac{b(b+1)}{2}} \cdot (-1)^{\frac{(a-b)(a-b+1)}{2}} = (-1)^{\frac{b(b+1)}{2} + \frac{(a-b)(a-b+1)}{2}} \pmod 4 $$

ここで、$K$ と $L$ の指数部の差をとると、

$$ \begin{aligned} & \frac{a(a+1)}{2} - \left\{ \frac{b(b+1)}{2} + \frac{(a-b)(a-b+1)}{2} \right\} \\ &= \frac{1}{2} \{ (a^2+a) - (b^2+b) - ((a-b)^2 + a-b) \} \\ &= \frac{1}{2} \{ a^2 - b^2 + a - b - (a^2 - 2ab + b^2 + a - b) \} \\ &= \frac{1}{2} (2ab - 2b^2) \\ &= b(a-b) \end{aligned} $$

仮定より $a-b$ は 2 で割り切れる偶数であるから、$b(a-b)$ も偶数である。指数部の差が偶数であるため、$(-1)^{\frac{a(a+1)}{2}} = (-1)^{\frac{b(b+1)}{2} + \frac{(a-b)(a-b+1)}{2}}$ となり、

$$ K \equiv L \pmod 4 $$

が成り立つ。したがって (1) より、$A$ を 4 で割った余りは $B$ を 4 で割った余りと等しい。すなわち、${}_{4a+1}\mathrm{C}_{4b+1}$ を 4 で割った余りは ${}_a\mathrm{C}_{b}$ を 4 で割った余りと等しいことが示された。

(4) (3) の結果を利用する。 $A = {}_{2021}\mathrm{C}_{37}$ について考える。 $2021 = 4 \times 505 + 1$ $37 = 4 \times 9 + 1$ であるから、$a = 505, b = 9$ とおくと、$a-b = 496$ は 2 で割り切れる偶数である。よって (3) より、

$$ {}_{2021}\mathrm{C}_{37} \equiv {}_{505}\mathrm{C}_{9} \pmod 4 $$

次に ${}_{505}\mathrm{C}_{9}$ について考える。 $505 = 4 \times 126 + 1$ $9 = 4 \times 2 + 1$ であるから、$a = 126, b = 2$ とおくと、$a-b = 124$ は 2 で割り切れる偶数である。よって再び (3) より、

$$ {}_{505}\mathrm{C}_{9} \equiv {}_{126}\mathrm{C}_{2} \pmod 4 $$

ここで、${}_{126}\mathrm{C}_{2}$ を計算すると、

$$ {}_{126}\mathrm{C}_{2} = \frac{126 \times 125}{2} = 63 \times 125 $$

となる。 $63 \equiv 3 \pmod 4$、$125 \equiv 1 \pmod 4$ であるから、

$$ 63 \times 125 \equiv 3 \times 1 = 3 \pmod 4 $$

以上より、${}_{2021}\mathrm{C}_{37}$ を 4 で割った余りは 3 である。

解説

階乗を 4 の倍数とそれ以外に分けて計算する手法が核となる問題である。 (1) は合同式の性質を証明する基本問題であり、奇数の 2 乗が 4 を法として 1 と合同になることを用いる。 (2) は階乗から 2 の因子を括り出す処理に帰着する。積を 4 の倍数と奇数部分に分けると、$A/B$ の形が整いやすい。 (3) は $K, L$ の具体的な構成式に対して $\pmod 4$ の評価を行う。連乗積を $(-1)^k$ に読み替えて指数を整理するのが中心となる。 (4) は前問までの誘導に従って、素数 $p$ におけるルーカスの定理に似た構造（今回は mod 4）を利用し、具体的な値を計算する問題である。