はじめに
この記事は、二項係数の連載のPart2です。Part1は
こちら
からご覧ください。
テーマ
今回は、二項係数を素数で割ったあまりについて調べます。
母関数
前回の記事
の議論では、ある素因数の個数についてしかわからず、で割ったあまりについてはわかりません。よって、別の方法が必要になります。それは、「母関数」を使うものです。
数列を係数にもつ多項式(またはその無限和)
を、の母関数という。
二項係数は、ご存知の通り、美しい母関数を持っています。
これを用いて、二項係数ので割ったあまりを調べていきます。
整数係数多項式の合同式
どうやって上の式を使うのかというと、次のような定義で合同式を考えます。
整数係数多項式の合同式
整数係数多項式が、次の条件を満たすとき、とは法をとして合同であるといい、と表す。
(条件) 任意のに対し、のの係数は法をとして合同である。
ここでは証明はしませんが、この定義によって、整数の合同式と同じような計算ができます。例えば
という具合です。このもとで、となるで、係数が簡単なものがあれば、両辺の係数を比較して、二項係数ので割ったあまりを求めることができるわけです。では、そのようなはどう見つけるのでしょうか。
この節のタイトルにある通り、次の補題が成り立ちます。
である。ここで、
前回の記事
の考察により、に対して、はで(ちょうど一回)割り切れる。(実際、である。)したがって目的の合同式を得る。
これは、指数がのべきのときにも有用です。
二項係数の素数で割ったあまり
以上の準備により、二項係数の素数で割ったあまりが求められます。
を進数表示し、そのの位の数をとします。すると、
ですから、
となります。は最右辺の展開のの係数と合同です。そしてそれは、を進数表示したときのの係数をとして、
と表すことができます。ただし、ならばとします。実際、の項は、個のから個選んで、個のから個選んで、、、、と選ぶことで作られますから、その場合の数を考えることで上の式を得ます。まとめると、次のようです。
を素数とする。を進数表示したときのの位の数をとするとき、
が成り立つ。
もちろん、この右辺はより小さいとは限りませんから、これであまりが完璧に求まったわけではないですが、多くの場合において、左辺を実際に計算してで割るより、圧倒的に計算量が少ないです。
おわりに
今回は、二項係数のを考えました。次は、を考えてみたいと思いますが、その前に、それに使う考え方として、「整数係数多項式による整数の分類」というものについて書きたいと思います。
読んでいただきありがとうございました。次回もお楽しみに。