p進法展開からみる階乗と二項係数の整数論的性質その２

711

前回の記事では，階乗や二項係数が素数 $p$ で割り切れる回数について見てきました．今回は，余りの世界から階乗や二項係数の性質を見ていきます．次のウィルソンの定理を使います．

ウィルソンの定理

素数 $p$ に対し，
$(p - 1)! \equiv - 1 (\mod p)$

$p = 2$ のときは明らかに成立するので， $p$ が奇素数の時を考える． $p$ は素数なので $k = 1, 2, 3, \dots, p - 1$ に対し，合同方程式 $k x \equiv 1 (\mod p)$ の解は全て異なり， $1, 2, 3, \dots, p - 1$ が一つずつ現れる．特に $k = x$ となるのは $k^{2} - 1 \equiv 0 (\mod p)$ の解だから $k = 1, p - 1$ のときのみである．よって， $2, 3, \dots, p - 2$ から積が $1$ となるペアが $\frac{p - 3}{2}$ 組つくれるので， $(p - 1)! \equiv 1 \cdot 1^{\frac{p - 3}{2}} \cdot (p - 1) \equiv - 1 (\mod p)$

これからこのウィルソンの定理を使って階乗や二項係数の $\mod p$ での性質を見ていきたいのですが， $n!$ を素数 $p$ で割った余りというのは $n$ が $p$ 以上のとき $0$ になってしまうだけで面白くありません．またそれでは二項係数の $\mod p$ での性質もわかりません．そこでここでは， $n!$ の $p$ の指数を $0$ として得られる整数に対して， $p$ で割った余りを考えることにします．そのためにまずは次の記号を導入しましょう．

正の整数 $n$ ，素数 $p$ に対し，
$F_{p} (n) := \frac{n}{p^{o r d_{p} (n)}}$ とする．すなわち， $F_{p} (n)$ で $n$ の素因数 $p$ の指数を $0$ として得られる整数を表す．

これに対し， $F_{p} (n!)$ の $\mod p$ での計算式を見つけてしまえば
$F_{p} (_{n} C_{k}) \equiv F_{p} (n!) F_{p} (k!)^{- 1} F_{p} ((n - k)!)^{- 1} (\mod p)$
なので，二項係数の $\mod p$ での値も分かるのです!
(ただし $n^{- 1}$ は $\mod p$ での $n$ の逆元( $n x \equiv 1$ の解)を表すとします)

それでは実際に計算していきましょう．まず，ウィルソンの定理を使うと， $F_{p} (n!)$ を $p$ で割った余りについて次の定理が得られます．

$n = {a_{s} a_{s - 1} \dots a_{0}}_{(p)}$ に対し，
$F_{p} (n!) \equiv (- 1)^{o r d_{p} (n!)} \prod_{i = 0}^{s} a_{i}! (\mod p)$

$1, 2, 3, \dots, n$ のうち， $p$ で $i$ 回割り切れるものを書き出すと，
$1 p^{i}, 2 p^{i}, 3 p^{i}, \dots, (p - 1) p^{i}, (p + 1) p^{i}, \dots, (p^{2} - 1) p^{i}, (p^{2} + 1) p^{i}, \dots, (({a_{s} a_{s - 1} \dots a_{i + 1}}_{(p)}) p - 1) p^{i}, (({a_{s} a_{s - 1} \dots a_{i + 1}}_{(p)}) p + 1) p^{i}, (({a_{s} a_{s - 1} \dots a_{i + 1}}_{(p)}) p + 2) p^{i}, \dots, ({a_{s} a_{s - 1} \dots a_{i}}_{(p)}) p^{i}$
となる．これらに $F_{p}$ を施した値は $\mod p$ においてそれぞれ
$1, 2, 3, \dots, (p - 1), 1, \dots, (p - 1), 1, \dots, (p - 1), 1, 2, \dots, a_{i}$
となる．これには $1, 2, 3, \dots, p - 1$ の並びが ${a_{0} a_{1} \dots a_{i + 1}}_{(p)}$ 回現れ，最後に $1, 2, 3, \dots, a_{i}$ が現れるので，ウィルソンの定理よりこれらの積は $\mod p$ において $(- 1)^{{a_{s} a_{s - 1} \dots a_{i + 1}}_{(p)}} a_{i}!$
となる．よって，
$F_{p} (n!) \equiv (- 1)^{{a_{s} a_{s - 1} \dots a_{1}}_{(p)} + {a_{s} a_{s - 1} \dots a_{2}}_{(p)} + \dots + {a_{s}}_{(p)}} \prod_{i = 0}^{s} a_{i}! (\mod p)$

ここで，前回扱ったルジャンドルの定理から，
${a_{s} a_{s - 1} \dots a_{1}}_{(p)} + {a_{s} a_{s - 1} \dots a_{2}}_{(p)} + \dots + {a_{s}}_{(p)} = o r d_{p} (n!)$
以上より，
$F_{p} (n!) \equiv (- 1)^{o r d_{p} (n!)} \prod_{i = 0}^{s} a_{i}! (\mod p)$

ここから二項係数については次が得られます．

$n = {a_{s} a_{s - 1} \dots a_{0}}_{(p)}, k = {b_{s} b_{s - 1} \dots b_{0}}_{(p)}, n - k = {c_{s} c_{s - 1} \dots c_{0}}_{(p)}$ に対し，
$F_{p} (_{n} C_{k}) \equiv (- 1)^{o r d_{p} (_{n} C_{k})} \prod_{i = 0}^{s} a_{i}! (b_{i}!)^{- 1} (c_{i}!)^{- 1} (\mod p)$
ただし， $k^{- 1}$ で $\mod p$ における $k$ の逆元( $k x \equiv 1$ の解)を表すものとする．

これが特に重要になるのは $_{n} C_{k} ≢ 0$ のときです．前回紹介した通りこのとき全ての $i$ に対して $c_{i} = a_{i} - b_{i} \geq 0$ となります．よって次の定理が得られます．

$n = {a_{s} a_{s - 1} \dots a_{0}}_{(p)}, k = {b_{s} b_{s - 1} \dots b_{0}}_{(p)}$ に対し，全ての $i$ に対し $a_{i} \geq b_{i}$ となるときのみ $_{n} C_{k} ≢ 0 (\mod p)$ であり，このとき
$_{n} C_{k} \equiv \prod_{i = 0}^{s}_{a_{i}} C_{b_{i}} (\mod 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 (\mod 5)

実際にwolfram alphaで

_{2022} C_{142}

を計算してみると，

_{2022} C_{142} = 61391415205958041091425541426 \dots 76234792040522753244 \equiv 4 (\mod 5)

となって正しいことが確認できる．

追記: 後から知ったのですが，定理3はLucasの定理という名前のある結構有名な定理でした．

投稿日：2022年6月30日

この記事を高評価した人

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

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

バッジはありません。

バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

dragoemon

144

31667

大学3年生です

他の人のコメント

コメントはありません。

読み込み中

dragoemon

p進法展開からみる階乗と二項係数の整数論的性質その２

p進法展開からみる階乗と二項係数の整数論的性質 その２

この記事を高評価した人

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

投稿者

コメント

他の人のコメント

p進法展開からみる階乗と二項係数の整数論的性質その２