1

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

891
0

はじめに

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

テーマ

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

母関数

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

数列(an)nNを係数にもつ多項式(またはその無限和)
a0+a1x+a2x2+
を、(an)nNの母関数という。

二項係数は、ご存知の通り、美しい母関数を持っています。
(m0)+(m1)x+(m2)x2++(mm)xm=(1+x)m
これを用いて、二項係数のpで割ったあまりを調べていきます。

整数係数多項式の合同式

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

整数係数多項式の合同式

整数係数多項式f(x),g(x)が、次の条件を満たすとき、fgは法をpとして合同であるといい、fgと表す。
(条件) 任意のkに対し、f(x),g(x)xkの係数は法をpとして合同である。

ここでは証明はしませんが、この定義によって、整数の合同式と同じような計算ができます。例えば
f1g1, f2g2f1+f2g1+g2, f1f2g1g2
という具合です。このもとで、(1+x)mf(x)modpとなるf(x)で、係数が簡単なものがあれば、両辺の係数を比較して、二項係数のpで割ったあまりを求めることができるわけです。では、そのようなf(x)はどう見つけるのでしょうか。

(1+x)p1+xpmodp

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

pが素数のとき、
(1+x)p1+xpmodp
が成り立つ。

(1+x)p=1+(p1)x++(pp1)xp1+(pp)xp
である。ここで、 前回の記事 の考察により、r=1,2,,p1に対して、(pr)pで(ちょうど一回)割り切れる。(実際、Rp(p)=0<Rp(r)である。)したがって目的の合同式を得る。

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

補題1

pが素数のとき、任意の正整数kに対して、
(1+x)pk1+xpkmodp
が成り立つ。

補題1より
(1+x)pk((1+x)p)pk1(1+xp)pk1((1+xp)p)pk21+xpkmodp
となる。

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

以上の準備により、二項係数の素数pで割ったあまりが求められます。
mp進数表示し、そのpkの位の数をMkとします。すると、
m=k=0Mkpk
ですから、
(1+x)m=k=0(1+x)Mkpkk=0(1+xpk)Mkmodp
となります。(mn)は最右辺の展開のxnの係数と合同です。そしてそれは、np進数表示したときのpkの係数をNkとして、
k=0(MkNk)
と表すことができます。ただし、Mk<Nkならば(MkNk)=0とします。実際、xnの項は、M0個の(1+x)からN0個選んで、M1個の(1+xp)からN1個選んで、、、、と選ぶことで作られますから、その場合の数を考えることで上の式を得ます。まとめると、次のようです。

pを素数とする。m,np進数表示したときのpkの位の数をMk,Nkとするとき、
(mn)k=0(MkNk)modp
が成り立つ。

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

おわりに

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

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

投稿日:20201125
OptHub AI Competition

この記事を高評価した人

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

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

バッジはありません。
バッチを贈って投稿者を応援しよう

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

投稿者

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. はじめに
  2. テーマ
  3. 母関数
  4. 整数係数多項式の合同式
  5. (1+x)p1+xpmodp
  6. 二項係数の素数pで割ったあまり
  7. おわりに