p進法展開からみる階乗と二項係数の整数論的性質 その２
前回の記事 では，階乗や二項係数が素数$p$で割り切れる回数について見てきました．今回は，余りの世界から階乗や二項係数の性質を見ていきます．次のウィルソンの定理を使います．
素数$p$に対し，
$$(p-1)!\equiv -1 \pmod{p}$$
$p=2$のときは明らかに成立するので，$p$が奇素数の時を考える．$p$は素数なので$k=1,2,3,\cdots,p-1$に対し，合同方程式$kx\equiv 1\pmod{p}$の解は全て異なり，$1,2,3,\cdots,p-1$が一つずつ現れる．特に$k=x$となるのは$k^2-1\equiv0 \pmod{p}$の解だから$k=1,p-1$のときのみである．よって，$2,3,\cdots,p-2$から積が$1$となるペアが$\frac{p-3}{2}$組つくれるので，$$(p-1)!\equiv 1\cdot 1^{\frac{p-3}{2}}\cdot(p-1)\equiv -1 \pmod{p}$$
これからこのウィルソンの定理を使って階乗や二項係数の$\mod p$での性質を見ていきたいのですが，$n!$を素数$p$で割った余りというのは$n$が$p$以上のとき$0$になってしまうだけで面白くありません．またそれでは二項係数の$\mod p$での性質もわかりません．そこでここでは，$n!$の$p$の指数を$0$として得られる整数に対して，$p$で割った余りを考えることにします．そのためにまずは次の記号を導入しましょう．
正の整数$n$，素数$p$に対し，
$F_p(n):=\frac{n}{p^{ord_p(n)}}$とする．すなわち，$F_p(n)$で$n$の素因数$p$の指数を$0$として得られる整数を表す．
これに対し，$F_p(n!)$の$\mod p$での計算式を見つけてしまえば
$F_p({}_nC_{k})\equiv F_p(n!)F_p(k!)^{-1}F_p((n-k)!)^{-1} \pmod p$
なので，二項係数の$\mod p$での値も分かるのです!
(ただし$n^{-1}$は$\mod{p}$での$n$の逆元($nx\equiv 1$の解)を表すとします)
それでは実際に計算していきましょう．まず，ウィルソンの定理を使うと，$F_p(n!)$を$p$で割った余りについて次の定理が得られます．
$n={a_sa_{s-1}\cdots a_0}_{(p)}$に対し，
$$
F_p(n!) \equiv (-1)^{ord_p(n!)} \prod_{i=0}^{s}{a_i!} \pmod p
$$
$1,2,3,\cdots,n$のうち，$p$で$i$回割り切れるものを書き出すと，
$1p^i,2p^i,3p^i,\cdots,(p-1)p^i,(p+1)p^i,\cdots,(p^2-1)p^i,(p^2+1)p^i,\\
\cdots,(({a_sa_{s-1}\cdots a_{i+1}}_{(p)})p-1)p^i,(({a_sa_{s-1}\cdots a_{i+1}}_{(p)})p+1)p^i,(({a_sa_{s-1}\cdots a_{i+1}}_{(p)})p+2)p^i,\cdots,({a_sa_{s-1}\cdots a_i}_{(p)})p^i$
となる．これらに$F_p$を施した値は$\mod p$においてそれぞれ
$1,2,3,\cdots,(p-1),1,\cdots,(p-1),1,\cdots,(p-1),1,2,\cdots,a_i$
となる．これには$1,2,3,\cdots,p-1$の並びが${a_0a_1\cdots a_{i+1}}_{(p)}$回現れ，最後に$1,2,3,\cdots,a_i$が現れるので，ウィルソンの定理よりこれらの積は$\mod p$において$(-1)^{{a_sa_{s-1}\cdots a_{i+1}}_{(p)}}a_i!$
となる．よって，
$$
F_p(n!) \equiv (-1)^{{a_sa_{s-1}\cdots a_{1}}_{(p)}+{a_sa_{s-1}\cdots a_{2}}_{(p)}+\cdots+{a_{s}}_{(p)}}\prod_{i=0}^{s}{a_i!} \pmod p
$$
ここで，前回扱ったルジャンドルの定理から，
$$
{a_sa_{s-1}\cdots a_{1}}_{(p)}+{a_sa_{s-1}\cdots a_{2}}_{(p)}+\cdots+{a_{s}}_{(p)}=ord_p(n!)
$$
以上より，
$$
F_p(n!) \equiv (-1)^{ord_p(n!)}\prod_{i=0}^{s}{a_i!} \pmod p
$$
ここから二項係数については次が得られます．
$n={a_sa_{s-1}\cdots a_0}_{(p)},k={b_sb_{s-1}\cdots b_0}_{(p)},n-k={c_sc_{s-1}\cdots c_0}_{(p)}$に対し，
$$
F_p({}_{n} C _{k}) \equiv (-1)^{ord_p({}_{n} C _{k})}\prod_{i=0}^{s} a_i!(b_i!)^{-1}(c_i!)^{-1} \pmod p
$$
ただし，$k^{-1}$で$\mod p$における$k$の逆元($kx\equiv 1$の解)を表すものとする．
これが特に重要になるのは${}_{n} C _{k} \not\equiv 0$のときです．前回紹介した通りこのとき全ての$i$に対して$c_i=a_i-b_i\ge 0$となります．よって次の定理が得られます．
$n={a_sa_{s-1}\cdots a_0}_{(p)},k={b_sb_{s-1}\cdots b_0}_{(p)}$に対し，全ての$i$に対し$a_i\ge b_i$となるときのみ${}_{n} C _{k} \not\equiv 0 \pmod p$であり，このとき
$$
{}_{n} C _{k} \equiv \prod_{i=0}^{s} {}_{a_i} C _{b_i} \pmod p
$$
かなり綺麗な結果になりました．実際に使ってみて正しいかどうか確認しましょう!
${}_{2022}C_{142}$を$5$で割った余りを求めよ．
(自作問題)
解答
$2022={31042}_{(5)}$,$142={1032}_{(5)}$なので，定理3より，
$$ {}_{2022} C _{142} \equiv {}_{3}C_{0}\cdot{}_{1}C_{1}\cdot{}_{0}C_{0}\cdot{}_{4}C_{3}\cdot{}_{2}C_{2} \equiv 4 \pmod 5 $$
実際にwolfram alphaで${}_{2022}C_{142}$を計算してみると，
${}_{2022}C_{142}=61391415205958041091425541426 \cdots 76234792040522753244 \equiv 4 \pmod 5$
となって正しいことが確認できる．
追記: 後から知ったのですが，定理3はLucasの定理という名前のある結構有名な定理でした．