1

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

666
0
$$$$

はじめに

この記事は、二項係数の連載の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$のべきのときにも有用です。

補題1

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

補題1より
$$ (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$個選んで、、、、と選ぶことで作られますから、その場合の数を考えることで上の式を得ます。まとめると、次のようです。

$p$を素数とする。$m,n$$p$進数表示したときの$p^k$の位の数を$M_k,N_k$とするとき、
$$ \binom{m}{n}\equiv \prod_{k=0}^{\infty} \binom{M_k}{N_k} \mod p $$
が成り立つ。

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

おわりに

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

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

投稿日:20201125

この記事を高評価した人

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

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

バッジはありません。

投稿者

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中