二項係数Part2 〜素数pで割ったあまり〜

はじめに

この記事は、二項係数の連載のPart2です。Part1は こちら からご覧ください。

テーマ

今回は、二項係数を素数$p$で割ったあまりについて調べます。

母関数

前回の記事 の議論では、ある素因数$p$の個数についてしかわからず、$p$で割ったあまりについてはわかりません。よって、別の方法が必要になります。それは、「母関数」を使うものです。

二項係数は、ご存知の通り、美しい母関数を持っています。
$$ \binom{m}{0}+\binom{m}{1}x+\binom{m}{2}x^2+\cdots +\binom{m}{m}x^m=(1+x)^m $$
これを用いて、二項係数の$p$で割ったあまりを調べていきます。

整数係数多項式の合同式

どうやって上の式を使うのかというと、次のような定義で合同式を考えます。

ここでは証明はしませんが、この定義によって、整数の合同式と同じような計算ができます。例えば
$$ f_1\equiv g_1,\ f_2\equiv g_2 \Rightarrow f_1+f_2\equiv g_1+g_2,\ f_1f_2\equiv g_1g_2 $$
という具合です。このもとで、$(1+x)^m\equiv f(x)\mod p$となる$f(x)$で、係数が簡単なものがあれば、両辺の係数を比較して、二項係数の$p$で割ったあまりを求めることができるわけです。では、そのような$f(x)$はどう見つけるのでしょうか。

$(1+x)^p\equiv 1+x^p\mod p$

この節のタイトルにある通り、次の補題が成り立ちます。

これは、指数が$p$のべきのときにも有用です。

二項係数の素数$p$で割ったあまり

以上の準備により、二項係数の素数$p$で割ったあまりが求められます。
$m$を$p$進数表示し、その$p^k$の位の数を$M_k$とします。すると、
$$ m=\sum_{k=0}^{\infty}M_kp^k $$
ですから、
$$ (1+x)^m=\prod_{k=0}^{\infty}(1+x)^{M_kp^k}\equiv \prod_{k=0}^{\infty}(1+x^{p^k})^{M_k} \mod p $$
となります。$\binom{m}{n}$は最右辺の展開の$x^n$の係数と合同です。そしてそれは、$n$を$p$進数表示したときの$p^k$の係数を$N_k$として、
$$ \prod_{k=0}^{\infty} \binom{M_k}{N_k} $$
と表すことができます。ただし、$M_k< N_k$ならば$\binom{M_k}{N_k}=0$とします。実際、$x^n$の項は、$M_0$個の$(1+x)$から$N_0$個選んで、$M_1$個の$(1+x^p)$から$N_1$個選んで、、、、と選ぶことで作られますから、その場合の数を考えることで上の式を得ます。まとめると、次のようです。

もちろん、この右辺は$p$より小さいとは限りませんから、これであまりが完璧に求まったわけではないですが、多くの場合において、左辺を実際に計算して$p$で割るより、圧倒的に計算量が少ないです。

おわりに

今回は、二項係数の$\mod p$を考えました。次は、$\mod p^k$を考えてみたいと思いますが、その前に、それに使う考え方として、「整数係数多項式による整数の分類」というものについて書きたいと思います。

読んでいただきありがとうございました。次回もお楽しみに。