一般化Lucasの定理と東大数学2021
はじめに
この記事では今年の東大入試問題を起点に二項係数${}_nC_m$にまつわる法$p^e$の合同関係を紹介していきます。
さて今年の東大入試では第4問に次のような問題が出たとのことでした。
以下の問いに答えよ。
- 正の奇数$K,L$と正の整数$A,B$が$KA=LB$を満たしているとする。$K$を$4$で割った余りが$L$を$4$で割った余りと等しいならば、$A$を$4$で割った余りは$B$を$4$で割った余りと等しいことを示せ。
- 正の整数$a,b$が$a>b$を満たしているとする。このとき、$A={}_{4a+1}C_{4b+1},B={}_aC_b$に対して$KA=LB$となるような正の奇数$K,L$が存在することを示せ。
- $a,b$は(2)の通りとし、さらに$a-b$が$2$で割り切れるとする。${}_{4a+1}C_{4b+1}$を$4$で割った余りは${}_aC_b$を$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の定理が頭に浮かびました。
素数$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$と定める。
$\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})!}$$
とも表せることに注意する。
$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}{rl}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}}
\farc{(N_d)!_p}{(M_d)!_p(L_d)!_p}
\cdots
\farc{(N_1)!_p}{(M_1)!_p(L_1)!_p}
\c\farc{(N_0)!_p}{(M_0)!_p(L_0)!_p}\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\c
\frac{(03)!_5}{(00)!_5(03)!_5}\c
\frac{(31)!_5}{(00)!_5(30)!_5}\c
\frac{(10)!_5}{(01)!_5(04)!_5}\c
\frac{(04)!_5}{(12)!_5(41)!_5}\c
\frac{(41)!_5}{(22)!_5(14)!_5}
\\&=_{(5)}&{-}1\c1\c31_{(5)}\c1\c\frac{(04)!_5}{(12)!_5(22)!_5(14)!_5}
\\&=_{(10)}&{-}16\c\frac{4!}{\frac{7!}5\c\frac{12!}{5\c10}\c\frac{9!}5}
\\&\eq_{(10)}&9\c\frac{4!}{(4!)^3}\c\frac1{(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)}&-\frac1{2^9}\c\frac{7}{49}
\eq2\c(-7)\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}{rl}
\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の定理
$\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}$$
を得る。
$\dis v_p({}_nC_m)=\sum^{d-1}_{i=0}\e_i\quad$が成り立つ。
いま$n=m+l$および$\e_i$の取り方から
\begin{align}
n_0&=m_0+l_0-p\e_0\\
n_i&=m_i+l_i+\e_{i-1}-p\e_i\quad(i\geq1)
\end{align}
が成り立つので($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}
と主張を得る。
$(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{n/p^e}}(N_0)!_p\pmod{p^e}$が成り立つ。
\begin{align}
n!_p
&=\l(\prod^{\lfloor n/p^e\rfloor-1}_{i=0}\frac{((i+1)p^e)!_p}{(ip^e)!_p}\r)\frac{n!_p}{(n-N_0)!_p}\\
&\equiv\Big((p^e)!_p\Big)^{\s{n/p^e}}(N_0)!_p\\
&\equiv\d_{p^e}^{\s{n/p^e}}(N_0)!_p\pmod{p^e}
\end{align}
とわかる。
$(\lfloor n/p^{e-1}\rfloor)!$の素因数分解における$p$の指数を$v'=\sum^d_{j=e}\lfloor n/p^j\rfloor$とおくと
$$\frac{n!}{p^{v_p(n!)}}\equiv\d_{p^e}^{v'}\prod^d_{j=0}(N_j)!_p\pmod{p^e}$$
が成り立つ。
$$n!_p=\frac{n!}{p^{\s{n/p}}(\s{n/p})!}$$
であったことおよび通常のLegendreの公式より
\begin{align}
\frac{n!}{p^{v_p(n!)}}
&=\frac{(\s{n/p^0})!}{p^{\sum^d_{j=0}\s{n/p^j}}(\s{n/p^{d+1}})!}\\
&=\prod^d_{j=0}\frac{(\s{n/p^j})!}{p^{\s{n/p^j}}(\s{n/p^{j+1}})!}\\
&=\prod^d_{j=0}(\s{\frac n{p^j}})!_p
\end{align}
と変形できるので補題8より
$$\frac{n!}{p^{v_p(n!)}}
\eq\prod^d_{j=0}\d_{p^e}^{\s{\frac{n}{p^{e+j}}}}(N_j)!_p
=\d_{p^e}^{v'}\prod^d_{j=0}(N_j)!_p\pmod{p^e}$$
を得る。
$$\frac{\b nm}{p^{k_0}}\eq\d_{p^e}^{k_{e-1}}
\farc{(N_d)!_p}{(M_d)!_p(L_d)!_p}
\cdots
\farc{(N_1)!_p}{(M_1)!_p(L_1)!_p}\c
\farc{(N_0)!_p}{(M_0)!_p(L_0)!_p}\pmod{p^e}$$
が成り立つ。
補題6より
\begin{align}
\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!}\\
&\equiv\d_{p^e}^{\sum^d_{j=e}(\s{\frac n{p^j}}-\s{\frac m{p^j}}-\s{\frac l{p^j}})}
\prod^d_{j=0}\frac{(N_j)!_p}{(M_j)!_p(L_j)!_p}\pmod{p^e}\\
&=\d_{p^e}^{\sum^d_{j=e}\e_{j-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{align}
を得る。
おまけ
定理9として紹介したように一般化Lucasの定理より強い主張として、$v'=\sum^d_{j=e}\lfloor n/p^j\rfloor$とおいたとき
$$\frac{n!}{p^{v_p(n!)}}\equiv\d_{p^e}^v\prod^d_{j=0}(N_j)!_p\pmod{p^e}$$
という公式が成り立つのでした。
これを使うと例えば以下のようなことが言えたりします。
奇素数$p$と非負整数$n$に対し、$n$の$p$進数表示を
$$n=n_dn_{d-1}\cdots n_1n_0\ {}_{(p)}$$
とおくと
$$\frac{n!}{p^{v_p(n!)}}\equiv(-1)^{v_p(n!)}n_d!n_{d-1}!\cdots n_1!n_0!\pmod p$$
が成り立つ。
$(10^{14})!$の$0$でない部分の下二桁、つまり
$$\frac{(10^{14})!}{10^{v_5((10^{14})!)}}\pmod{100}$$
を求めたい。
いま
$$10^{14}=16384\c5^{14}=1011014_{(5)}\c10^{14}_{(5)}$$
より
\begin{align}
v&=\frac{10^{14}-(1+1+1+1+4)}4=25\c10^{12}-2\\
v'&=\frac{\frac{10^{14}}5-(1+1+1+1+4)}4=5\c10^{12}-2
\end{align}
とおくと
\begin{align}
\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\pmod{25}\\
&=_{(10)}1\c1\c4!\c1\c(6\c4!)\c4!\c1\c(9\c8\c7\c6\c4!)\c(25!_5/24\c23\c22\c21)\\
&\equiv_{(10)}(4!)^4\c25!_5\c36/23\c22\\
&\equiv_{(10)}-36/(-2)\c(-3)=6\pmod{25}
\end{align}
が成り立つので$2^{20}\equiv1\pmod{25}$に注意すると
$$\frac{(10^{14})!}{10^v}\equiv-6\c2^{-v}\equiv-6\c2^2\equiv1\pmod{25}$$
つまり、明らかに$(10^{14})!/10^v\equiv0\pmod4$であること合わせると
$$\frac{(10^{14})!}{10^v}\equiv76\pmod{100}$$
を得る。
追記：計算の簡略化
いくつかの例からもわかるように一般化Lucasの定理を使っても法$p^e$の指数が高くなるほどその手計算はダルくなっていくわけですが、法$p^3$程度であればウォルステンホルムの定理を使うことで幾ばくか計算を楽にできることに気付いたのでそのことについて簡単に紹介していきます。
以下$p\geq5$とします。
$\dis\sum^{p-1}_{k=1}\frac1k\equiv0\pmod{p^2}$
\begin{align}
\sum^{p-1}_{k=1}\frac1k
&=\frac12\sum^{p-1}_{k=1}\l(\frac1k+\frac1{p-k}\r)
=\frac p2\sum^{p-1}_{k=1}\frac1{k(p-k)}\\
&\equiv-\frac p2\sum^{p-1}_{k=1}\frac1{k^2}
\equiv-\frac p2\sum^{p-1}_{k=1}k^2\\
&\equiv-p^2\frac{(p-1)(2p-1)}{12}\equiv0\pmod{p^2}
\end{align}
とわかる。
$\dis\sum_{1\leq i< j< p}\frac1{ij}\equiv0\pmod p$
$$\l(\sum^{p-1}_{k=1}\frac1k\r)^2
=\sum^{p-1}_{k=1}\frac1{k^2}+2\sum_{1\leq i< j< p}\frac1{ij}$$
に注意すると
\begin{align}
2\sum_{1\leq i< j< p}\frac1{ij}
&\equiv\l(\sum^{p-1}_{k=1}k\r)^2-\sum^{p-1}_{k=1}k^2\\
&=\frac{p^2(p-1)^2}4-\frac{p(p-1)(2p-1)}6\\
&=\frac{p(p-1)(p-2)(3p-1)}{12}\\
&\equiv0\pmod p
\end{align}
とわかる。
${}_{np-1}C_{p-1}\equiv1\pmod{p^3}$
\begin{align}
{}_{x-1}C_{p-1}
&=\frac{(x-1)(x-2)\cdots(x-(p-1))}{(p-1)!}\\
&=(1-x)\bigg(1-\frac x2\bigg)\cdots\l(1-\frac x{p-1}\r)\\
&=1-\l(\sum^{p-1}_{k=1}\frac1k\r)x+\l(\sum_{1\leq i< j< p}\frac1{ij}\r)x^2-\cdots
\end{align}
と展開できることに注意すると補題11,12から
\begin{align}
{}_{np-1}C_{p-1}
&\equiv1-\l(\sum^{p-1}_{k=1}\frac1k\r)np+\l(\sum_{1\leq i< j< p}\frac1{ij}\r)(np)^2\\
&\equiv1\pmod{p^3}
\end{align}
を得る。
素数$p$と非負整数$n$に対し
$$n!_p'=\frac{n!}{(n-n_0)!}$$
と定める。ただし$n_0$は$n$の$p$進数表示における下一桁とした。
特に$p\geq5$および$n_0=p-1$のとき
$$n!'_p\equiv(p-1)!\pmod{p^3}$$
が成り立つことに注意する。
$p\geq5$において
$$n!_p\equiv((p-1)!)^{\lfloor n/p\rfloor}n!_p'\pmod{p^3}$$
が成り立つ。
\begin{align}
n!_p
&=\l(\prod^{\lfloor n/p\rfloor-1}_{i=0}\frac{((i+1)p)!_p}{(ip)!_p}\r)\frac{n!_p}{(n-n_0)!_p}\\
&=\l(\prod^{\lfloor n/p\rfloor-1}_{i=0}{}_{(i+1)p-1}C_{p-1}\r)((p-1)!)^{\lfloor n/p\rfloor}\frac{n!}{(n-n_0)!}\\
&\equiv((p-1)!)^{\lfloor n/p\rfloor}\frac{n!}{(n-n_0)!}\pmod{p^3}
\end{align}
とわかる。
$p\geq5$および$e\leq3$において
$$\frac{n!}{p^{v_p(n!)}}\equiv((p-1)!)^{v_p(n!)}\prod^d_{j=0}(N_j)!_p'\pmod{p^e}$$
が成り立つ。
定理9の証明から
$$\frac{n!}{p^{v_p(n!)}}=\prod^d_{j=0}(\s{\frac n{p^j}})!_p$$
が成り立っていたので定理14から
\begin{align}
\frac{n!}{p^{v_p(n!)}}
&\equiv\prod^d_{j=0}((p-1)!)^{\lfloor n/p^{j+1}\rfloor}(\s{\frac n{p^j}})!_p'\\
&\equiv((p-1)!)^{v_p(n!)}
\prod^d_{j=0}(N_j)!_p'\pmod{p^e}
\end{align}
を得る。
$p\geq5$および$e\leq3$において
$$\frac{{}_nC_m}{p^{k_0}}\equiv((p-1)!)^{k_0}\prod^d_{j=0}\frac{(N_j)!_p'}{(M_j)!_p'(L_j)!_p'}\pmod{p^e}$$
が成り立つ。
例えば例3の計算は
\begin{align}
\frac{\b{2021}{37}}{5^2}
&\equiv_{(5)}4!^2\c
\frac{(03)!'_5}{(00)!'_5(03)!'_5}\c
\frac{(31)!'_5}{(00)!'_5(30)!'_5}\c
\frac{(10)!'_5}{(01)!'_5(04)!'_5}\c
\frac{(04)!'_5}{(12)!'_5(41)!'_5}\c
\frac{(41)!'_5}{(22)!'_5(14)!'_5}\\
&=_{(10)}4!^2\c1\c16\c\frac1{4!}\c\frac{4!}{7!'_512!'_59!'_5}\\
&\equiv_{(10)}-16\frac{4!}{(7\c6)\c(11\c12)\c4!}=-\frac{2\c7}{49\c99}\\
&\equiv_{(10)}11\pmod{25}
\end{align}
と簡略化できる。
また例えば例5の計算は
\begin{align}
\frac{(10^{14})!}{5^v}
&\equiv_{(5)}4!^v\c(01)!'_5(10)!'_5(01)!'_5(11)!'_5(10)!'_5(01)!'_5(14)!'_5(40)!'_5\\
&=_{(10)}4!^v\c6\c9!'_5\\
&\equiv_{(10)}1\c6\c4!\equiv-6\pmod{25}
\end{align}
と簡略化できる。
ちなみに$p=3$の場合も
$$\sum^2_{k=1}\frac1k=\frac32\equiv0\pmod3$$
は成り立つので、上と同様の議論によって
$${}_{3n-1}C_2\equiv1\pmod9$$
や
\begin{align}
\frac{n!}{3^{v_3(n!)}}
&\equiv2^{v_3(n!)}\prod^d_{j=0}(N_j)!'_3\pmod9\\
\frac{{}_nC_m}{3^{k_0}}
&\equiv2^{k_0}\prod^d_{j=0}\frac{(N_j)!'_3}{(M_j)!'_3(L_j)!'_3}\pmod9
\end{align}
が成り立ちます。
参考文献
この記事を高評価した人
投稿者
