大学数学基礎解説

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

整数,二項係数

891

はじめに

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

テーマ

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

母関数

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

数列$(a_n)_{n\in \mathbb{N}}$を係数にもつ多項式(またはその無限和)
$$ a_0+a_1x+a_2x^2+\cdots $$
を、$(a_n)_{n\in \mathbb{N}}$の母関数という。

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

整数係数多項式の合同式

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

整数係数多項式の合同式

整数係数多項式$f(x),g(x)$が、次の条件を満たすとき、$f$と$g$は法を$p$として合同であるといい、$f\equiv g$と表す。
(条件)　任意の$k$に対し、$f(x),g(x)$の$x^k$の係数は法を$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$が素数のとき、
$$ (1+x)^p \equiv 1+x^p\mod p $$
が成り立つ。

$$ (1+x)^p=1+\binom{p}{1}x+\cdots +\binom{p}{p-1}x^{p-1}+\binom{p}{p}x^p $$
である。ここで、前回の記事の考察により、$r=1,2,\cdots ,p-1$に対して、$\binom{p}{r}$は$p$で(ちょうど一回)割り切れる。(実際、$R_p(p)=0< R_p(r)$である。)したがって目的の合同式を得る。

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

補題１

$p$が素数のとき、任意の正整数$k$に対して、
$$ (1+x)^{p^k} \equiv 1+x^{p^k}\mod p $$
が成り立つ。

補題１より
$$ (1+x)^{p^k} \equiv ((1+x)^{p})^{p^{k-1}} \equiv (1+x^p)^{p^{k-1}} \equiv ((1+x^p)^p)^{p^{k-2}} \equiv \cdots \equiv 1+x^{p^k}\mod 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$個選んで、、、、と選ぶことで作られますから、その場合の数を考えることで上の式を得ます。まとめると、次のようです。