文献あり

一般化Lucasの定理と東大数学2021

883

はじめに

　この記事では今年の東大入試問題を起点に二項係数 $_{n} C_{m}$ にまつわる法 $p^{e}$ の合同関係を紹介していきます。
　さて今年の東大入試では第4問に次のような問題が出たとのことでした。

　以下の問いに答えよ。
(1) 正の奇数 $K, L$ と正の整数 $A, B$ が $K A = L B$ を満たしているとする。 $K$ を $4$ で割った余りが $L$ を $4$ で割った余りと等しいならば、 $A$ を $4$ で割った余りは $B$ を $4$ で割った余りと等しいことを示せ。
(2) 正の整数 $a, b$ が $a > b$ を満たしているとする。このとき、 $A =_{4 a + 1} C_{4 b + 1}, B =_{a} C_{b}$ に対して $K A = L B$ となるような正の奇数 $K, L$ が存在することを示せ。
(3) $a, b$ は(2)の通りとし、さらに $a - b$ が $2$ で割り切れるとする。 $_{4 a + 1} C_{4 b + 1}$ を $4$ で割った余りは $_{a} C_{b}$ を $4$ で割った余りと等しいことを示せ。
(4) $_{2021} C_{37}$ を $4$ で割った余りを求めよ。

　(1)は $K \equiv L \in (Z / 4 Z)^{\times}$ より
$A \equiv K^{- 1} K A = K^{- 1} L B \equiv L^{- 1} L B \equiv B (\mod 4)$
という話で、(4)は(3)から
$_{2021} C_{37} \equiv_{505} C_{9} \equiv_{126} C_{2} = 63 \cdot 125 \equiv 3 (\mod 4)$
という単純な話ですが気になるのは(2)と(3)です。(2)はひとまず置いておくとして(3)を見て私はまずLucasの定理が頭に浮かびました。

Lucasの定理

　素数 $p$ と非負整数 $n, m$ に対して $n, m$ の $p$ 進数表示を
$\begin{aligned} n & = n_{d} n_{d - 1} \dots n_{1} n_{0}_{(p)} & (= n_{d} p^{d} + n_{d - 1} p^{d - 1} + \dots + n_{1} p + n_{0}) \\ m & = m_{d} m_{d - 1} \dots m_{1} m_{0}_{(p)} & (= m_{d} p^{d} + m_{d - 1} p^{d - 1} + \dots + n_{1} p + m_{0}) \end{aligned}$
とおくと
$_{n} C_{m} \equiv_{n_{d}} C_{m_{d}} \cdot_{n_{d - 1}} C_{m_{d - 1}} \dots_{n_{1}} C_{m_{1}} \cdot_{n_{0}} C_{m_{0}} (\mod p)$
が成り立つ。ただし $n < m$ に対しては $_{n} C_{m} = 0$ と定める。

　しかしLucasの定理からわかるのは
$_{4 a + 1} C_{4 b + 1} \equiv_{a} C_{b} \cdot_{0} C_{0} \cdot_{1} C_{1} =_{a} C_{b} (\mod 2)$
であって法 $4$ における合同関係まではわかりません。となるとLucasの定理の素数冪版を考えてみたくなります。自力では思いつかなかったので Lucas's theorem - Wikipedia を覗いてみると

Andrew Granville has given a generalization of Lucas's theorem to the case of p being a power of prime.
(Andrew GranvilleはLucasの定理の素数冪を法とした場合への一般化を与えました。)

とあったので早速そのリンク先を見てみることにしました。

Kummerの定理と一般化Lucasの定理

　証明は後にするとしてまずはAndrew Granvilleの得た結果と先の問題への応用を見てみましょう。
　以下 $n, m$ を非負整数とし、 $n, m$ および $l = n - m$ の $p$ 進数表示を
$\begin{array}{rcl} n & = & n_{d} n_{d - 1} \dots n_{1} n_{0}_{(p)} \\ m & = & m_{d} m_{d - 1} \dots m_{1} m_{0}_{(p)} \\ l & = & l_{d} l_{d - 1} \dots l_{1} l_{0}_{(p)} \end{array}$
とおき、 $ε_{i}$ を $p$ 進数における足し算 $m + l$ の各桁について $m_{i} + l_{i} + ε_{i - 1}$ が繰り上がるとき(つまり $m_{i} + l_{i} + ε_{i - 1} \geq p$ のとき) $ε_{i} = 1$ 、繰り上がらないとき( $m_{i} + l_{i} + ε_{i - 1} < p$ のとき) $ε_{i} = 0$ と定める。

