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

はじめに

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

テーマ

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

母関数

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

二項係数は、ご存知の通り、美しい母関数を持っています。
$$(\genfrac{}{}{0ex}{}{m}{0})+(\genfrac{}{}{0ex}{}{m}{1})x+(\genfrac{}{}{0ex}{}{m}{2})x^2+\cdots +(\genfrac{}{}{0ex}{}{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_1{f}_2\equiv g_1{g}_2$$
という具合です。このもとで、$(1+x{)}^m\equiv f(x)\mathrm{mod}p$となる$f(x)$で、係数が簡単なものがあれば、両辺の係数を比較して、二項係数の$p$で割ったあまりを求めることができるわけです。では、そのような$f(x)$はどう見つけるのでしょうか。

$(1+x{)}^p\equiv 1+x^p\mathrm{mod}p$

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

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

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

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

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

おわりに

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

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