高校数学解説

文献あり

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

二項係数,Lucasの定理

1014

はじめに

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

　以下の問いに答えよ。

正の奇数 $K, L$ と正の整数 $A, B$ が $K A = L B$ を満たしているとする。 $K$ を $4$ で割った余りが $L$ を $4$ で割った余りと等しいならば、 $A$ を $4$ で割った余りは $B$ を $4$ で割った余りと等しいことを示せ。
正の整数 $a, b$ が $a > b$ を満たしているとする。このとき、 $A =_{4 a + 1} C_{4 b + 1}, B =_{a} C_{b}$ に対して $K A = L B$ となるような正の奇数 $K, L$ が存在することを示せ。
$a, b$ は(2)の通りとし、さらに $a - b$ が $2$ で割り切れるとする。 $_{4 a + 1} C_{4 b + 1}$ を $4$ で割った余りは $_{a} C_{b}$ を $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{aligned} 1 & if p^{e} = 2^{e} \geq 2^{3} \\ - 1 & otherwise \end{aligned}$
と定める。このとき
$\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}} \cdot \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} \cdot \frac{(03)!_{5}}{(00)!_{5} (03)!_{5}} \cdot \frac{(31)!_{5}}{(00)!_{5} (30)!_{5}} \cdot \frac{(10)!_{5}}{(01)!_{5} (04)!_{5}} \cdot \frac{(04)!_{5}}{(12)!_{5} (41)!_{5}} \cdot \frac{(41)!_{5}}{(22)!_{5} (14)!_{5}} \\ =_{(5)} & - 1 \cdot 1 \cdot 31_{(5)} \cdot 1 \cdot \frac{(04)!_{5}}{(12)!_{5} (22)!_{5} (14)!_{5}} \\ =_{(10)} & - 16 \cdot \frac{4!}{\frac{7!}{5} \cdot \frac{12!}{5 \cdot 10} \cdot \frac{9!}{5}} \\ \equiv_{(10)} & 9 \cdot \frac{4!}{(4!)^{3}} \cdot \frac{1}{(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)} & - \frac{1}{2^{9}} \cdot \frac{7}{49} \equiv 2 \cdot (- 7) \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{aligned} \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{aligned} \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の定理(再掲)

$v_{p} (_{n} C_{m}) = \sum_{i = 0}^{d - 1} ε_{i}$ が成り立つ。

　いま $n = m + l$ および $ε_{i}$ の取り方から
$\begin{aligned} n_{0} & = m_{0} + l_{0} - p ε_{0} \\ n_{i} & = m_{i} + l_{i} + ε_{i - 1} - p ε_{i} (i \geq 1) \end{aligned}$
が成り立つので( $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}}^{⌊ n / p^{e} ⌋} (N_{0})!_{p} (\mod p^{e})$ が成り立つ。

$\begin{aligned} n!_{p} & = (\prod_{i = 0}^{⌊ n / p^{e} ⌋ - 1} \frac{((i + 1) p^{e})!_{p}}{(i p^{e})!_{p}}) \frac{n!_{p}}{(n - N_{0})!_{p}} \\ \equiv ((p^{e})!_{p})^{⌊ n / p^{e} ⌋} (N_{0})!_{p} \\ \equiv δ_{p^{e}}^{⌊ n / p^{e} ⌋} (N_{0})!_{p} (\mod p^{e}) \end{aligned}$
とわかる。