Kummerの定理

　 $_{n} C_{m}$ の素因数分解における素因数 $p$ の指数 $v_{p} (_{n} C_{m})$ は $p$ 進数での足し算 $m + l (= n)$ における繰り上がりの回数 $\sum_{i = 0}^{d - 1} ε_{i}$ に等しい。

　例えば $_{2021} C_{37}$ の素因数分解における素因数 $5$ の指数を考えてみよう。
　 $2021 - 37 = 1984 = 30414_{(5)}$ と $37 = 122_{(5)}$ の足し算を考えると
$\begin{array}{cr} 1 1 \\ 30414_{(5)} \\ + & 122_{(5)} \\ 31041_{(5)} \end{array}$
と $2$ 回繰り上がっているので $v_{5} (_{2021} C_{37}) = 2$ がわかる。

　これは最初に挙げた問題の(2)に有効です。具体的には $a, b$ の $2$ 進数表示を
$\begin{aligned} a & = a_{d} a_{d - 1} \dots a_{1} a_{0}_{(2)} \\ b & = b_{d} b_{d - 1} \dots b_{1} b_{0}_{(2)} \end{aligned}$
とおくと $4 a + 1, 4 b + 1$ の $2$ 進数表示はそれぞれ
$\begin{aligned} 4 a + 1 & = 100 a + 1_{(2)} = a_{d} a_{d - 1} \dots a_{1} a_{0} 01_{(2)} \\ 4 b + 1 & = 100 b + 1_{(2)} = b_{d} b_{d - 1} \dots b_{1} b_{0} 01_{(2)} \end{aligned}$
となるので $2$ 進数での足し算 $(a - b) + b$ と $4 (a - b) + (4 b + 1)$ における繰り上がりの回数は等しく、Kummerの定理から $v_{2} (_{4 a + 1} C_{4 b + 1}) = v_{2} (_{a} C_{b}) = k$ が言え、
$K = \frac{_{a} C_{b}}{2^{k}}, L = \frac{_{4 a + 1} C_{4 b + 1}}{2^{k}}$
について $K \cdot_{4 a + 1} C_{4 b + 1} = L \cdot_{a} C_{b}$ が成り立つ。といった具合に示せます。
　次に一般化Lucasの定理を紹介しますが、その前に特殊な階乗を定義しておきます。

　素数 $p$ と非負整数 $n$ に対し $n!_{p}$ を
$n!_{p} = \prod_{\begin{matrix} k = 1 \\ p ∤ k \end{matrix}}^{n} k$
と定める(ただし $0!_{p} = 1$ とする)。このとき
$n!_{p} = \frac{\prod_{k = 1}^{n} k}{\prod_{p | k} k} = \frac{n!}{\prod_{j = 1}^{⌊ n / p ⌋} p j} = \frac{n!}{p^{⌊ n / p ⌋} (⌊ n / p ⌋)!}$
とも表せることに注意する。

一般化Lucasの定理

