2
高校数学解説
文献あり

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

708
0
$$\newcommand{a}[0]{\alpha} \newcommand{b}[2]{{}_{#1}C_{#2}} \newcommand{c}[0]{\cdot} \newcommand{C}[0]{\mathbb{C}} \newcommand{d}[0]{\delta} \newcommand{dis}[0]{\displaystyle} \newcommand{e}[0]{\varepsilon} \newcommand{eq}[0]{\equiv} \newcommand{farc}[2]{\frac{#1}{#2}} \newcommand{g}[0]{\gamma} \newcommand{Gal}[0]{\mathrm{Gal}} \newcommand{id}[0]{\mathrm{id}} \newcommand{if}[0]{\mathrm{if}\;} \newcommand{Im}[0]{\mathrm{Im}} \newcommand{Ker}[0]{\mathrm{Ker}} \newcommand{l}[0]{\left} \newcommand{ndiv}[0]{\nmid} \newcommand{ol}[1]{\overline{#1}} \newcommand{ord}[0]{\mathrm{ord}} \newcommand{prime}[0]{\mathrm{prime}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{r}[0]{\right} \newcommand{R}[0]{\mathbb{R}} \newcommand{Re}[0]{\mathrm{Re}} \newcommand{resp}[0]{\mathrm{resp}} \newcommand{s}[0]{\sigma} \newcommand{s}[1]{\left\lfloor #1\right\rfloor} \newcommand{ul}[1]{\underline{#1}} \newcommand{Z}[0]{\mathbb{Z}} \newcommand{z}[0]{\zeta} \newcommand{ZZ}[1]{\mathbb{Z}/{#1}\mathbb{Z}} \newcommand{ZZt}[1]{(\mathbb{Z}/{#1}\mathbb{Z})^\times} $$

はじめに

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

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

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

Lucasの定理

 素数$p$と非負整数$n,m$に対して$n,m$$p$進数表示を
\begin{align} n&=n_dn_{d-1}\cdots n_1n_0\;{}_{(p)}&&(=n_dp^d+n_{d-1}p^{d-1}+\cdots+n_1p+n_0)\\ m&=m_dm_{d-1}\cdots m_1m_0\;{}_{(p)}&&(=m_dp^d+m_{d-1}p^{d-1}+\cdots+n_1p+m_0) \end{align}
とおくと
$${}_nC_m\eq{}_{n_d}C_{m_d}\cdot{}_{n_{d-1}}C_{m_{d-1}}\cdots{}_{n_1}C_{m_1}\cdot{}_{n_0}C_{m_0}\pmod{p}$$
が成り立つ。ただし$n< m$に対しては${}_nC_m=0$と定める。

 しかしLucasの定理からわかるのは
$${}_{4a+1}C_{4b+1}\equiv{}_aC_b\c\b00\c\b11={}_aC_b\pmod{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{eqnarray} n&=&n_dn_{d-1}\cdots n_1n_0\;{}_{(p)} \\m&=&m_dm_{d-1}\cdots m_1m_0\;{}_{(p)} \\l&=&l_dl_{d-1}\cdots l_1l_0\;{}_{(p)} \end{eqnarray}
とおき、$\e_i$$p$進数における足し算$m+l$の各桁について$m_i+l_i+\e_{i-1}$が繰り上がるとき(つまり$m_i+l_i+\e_{i-1}\geq p$のとき)$\e_i=1$、繰り上がらないとき($m_i+l_i+\e_{i-1}< p$のとき)$\e_i=0$と定める。

Kummerの定理

 $\b{n}{m}$の素因数分解における素因数$p$の指数$v_p(\b nm)$$p$進数での足し算$m+l\;(=n)$における繰り上がりの回数$\sum^{d-1}_{i=0}\e_i$に等しい。

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

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

 素数$p$と非負整数$n$に対し$n!_p$
$$n!_p=\prod^n_{\substack{k=1\\p\nmid k}}k$$
と定める(ただし$0!_p=1$とする)。このとき
$$n!_p=\frac{\prod^n_{k=1}k}{\prod_{p|k}k} =\frac{n!}{\prod^{\s{n/p}}_{j=1}pj} =\frac{n!}{p^{\s{n/p}}(\s{n/p})!}$$
とも表せることに注意する。

一般化Lucasの定理

 $N_i$$n$$p$進数表示における(下から)$i+1$から$i+e$桁目まで抜き出したもの、つまり
$$N_i=n_{i+e-1}\cdots n_{i+1}n_i\;{}_{(p)}$$
とおく。$m,l$についても同様に$M_i,L_i$を定める。また$k_j,\;\d_{p^e}$
$$k_j=\sum^{d-1}_{i=j}\e_i,\quad\d_{p^e}=\left\{\begin{array}{cl}1&\if p^e=2^e\geq2^3\\-1&\mathrm{otherwise}\end{array}\right.$$
と定める。このとき
$$\frac{\b nm}{p^{k_0}}\eq\d_{p^e}^{k_{e-1}} \l(\farc{(N_d)!_p}{(M_d)!_p(L_d)!_p}\r) \cdots \l(\farc{(N_1)!_p}{(M_1)!_p(L_1)!_p}\r) \l(\farc{(N_0)!_p}{(M_0)!_p(L_0)!_p}\r)\pmod{p^e}$$
が成り立つ。

 一般化Lucasの定理を$e=1$のときに適応すると
$$\frac{\b nm}{p^{k_0}}\eq(-1)^{k_0}\prod^d_{i=1}\farc{(n_i)!}{(m_i)!(l_i)!}\pmod{p}$$
となり、特に全ての$i$に対し$n_i\geq m_i$ならば$k_0=0$であり$l_i=n_i-m_i$なので
$$\b nm\eq\prod^d_{i=1}\b{n_i}{m_i}\pmod{p}$$
とLucasの定理を得る。

 例えば$\dis\frac{\b{2021}{37}}{5^2}$$5^2$で割った余りを考えてみよう。このとき
$$n=2021=31041_{(5)},\quad m=37=122_{(5)},\quad l=2021-37=30414_{(5)}$$
および$\d_{5^2}=-1,\ k_{2-1}=1$なので(都合、進数表記${}_{(n)}$は等号の右下に記す)
\begin{eqnarray} \frac{\b{2021}{37}}{5^2} &\eq_{(5)}&(-1)^1 \l(\frac{(03)!_5}{(00)!_5(03)!_5}\r) \l(\frac{(31)!_5}{(00)!_5(30)!_5}\r) \l(\frac{(10)!_5}{(01)!_5(04)!_5}\r) \l(\frac{(04)!_5}{(12)!_5(41)!_5}\r) \l(\frac{(41)!_5}{(22)!_5(14)!_5}\r) \\&=_{(5)}&-1\c1\c31\c1\c\frac{(04)!_5}{(12)!_5(22)!_5(14)!_5} \\&=_{(10)}&-16\c4!\c\frac{5\c(5\c10)\c5}{7!12!9!}\pmod{25} \\&\eq_{(10)}&9\c4!\c\frac{1}{(4!)^3(6\c7)(6\c7\c8\c9\c11\c12)(6\c7\c8\c9)} \\&\eq_{(10)}&\frac{1}{42(84\c48\c99)(48\c7)} \\&\eq_{(10)}&\frac{1}{(-8)(-16\c2\c1)(-2\c7)} \\&=_{(10)}&2^{10-9}\c\frac{7}{49} \eq-14\eq11\pmod{25} \end{eqnarray}
(途中$4!=24\equiv-1\pmod{25}$であることや$2^{10}=1024\equiv-1\pmod{25}$であることを用いた。)
のように$\dis\frac{\b{2021}{37}}{5^2}$$5^2$で割った余りは$11$であることがわかる。

 これは(3)に有効です。具体的には$v_2(\b{4a+1}{4b+1})=v_2(\b ab)=k_0$および
\begin{align} c&=a-b=c_dc_{d-1}\cdots c_1c_0\\ A_i&=a_{i+1}a_i\;{}_{(2)},\quad B_i=b_{i+1}b_i\;{}_{(2)},\quad C_i=c_{i+1}c_i\;{}_{(2)} \end{align}
とおくと一般化Lucasの定理より
\begin{eqnarray} \frac{\b{4a+1}{4b+1}}{2^{k_0}} &\eq&(-1)^{k_0}\l(\prod^d_{i=0}\frac{(A_i)!_2}{(B_i)!_2(C_i)!_2}\r) \frac{(a_00)!_2}{(b_00)!_2(c_00)!_2}\c\frac{(01)!_2}{(01)!_2(00)!_2} \\&\eq&(-1)^{k_0-k_1}\c\frac{\b ab}{2^{k_0}}\c1\c1\pmod{2^2} \\&=&\left\{\begin{array}{cl} \dis\frac{\b ab}{2^{k_0}}&\if a_0\geq b_0\\ \dis-\frac{\b ab}{2^{k_0}}&\if a_0< b_0 \end{array}\right. \end{eqnarray}
が成り立ち、$a-b\eq0\pmod{2}$のとき$a_0=b_0$であるので
$$\frac{\b{4a+1}{4b+1}}{2^{k_0}}\eq\frac{\b ab}{2^{k_0}}\pmod{4}$$
ひいては
$$\b{4a+1}{4b+1}\eq\b ab\pmod{4}$$
を得る。といった具合に示せます。

証明

Kummerの定理

Legendreの公式

$\dis v_p(n!)=\frac{n-\sum^d_{i=1}n_i}{p-1}$が成り立つ。

$$n=\sum^d_{i=1}n_ip^i$$
より
$$\s{\frac{n}{p^j}}=\sum^d_{i=j}n_ip^{i-j}$$
が成り立つので通常のLegendreの公式から
$$v_p(n!)=\sum^d_{j=1}\s{\frac{n}{p^j}}=\sum^d_{i=1}n_i\sum^i_{j=1}p^{i-j}=\frac{\sum^d_{i=1}n_i(p^i-1)}{p-1}=\frac{n-\sum^d_{i=1}n_i}{p-1}$$
を得る。

Kummerの定理の証明

 いま$n=m+l$および$\e_i$の取り方から
$$n_0=m_0+l_0-p\e_0,\quad n_i=m_i+l_i+\e_{i-1}-p\e_i\;(i\geq1)$$
が成り立つので($n_{d+1}=\e_d=0$に注意すると)
\begin{eqnarray} v_p(\b nm)&=&v_p\l(\frac{n!}{m!l!}\r) \\&=&v_p(n!)-v_p(m!)-v_p(l!) \\&=&\frac{\sum^d_{i=0}(-n_i+m_i+l_i)}{p-1} \\&=&\frac{p\e_0+\sum^d_{i=1}(p\e_i-\e_{i-1})}{p-1} \\&=&\frac{(p-1)\sum^{d-1}_{i=0}\e_i}{p-1}=\sum^{d-1}_{i=0}\e_i \end{eqnarray}
を得る。

一般化Lucasの定理

$\dis\s{\frac{n}{p^j}}-\s{\frac{m}{p^j}}-\s{\frac{l}{p^j}}=\e_{j-1}$が成り立つ。

\begin{eqnarray} \s{\frac{n}{p^j}}-\s{\frac{m}{p^j}}-\s{\frac{l}{p^j}} &=&\sum^d_{i=j}(n_i-m_i-l_i)p^{i-j} \\&=&\sum^d_{i=j}(\e_{i-1}-p\e_i)p^{i-j} \\&=&\e_{j-1}+\sum^{d}_{i=j+1}\e_{i-1}p^{i-j}-\sum^{d-1}_{i=j}\e_ip^{i-j+1} \\&=&\e_{j-1} \end{eqnarray}
と主張を得る。

一般化Wilsonの定理

$(p^e)!_p\eq\d_{p^e}\pmod{p^e}$が成り立つ。

$$(p^e)!_p\eq\prod_{x\in\ZZt{p^e}}x\pmod{p^e}$$
の各因子$x$について$x\not\eq x^{-1}\pmod{p^e}$すなわち$x^2\not\eq1\pmod{p^e}$であれば$x$に対応する因子$x^{-1}$と打ち消し合って$1$になるので
$$\prod_{x\in\ZZt{p^e}}x\eq\prod_{x^2\eq1}x\pmod{p^e}$$
であって、 この記事 でも紹介したように合同方程式$x^2\eq1\pmod{p^e}$の解は
$$x\eq\left\{\begin{array}{ll} 1\eq-1&\if p^e=2\\ \pm1,2^{e-1}\pm1&\if p^e=2^e\geq2^3\\ \pm1&\mathrm{otherwise} \end{array}\right.\quad\pmod{p^e}$$
で尽くされるので
$$\prod_{x^2\eq1}x\eq\left\{\begin{array}{ll} -(2^{e-1}-1)(2^{e-1}+1)\eq1&\if p^e=2^e\geq2^3\\ -1&\mathrm{otherwise} \end{array}\right\}=\d_{p^e}\pmod{p^e}$$
を得る。

$n!_p=\d_{p^e}^{\s{\frac{n}{p^e}}}(N_0)!_p\pmod{p^e}$が成り立つ。

\begin{eqnarray} n!_p &=&\prod^n_{\substack{k=1\\p\nmid k}}k \\&=& \l(\prod^{\s{\frac{n}{p^e}}-1}_{i=0}\prod^{p^e}_{\substack{j=1\\p\nmid j}}(ip^e+j)\r) \prod^{N_0}_{\substack{j=1\\p\nmid j}}(\s{\frac{n}{p^e}}p^e+j) \\&\eq&\Big((p^e)!_p\Big)^{\s{\frac{n}{p^e}}}(N_0)!_p \\&\eq&\d_{p^e}^{\s{\frac{n}{p^e}}}(N_0)!_p\pmod{p^e} \end{eqnarray}
と主張を得る。

一般化Lucasの定理の証明

$$n!_p=\frac{n!}{(\s{\frac np})!p^{\s{\frac np}}}$$
および通常のLegendreの公式より
$$\frac{n!}{p^{v_p(n!)}} =\frac{(\s{\frac{n}{p^0}})!}{p^{\sum^d_{j=0}\s{\frac{n}{p^j}}}(\s{\frac{n}{p^{d+1}}})!} =\prod^d_{j=0}\frac{(\s{\frac{n}{p^j}})!}{p^{\s{\frac{n}{p^j}}}(\s{\frac{n}{p^{j+1}}})!} =\prod^d_{j=0}(\s{\frac{n}{p^j}})!_p$$
と変形できるので補題7より
$$\frac{n!}{p^{v_p(n!)}}=\prod^d_{j=0}(\s{\frac{n}{p^j}})!_p \eq\prod^d_{j=0}\d_{p^e}^{\s{\frac{n}{p^{e+j}}}}(N_j)!_p\pmod{p^e}$$
であり補題5より
\begin{eqnarray} \frac{\b nm}{p^{k_0}} &=&\frac{n!}{p^{v_p(n!)}}\c\frac{p^{v_p(m!)}}{m!}\c\frac{p^{v_p(l!)}}{l!} \\&\eq&\prod^d_{j=0} \l(\d_{p^e}^{\s{\frac{n}{p^{e+j}}}-\s{\frac{m}{p^{e+j}}}-\s{\frac{l}{p^{e+j}}}}\r) \prod^d_{j=0}\frac{(N_j)!_p}{(M_j)!_p(L_j)!_p}\pmod{p^e} \\&=&\d_{p^e}^{\sum^{d}_{j=0}\e_{j+e-1}}\prod^d_{j=0}\frac{(N_j)!_p}{(M_j)!_p(L_j)!_p} \\&=&\d_{p^e}^{k_{e-1}}\prod^d_{j=0}\frac{(N_j)!_p}{(M_j)!_p(L_j)!_p} \end{eqnarray}
を得る。

参考文献

投稿日:202131
更新日:125

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

子葉
子葉
966
213783
主に複素解析、代数学、数論を学んでおります。 私の経験上、その証明が簡単に探しても見つからない、英語の文献を漁らないと載ってない、なんて定理の解説を主にやっていきます。 同じ経験をしている人の助けになれば。最近は自分用のノートになっている節があります。

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中