二項係数の素因数と合同関係と東大数学2021
はじめに
この記事では今年の東大入試問題を起点に二項係数${}_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)から$\dis{}_{2021}C_{37}\eq{}_{505}C_9\eq{}_{126}C_{2}=63\cdot125\eq3\pmod{4}$
という単純な話ですが気になるのは(2)と(3)です。(2)はひとまず置いておくとして(3)を見て私はまずLucasの定理が頭に浮かびました。
素数$p$と非負整数$n,m$に対して$n,m$の$p$進数表示を
$n=n_dp^d+n_{d-1}p^{d-1}+\cdots+n_1p+n_0=n_dn_{d-1}\cdots n_1n_0\;{}_{(p)}$
$m=m_dp^d+m_{d-1}p^{d-1}+\cdots+n_1p+m_0=m_dm_{d-1}\cdots m_1m_0\;{}_{(p)}$
とおくと
${}_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$と定める。
$\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$進数表示を
$a=a_da_{d-1}\cdots a_1a_0\;{}_{(2)}$
$b=b_db_{d-1}\cdots b_1b_0\;{}_{(2)}$
とおくと$4a+1,4b+1$の$2$進数表示はそれぞれ
$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)}$
となるので$2$進数での足し算$(a-b)+b$と$4(a-b)+(4b+1)$における繰り上がりの回数は等しく、Kummerの定理から$v_2(\b{4a+1}{4b+1})=v_2(\b ab)=k$が言え、
$\dis 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$を$\dis n!_p=\prod^n_{\substack{k=1\\p\nmid k}}k$と定める。(ただし$0!_p=1$)
また$\dis n!_p=\frac{\prod^n_{k=1}k}{\prod_{p|k}k}
=\frac{n!}{\prod^{\s{\farc{n}{p}}}_{j=1}pj}
=\frac{n!}{p^{\s{\frac np}}(\s{\frac np})!}$とも表せれる。
$N_i$を$n$の$p$進数表示における(下から)$i+1$から$i+e$桁目まで抜き出したもの、つまり
$N_i=n_{i+e-1}\cdots n_{i+1}n_i\;{}_{(p)}\quad$(このとき$N_i\equiv\s{\frac{n}{p^i}}\pmod{p^e}$が成り立つ。)
とおく。$m,l$についても同様に$M_i,L_i$を定める。また$k_j=\sum^{d-1}_{i=j}\e_i$とおく。
そして符号$\d_{p^e}=\pm1$を$\dis\d_{p^e}=\left\{\begin{array}{cl}1&\if p^e=2^e\geq2^3\\-1&\mathrm{otherwise}\end{array}\right.$と定める。
このとき
$\dis\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}$
が成り立つ。(Kummerの定理から$\b nm$は丁度$p^{k_0}$で割り切れることに注意する)
一般化Lucasの定理を$e=1$のときに適応すると
$\dis\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$なので
$\dis\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)},\;m=37=122_{(5)},\;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,\;A_i=a_{i+1}a_i\;{}_{(2)},\;B_i=b_{i+1}b_i\;{}_{(2)}$
$c=a-b=c_dc_{d-1}\cdots c_1c_0\;{}_{(2)},\;C_i=c_{i+1}c_i\;{}_{(2)}$
とおくと一般化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$であるので
$\dis\frac{\b{4a+1}{4b+1}}{2^{k_0}}\eq\frac{\b ab}{2^{k_0}}\pmod{4}$
ひいては
$\dis\b{4a+1}{4b+1}\eq\b ab\pmod{4}$
を得る。といった具合に示せます。
証明
Kummerの定理
$\dis v_p(n!)=\frac{n-\sum^d_{i=1}n_i}{p-1}$が成り立つ。
$\dis n=\sum^d_{i=1}n_ip^i$より$\dis\s{\frac{n}{p^j}}=\sum^d_{i=j}n_ip^{i-j}$なので通常のLegendreの公式から
$\dis 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,\;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=0}(p\e_i-\e_{i-1})}{p-1}
=\frac{(p-1)\sum^{d-1}_{i=1}\e_i}{p-1}=\sum^{d-1}_{i=1}\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}
と主張を得る。
$(p^e)!_p\eq\d_{p^e}\pmod{p^e}$が成り立つ。
$\dis(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$になるので
$\dis\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}$
で尽くされるので
$\dis\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の公式より
$\dis\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より
$\dis\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}
を得る。