　 $(⌊ n / p^{e - 1} ⌋)!$ の素因数分解における $p$ の指数を $v^{'} = \sum_{j = e}^{d} ⌊ n / p^{j} ⌋$ とおくと
$\frac{n!}{p^{v_{p} (n!)}} \equiv δ_{p^{e}}^{v^{'}} \prod_{j = 0}^{d} (N_{j})!_{p} (\mod p^{e})$
が成り立つ。

$n!_{p} = \frac{n!}{p^{⌊ n / p ⌋} (⌊ n / p ⌋)!}$
であったことおよび通常のLegendreの公式より
$\begin{aligned} \frac{n!}{p^{v_{p} (n!)}} & = \frac{(⌊ n / p^{0} ⌋)!}{p^{\sum_{j = 0}^{d} ⌊ n / p^{j} ⌋} (⌊ n / p^{d + 1} ⌋)!} \\ = \prod_{j = 0}^{d} \frac{(⌊ n / p^{j} ⌋)!}{p^{⌊ n / p^{j} ⌋} (⌊ n / p^{j + 1} ⌋)!} \\ = \prod_{j = 0}^{d} (⌊ \frac{n}{p^{j}} ⌋)!_{p} \end{aligned}$
と変形できるので補題8より
$\frac{n!}{p^{v_{p} (n!)}} \equiv \prod_{j = 0}^{d} δ_{p^{e}}^{⌊ \frac{n}{p^{e + j}} ⌋} (N_{j})!_{p} = δ_{p^{e}}^{v^{'}} \prod_{j = 0}^{d} (N_{j})!_{p} (\mod p^{e})$
を得る。

一般化Lucasの定理(再掲)

$\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}} \cdot \frac{(N_{0})!_{p}}{(M_{0})!_{p} (L_{0})!_{p}} (\mod p^{e})$
が成り立つ。

　補題6より
$\begin{aligned} \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 δ_{p^{e}}^{\sum_{j = e}^{d} (⌊ \frac{n}{p^{j}} ⌋ - ⌊ \frac{m}{p^{j}} ⌋ - ⌊ \frac{l}{p^{j}} ⌋)} \prod_{j = 0}^{d} \frac{(N_{j})!_{p}}{(M_{j})!_{p} (L_{j})!_{p}} (\mod p^{e}) \\ = δ_{p^{e}}^{\sum_{j = e}^{d} ε_{j - 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{aligned}$
を得る。

おまけ

　定理9として紹介したように一般化Lucasの定理より強い主張として、 $v^{'} = \sum_{j = e}^{d} ⌊ n / p^{j} ⌋$ とおいたとき
$\frac{n!}{p^{v_{p} (n!)}} \equiv δ_{p^{e}}^{v} \prod_{j = 0}^{d} (N_{j})!_{p} (\mod p^{e})$
という公式が成り立つのでした。
　これを使うと例えば以下のようなことが言えたりします。

　奇素数 $p$ と非負整数 $n$ に対し、 $n$ の $p$ 進数表示を
$n = n_{d} n_{d - 1} \dots n_{1} n_{0}_{(p)}$
とおくと
$\frac{n!}{p^{v_{p} (n!)}} \equiv (- 1)^{v_{p} (n!)} n_{d}! n_{d - 1}! \dots n_{1}! n_{0}! (\mod p)$
が成り立つ。

　 $(10^{14})!$ の $0$ でない部分の下二桁、つまり
$\frac{(10^{14})!}{10^{v_{5} ((10^{14})!)}} (\mod 100)$
を求めたい。
　いま
$10^{14} = 16384 \cdot 5^{14} = 1011014_{(5)} \cdot 10_{(5)}^{14}$
より
$\begin{aligned} v & = \frac{10^{14} - (1 + 1 + 1 + 1 + 4)}{4} = 25 \cdot 10^{12} - 2 \\ v^{'} & = \frac{\frac{10^{14}}{5} - (1 + 1 + 1 + 1 + 4)}{4} = 5 \cdot 10^{12} - 2 \end{aligned}$
とおくと
$\begin{aligned} \frac{(10^{14})!}{5^{v}} & \equiv_{(5)} (- 1)^{v^{'}} (01)!_{5} (10)!_{5} (01)!_{5} (11)!_{5} (10)!_{5} (01)!_{5} (14)!_{5} (40)!_{5} (\mod 25) \\ =_{(10)} 1 \cdot 1 \cdot 4! \cdot 1 \cdot (6 \cdot 4!) \cdot 4! \cdot 1 \cdot (9 \cdot 8 \cdot 7 \cdot 6 \cdot 4!) \cdot (25!_{5} / 24 \cdot 23 \cdot 22 \cdot 21) \\ \equiv_{(10)} (4!)^{4} \cdot 25!_{5} \cdot 36 / 23 \cdot 22 \\ \equiv_{(10)} - 36 / (- 2) \cdot (- 3) = 6 (\mod 25) \end{aligned}$
が成り立つので $2^{20} \equiv 1 (\mod 25)$ に注意すると
$\frac{(10^{14})!}{10^{v}} \equiv - 6 \cdot 2^{- v} \equiv - 6 \cdot 2^{2} \equiv 1 (\mod 25)$
つまり、明らかに $(10^{14})! / 10^{v} \equiv 0 (\mod 4)$ であること合わせると
$\frac{(10^{14})!}{10^{v}} \equiv 76 (\mod 100)$
を得る。

追記：計算の簡略化

　いくつかの例からもわかるように一般化Lucasの定理を使っても法 $p^{e}$ の指数が高くなるほどその手計算はダルくなっていくわけですが、法 $p^{3}$ 程度であればウォルステンホルムの定理を使うことで幾ばくか計算を楽にできることに気付いたのでそのことについて簡単に紹介していきます。
　以下 $p \geq 5$ とします。

ウォルステンホルムの定理

$\sum_{k = 1}^{p - 1} \frac{1}{k} \equiv 0 (\mod p^{2})$

$\begin{aligned} \sum_{k = 1}^{p - 1} \frac{1}{k} & = \frac{1}{2} \sum_{k = 1}^{p - 1} (\frac{1}{k} + \frac{1}{p - k}) = \frac{p}{2} \sum_{k = 1}^{p - 1} \frac{1}{k (p - k)} \\ \equiv - \frac{p}{2} \sum_{k = 1}^{p - 1} \frac{1}{k^{2}} \equiv - \frac{p}{2} \sum_{k = 1}^{p - 1} k^{2} \\ \equiv - p^{2} \frac{(p - 1) (2 p - 1)}{12} \equiv 0 (\mod p^{2}) \end{aligned}$
とわかる。

$\sum_{1 \leq i < j < p} \frac{1}{i j} \equiv 0 (\mod p)$

${(\sum_{k = 1}^{p - 1} \frac{1}{k})}^{2} = \sum_{k = 1}^{p - 1} \frac{1}{k^{2}} + 2 \sum_{1 \leq i < j < p} \frac{1}{i j}$
に注意すると
$\begin{aligned} 2 \sum_{1 \leq i < j < p} \frac{1}{i j} & \equiv {(\sum_{k = 1}^{p - 1} k)}^{2} - \sum_{k = 1}^{p - 1} k^{2} \\ = \frac{p^{2} (p - 1)^{2}}{4} - \frac{p (p - 1) (2 p - 1)}{6} \\ = \frac{p (p - 1) (p - 2) (3 p - 1)}{12} \\ \equiv 0 (\mod p) \end{aligned}$
とわかる。

$_{n p - 1} C_{p - 1} \equiv 1 (\mod p^{3})$

$\begin{aligned} _{x - 1} C_{p - 1} & = \frac{(x - 1) (x - 2) \dots (x - (p - 1))}{(p - 1)!} \\ = (1 - x) (1 - \frac{x}{2}) \dots (1 - \frac{x}{p - 1}) \\ = 1 - (\sum_{k = 1}^{p - 1} \frac{1}{k}) x + (\sum_{1 \leq i < j < p} \frac{1}{i j}) x^{2} - \dots \end{aligned}$
と展開できることに注意すると補題11,12から
$\begin{aligned} _{n p - 1} C_{p - 1} & \equiv 1 - (\sum_{k = 1}^{p - 1} \frac{1}{k}) n p + (\sum_{1 \leq i < j < p} \frac{1}{i j}) (n p)^{2} \\ \equiv 1 (\mod p^{3}) \end{aligned}$
を得る。

　素数 $p$ と非負整数 $n$ に対し
$n!_{p}^{'} = \frac{n!}{(n - n_{0})!}$
と定める。ただし $n_{0}$ は $n$ の $p$ 進数表示における下一桁とした。
　特に $p \geq 5$ および $n_{0} = p - 1$ のとき
$n!_{p}^{'} \equiv (p - 1)! (\mod p^{3})$
が成り立つことに注意する。

　 $p \geq 5$ において
$n!_{p} \equiv ((p - 1)!)^{⌊ n / p ⌋} n!_{p}^{'} (\mod p^{3})$
が成り立つ。

$\begin{aligned} n!_{p} & = (\prod_{i = 0}^{⌊ n / p ⌋ - 1} \frac{((i + 1) p)!_{p}}{(i p)!_{p}}) \frac{n!_{p}}{(n - n_{0})!_{p}} \\ = (\prod_{i = 0}^{⌊ n / p ⌋ - 1}_{(i + 1) p - 1} C_{p - 1}) ((p - 1)!)^{⌊ n / p ⌋} \frac{n!}{(n - n_{0})!} \\ \equiv ((p - 1)!)^{⌊ n / p ⌋} \frac{n!}{(n - n_{0})!} (\mod p^{3}) \end{aligned}$
とわかる。

　 $p \geq 5$ および $e \leq 3$ において
$\frac{n!}{p^{v_{p} (n!)}} \equiv ((p - 1)!)^{v_{p} (n!)} \prod_{j = 0}^{d} (N_{j})!_{p}^{'} (\mod p^{e})$
が成り立つ。

　定理9の証明から
$\frac{n!}{p^{v_{p} (n!)}} = \prod_{j = 0}^{d} (⌊ \frac{n}{p^{j}} ⌋)!_{p}$
が成り立っていたので定理14から
$\begin{aligned} \frac{n!}{p^{v_{p} (n!)}} & \equiv \prod_{j = 0}^{d} ((p - 1)!)^{⌊ n / p^{j + 1} ⌋} (⌊ \frac{n}{p^{j}} ⌋)!_{p}^{'} \\ \equiv ((p - 1)!)^{v_{p} (n!)} \prod_{j = 0}^{d} (N_{j})!_{p}^{'} (\mod p^{e}) \end{aligned}$
を得る。

　 $p \geq 5$ および $e \leq 3$ において
$\frac{_{n} C_{m}}{p^{k_{0}}} \equiv ((p - 1)!)^{k_{0}} \prod_{j = 0}^{d} \frac{(N_{j})!_{p}^{'}}{(M_{j})!_{p}^{'} (L_{j})!_{p}^{'}} (\mod p^{e})$
が成り立つ。

　例えば例3の計算は
$\begin{aligned} \frac{_{2021} C_{37}}{5^{2}} & \equiv_{(5)} 4!^{2} \cdot \frac{(03)!_{5}^{'}}{(00)!_{5}^{'} (03)!_{5}^{'}} \cdot \frac{(31)!_{5}^{'}}{(00)!_{5}^{'} (30)!_{5}^{'}} \cdot \frac{(10)!_{5}^{'}}{(01)!_{5}^{'} (04)!_{5}^{'}} \cdot \frac{(04)!_{5}^{'}}{(12)!_{5}^{'} (41)!_{5}^{'}} \cdot \frac{(41)!_{5}^{'}}{(22)!_{5}^{'} (14)!_{5}^{'}} \\ =_{(10)} 4!^{2} \cdot 1 \cdot 16 \cdot \frac{1}{4!} \cdot \frac{4!}{7!_{5}^{'} 12!_{5}^{'} 9!_{5}^{'}} \\ \equiv_{(10)} - 16 \frac{4!}{(7 \cdot 6) \cdot (11 \cdot 12) \cdot 4!} = - \frac{2 \cdot 7}{49 \cdot 99} \\ \equiv_{(10)} 11 (\mod 25) \end{aligned}$
と簡略化できる。

　また例えば例5の計算は
$\begin{aligned} \frac{(10^{14})!}{5^{v}} & \equiv_{(5)} 4!^{v} \cdot (01)!_{5}^{'} (10)!_{5}^{'} (01)!_{5}^{'} (11)!_{5}^{'} (10)!_{5}^{'} (01)!_{5}^{'} (14)!_{5}^{'} (40)!_{5}^{'} \\ =_{(10)} 4!^{v} \cdot 6 \cdot 9!_{5}^{'} \\ \equiv_{(10)} 1 \cdot 6 \cdot 4! \equiv - 6 (\mod 25) \end{aligned}$
と簡略化できる。

　ちなみに $p = 3$ の場合も
$\sum_{k = 1}^{2} \frac{1}{k} = \frac{3}{2} \equiv 0 (\mod 3)$
は成り立つので、上と同様の議論によって
$_{3 n - 1} C_{2} \equiv 1 (\mod 9)$
や
$\begin{aligned} \frac{n!}{3^{v_{3} (n!)}} & \equiv 2^{v_{3} (n!)} \prod_{j = 0}^{d} (N_{j})!_{3}^{'} (\mod 9) \\ \frac{_{n} C_{m}}{3^{k_{0}}} & \equiv 2^{k_{0}} \prod_{j = 0}^{d} \frac{(N_{j})!_{3}^{'}}{(M_{j})!_{3}^{'} (L_{j})!_{3}^{'}} (\mod 9) \end{aligned}$
が成り立ちます。