　 $N_{i}$ を $n$ の $p$ 進数表示における(下から) $i + 1$ から $i + e$ 桁目まで抜き出したもの、つまり
$N_{i} = n_{i + e - 1} \dots n_{i + 1} n_{i}_{(p)}$
とおく。 $m, l$ についても同様に $M_{i}, L_{i}$ を定める。また $k_{j}, δ_{p^{e}}$ を
$k_{j} = \sum_{i = j}^{d - 1} ε_{i}, δ_{p^{e}} = {\begin{array}{cl} 1 & if p^{e} = 2^{e} \geq 2^{3} \\ - 1 & otherwise \end{array}$
と定める。このとき
$\frac{_{n} C_{m}}{p^{k_{0}}} \equiv δ_{p^{e}}^{k_{e - 1}} (\frac{(N_{d})!_{p}}{(M_{d})!_{p} (L_{d})!_{p}}) \dots (\frac{(N_{1})!_{p}}{(M_{1})!_{p} (L_{1})!_{p}}) (\frac{(N_{0})!_{p}}{(M_{0})!_{p} (L_{0})!_{p}}) (\mod p^{e})$
が成り立つ。

　一般化Lucasの定理を $e = 1$ のときに適応すると
$\frac{_{n} C_{m}}{p^{k_{0}}} \equiv (- 1)^{k_{0}} \prod_{i = 1}^{d} \frac{(n_{i})!}{(m_{i})! (l_{i})!} (\mod p)$
となり、特に全ての $i$ に対し $n_{i} \geq m_{i}$ ならば $k_{0} = 0$ であり $l_{i} = n_{i} - m_{i}$ なので
$_{n} C_{m} \equiv \prod_{i = 1}^{d}_{n_{i}} C_{m_{i}} (\mod p)$
とLucasの定理を得る。

　例えば $\frac{_{2021} C_{37}}{5^{2}}$ を $5^{2}$ で割った余りを考えてみよう。このとき
$n = 2021 = 31041_{(5)}, m = 37 = 122_{(5)}, l = 2021 - 37 = 30414_{(5)}$
および $δ_{5^{2}} = - 1, k_{2 - 1} = 1$ なので(都合、進数表記 $_{(n)}$ は等号の右下に記す)
$\begin{array}{rcl} \frac{_{2021} C_{37}}{5^{2}} & \equiv_{(5)} & (- 1)^{1} (\frac{(03)!_{5}}{(00)!_{5} (03)!_{5}}) (\frac{(31)!_{5}}{(00)!_{5} (30)!_{5}}) (\frac{(10)!_{5}}{(01)!_{5} (04)!_{5}}) (\frac{(04)!_{5}}{(12)!_{5} (41)!_{5}}) (\frac{(41)!_{5}}{(22)!_{5} (14)!_{5}}) \\ =_{(5)} & - 1 \cdot 1 \cdot 31 \cdot 1 \cdot \frac{(04)!_{5}}{(12)!_{5} (22)!_{5} (14)!_{5}} \\ =_{(10)} & - 16 \cdot 4! \cdot \frac{5 \cdot (5 \cdot 10) \cdot 5}{7! 12! 9!} (\mod 25) \\ \equiv_{(10)} & 9 \cdot 4! \cdot \frac{1}{(4!)^{3} (6 \cdot 7) (6 \cdot 7 \cdot 8 \cdot 9 \cdot 11 \cdot 12) (6 \cdot 7 \cdot 8 \cdot 9)} \\ \equiv_{(10)} & \frac{1}{42 (84 \cdot 48 \cdot 99) (48 \cdot 7)} \\ \equiv_{(10)} & \frac{1}{(- 8) (- 16 \cdot 2 \cdot 1) (- 2 \cdot 7)} \\ =_{(10)} & 2^{10 - 9} \cdot \frac{7}{49} \equiv - 14 \equiv 11 (\mod 25) \end{array}$
(途中 $4! = 24 \equiv - 1 (\mod 25)$ であることや $2^{10} = 1024 \equiv - 1 (\mod 25)$ であることを用いた。)
のように $\frac{_{2021} C_{37}}{5^{2}}$ を $5^{2}$ で割った余りは $11$ であることがわかる。

　これは(3)に有効です。具体的には $v_{2} (_{4 a + 1} C_{4 b + 1}) = v_{2} (_{a} C_{b}) = k_{0}$ および
$\begin{aligned} c & = a - b = c_{d} c_{d - 1} \dots c_{1} c_{0} \\ A_{i} & = a_{i + 1} a_{i}_{(2)}, B_{i} = b_{i + 1} b_{i}_{(2)}, C_{i} = c_{i + 1} c_{i}_{(2)} \end{aligned}$
とおくと一般化Lucasの定理より
$\begin{array}{rcl} \frac{_{4 a + 1} C_{4 b + 1}}{2^{k_{0}}} & \equiv & (- 1)^{k_{0}} (\prod_{i = 0}^{d} \frac{(A_{i})!_{2}}{(B_{i})!_{2} (C_{i})!_{2}}) \frac{(a_{0} 0)!_{2}}{(b_{0} 0)!_{2} (c_{0} 0)!_{2}} \cdot \frac{(01)!_{2}}{(01)!_{2} (00)!_{2}} \\ \equiv & (- 1)^{k_{0} - k_{1}} \cdot \frac{_{a} C_{b}}{2^{k_{0}}} \cdot 1 \cdot 1 (\mod 2^{2}) \\ = & {\begin{array}{cl} \frac{_{a} C_{b}}{2^{k_{0}}} & if a_{0} \geq b_{0} \\ - \frac{_{a} C_{b}}{2^{k_{0}}} & if a_{0} < b_{0} \end{array} \end{array}$
が成り立ち、 $a - b \equiv 0 (\mod 2)$ のとき $a_{0} = b_{0}$ であるので
$\frac{_{4 a + 1} C_{4 b + 1}}{2^{k_{0}}} \equiv \frac{_{a} C_{b}}{2^{k_{0}}} (\mod 4)$
ひいては
$_{4 a + 1} C_{4 b + 1} \equiv_{a} C_{b} (\mod 4)$
を得る。といった具合に示せます。

証明

Kummerの定理

Legendreの公式

$v_{p} (n!) = \frac{n - \sum_{i = 1}^{d} n_{i}}{p - 1}$ が成り立つ。

$n = \sum_{i = 1}^{d} n_{i} p^{i}$
より
$⌊ \frac{n}{p^{j}} ⌋ = \sum_{i = j}^{d} n_{i} p^{i - j}$
が成り立つので通常のLegendreの公式から
$v_{p} (n!) = \sum_{j = 1}^{d} ⌊ \frac{n}{p^{j}} ⌋ = \sum_{i = 1}^{d} n_{i} \sum_{j = 1}^{i} p^{i - j} = \frac{\sum_{i = 1}^{d} n_{i} (p^{i} - 1)}{p - 1} = \frac{n - \sum_{i = 1}^{d} n_{i}}{p - 1}$
を得る。

Kummerの定理の証明

　いま $n = m + l$ および $ε_{i}$ の取り方から
$n_{0} = m_{0} + l_{0} - p ε_{0}, n_{i} = m_{i} + l_{i} + ε_{i - 1} - p ε_{i} (i \geq 1)$
が成り立つので( $n_{d + 1} = ε_{d} = 0$ に注意すると)
$\begin{array}{rcl} v_{p} (_{n} C_{m}) & = & v_{p} (\frac{n!}{m! l!}) \\ = & v_{p} (n!) - v_{p} (m!) - v_{p} (l!) \\ = & \frac{\sum_{i = 0}^{d} (- n_{i} + m_{i} + l_{i})}{p - 1} \\ = & \frac{p ε_{0} + \sum_{i = 1}^{d} (p ε_{i} - ε_{i - 1})}{p - 1} \\ = & \frac{(p - 1) \sum_{i = 0}^{d - 1} ε_{i}}{p - 1} = \sum_{i = 0}^{d - 1} ε_{i} \end{array}$
を得る。

一般化Lucasの定理

$⌊ \frac{n}{p^{j}} ⌋ - ⌊ \frac{m}{p^{j}} ⌋ - ⌊ \frac{l}{p^{j}} ⌋ = ε_{j - 1}$ が成り立つ。

$\begin{array}{rcl} ⌊ \frac{n}{p^{j}} ⌋ - ⌊ \frac{m}{p^{j}} ⌋ - ⌊ \frac{l}{p^{j}} ⌋ & = & \sum_{i = j}^{d} (n_{i} - m_{i} - l_{i}) p^{i - j} \\ = & \sum_{i = j}^{d} (ε_{i - 1} - p ε_{i}) p^{i - j} \\ = & ε_{j - 1} + \sum_{i = j + 1}^{d} ε_{i - 1} p^{i - j} - \sum_{i = j}^{d - 1} ε_{i} p^{i - j + 1} \\ = & ε_{j - 1} \end{array}$
と主張を得る。

一般化Wilsonの定理

$(p^{e})!_{p} \equiv δ_{p^{e}} (\mod p^{e})$ が成り立つ。

$(p^{e})!_{p} \equiv \prod_{x \in (Z / p^{e} Z)^{\times}} x (\mod p^{e})$
の各因子 $x$ について $x ≢ x^{- 1} (\mod p^{e})$ すなわち $x^{2} ≢ 1 (\mod p^{e})$ であれば $x$ に対応する因子 $x^{- 1}$ と打ち消し合って $1$ になるので
$\prod_{x \in (Z / p^{e} Z)^{\times}} x \equiv \prod_{x^{2} \equiv 1} x (\mod p^{e})$
であって、この記事でも紹介したように合同方程式 $x^{2} \equiv 1 (\mod p^{e})$ の解は
$x \equiv {\begin{cases} 1 \equiv - 1 & if p^{e} = 2 \\ \pm 1, 2^{e - 1} \pm 1 & if p^{e} = 2^{e} \geq 2^{3} \\ \pm 1 & otherwise \end{cases} (\mod p^{e})$
で尽くされるので
$\prod_{x^{2} \equiv 1} x \equiv {\begin{cases} - (2^{e - 1} - 1) (2^{e - 1} + 1) \equiv 1 & if p^{e} = 2^{e} \geq 2^{3} \\ - 1 & otherwise \end{cases}} = δ_{p^{e}} (\mod p^{e})$
を得る。

$n!_{p} = δ_{p^{e}}^{⌊ \frac{n}{p^{e}} ⌋} (N_{0})!_{p} (\mod p^{e})$ が成り立つ。

$\begin{array}{rcl} n!_{p} & = & \prod_{\begin{array}{c} k = 1 \\ p ∤ k \end{array}}^{n} k \\ = & (\prod_{i = 0}^{⌊ \frac{n}{p^{e}} ⌋ - 1} \prod_{\begin{array}{c} j = 1 \\ p ∤ j \end{array}}^{p^{e}} (i p^{e} + j)) \prod_{\begin{array}{c} j = 1 \\ p ∤ j \end{array}}^{N_{0}} (⌊ \frac{n}{p^{e}} ⌋ p^{e} + j) \\ \equiv & ((p^{e})!_{p})^{⌊ \frac{n}{p^{e}} ⌋} (N_{0})!_{p} \\ \equiv & δ_{p^{e}}^{⌊ \frac{n}{p^{e}} ⌋} (N_{0})!_{p} (\mod p^{e}) \end{array}$
と主張を得る。

一般化Lucasの定理の証明

$n!_{p} = \frac{n!}{(⌊ \frac{n}{p} ⌋)! p^{⌊ \frac{n}{p} ⌋}}$
および通常のLegendreの公式より
$\frac{n!}{p^{v_{p} (n!)}} = \frac{(⌊ \frac{n}{p^{0}} ⌋)!}{p^{\sum_{j = 0}^{d} ⌊ \frac{n}{p^{j}} ⌋} (⌊ \frac{n}{p^{d + 1}} ⌋)!} = \prod_{j = 0}^{d} \frac{(⌊ \frac{n}{p^{j}} ⌋)!}{p^{⌊ \frac{n}{p^{j}} ⌋} (⌊ \frac{n}{p^{j + 1}} ⌋)!} = \prod_{j = 0}^{d} (⌊ \frac{n}{p^{j}} ⌋)!_{p}$
と変形できるので補題7より
$\frac{n!}{p^{v_{p} (n!)}} = \prod_{j = 0}^{d} (⌊ \frac{n}{p^{j}} ⌋)!_{p} \equiv \prod_{j = 0}^{d} δ_{p^{e}}^{⌊ \frac{n}{p^{e + j}} ⌋} (N_{j})!_{p} (\mod p^{e})$
であり補題5より
$\begin{array}{rcl} \frac{_{n} C_{m}}{p^{k_{0}}} & = & \frac{n!}{p^{v_{p} (n!)}} \cdot \frac{p^{v_{p} (m!)}}{m!} \cdot \frac{p^{v_{p} (l!)}}{l!} \\ \equiv & \prod_{j = 0}^{d} (δ_{p^{e}}^{⌊ \frac{n}{p^{e + j}} ⌋ - ⌊ \frac{m}{p^{e + j}} ⌋ - ⌊ \frac{l}{p^{e + j}} ⌋}) \prod_{j = 0}^{d} \frac{(N_{j})!_{p}}{(M_{j})!_{p} (L_{j})!_{p}} (\mod p^{e}) \\ = & δ_{p^{e}}^{\sum_{j = 0}^{d} ε_{j + e - 1}} \prod_{j = 0}^{d} \frac{(N_{j})!_{p}}{(M_{j})!_{p} (L_{j})!_{p}} \\ = & δ_{p^{e}}^{k_{e - 1}} \prod_{j = 0}^{d} \frac{(N_{j})!_{p}}{(M_{j})!_{p} (L_{j})!_{p}} \end{array}$
を得る。