1

二項係数Part3 〜整数係数多項式による整数の分類〜

128
0

はじめに

この記事は、二項係数の連載のPart3です。 Part1 , Part2 を読んでいない方は、ぜひ先にご覧ください。

テーマ

今回は、二項係数からは外れますが、「整数係数多項式による整数の分類」というものについて書いていきます。整数係数多項式f(x)が与えられたとき、f(x)modpが等しいxを同値とみなす同値類を考えるということです。

整数係数多項式による整数の分類

以下、pを素数とします。整数係数多項式f(x)が与えられると、
R(i;p)={xZ|f(x)imodp}
として、
Z=i=0p1R(i;p)
と、Zを互いに交わらないp個の集合に分けることができます。さらに、
f(x)imodpef(x)i,i+pe,,i+(p1)pemodpe+1
であるので、
R(i;pe)=k=0p1R(i+kp;pe+1)
と、R(i;pe)をさらに互いに交わらないp個の集合に分けることができます。このような分類を次のような図で捉えます。
分類 分類
一番上を0段目として数えることにします。また、各R(i;pe)を部屋と考え、「e段目のi号室」などと表すことにします。
さて、例えば1段目では、1p+1を区別する必要はありません。そこで、次のような比喩を考えたいと思います。すなわち、0段目から0,1,,p1が落ちてきて、1段目の然るべき部屋に入ります。11,p+1,,(p1)p+1p個に分裂して2段目の然るべき部屋に入り、他の数も同様にして、無限に下の方に落ちてゆくのです。
このとき、各数の落ち方には規則があるのです。その規則を知ることで、与えられたxZに対して、xがどの部屋に入るのか、すなわちf(x)modpeを求められる場合があるということです。その最も重要な規則は次のものです。

落下の規則

x{0,1,,p1}に対し、f(x)0modpならば、xが分裂してできたp個は一段下のp個の部屋に一つずつバラバラに落ちる。以降xを先祖に持つものはすべて同じ落ち方をする。
一方、f(x)0modpならば、xが分裂してできたp個は一段下のp個の部屋のいずれか一つにまとまって落ちる。以降xを先祖に持つものはすべて同じ落ち方をする。

つまり、f(x)modpeについて知りたかったら、f(x)modp0か否かを調べるとよいわけです。それがいわばxの遺伝子であり、0でないなら常にバラバラに落ちてきたこと、0なら常にまとまって落ちてきたことが分かるのです。
これは整数論の初等的な定理であり、特に難しい証明は要しませんが、きちんと書くと長くなりますし、本記事の趣旨から外れますので、証明は省きます。

例として、次の問題を考えてみましょう。

pを奇素数とする。xp1kmodpe (0xpe1)の解の個数を調べよ。

(解答)
フェルマーの小定理より、e=1のときは自明(k=0のとき1個,k=1のときp1個,他0個)。e>1のときを考える。f(x)=xp1とすると、f(x)=(p1)xp2であり、これがpを法として0となるのはx=0のみだから、1,2,,p1は以降常にバラバラに落ち、0は以降常にまとまって落ちる。したがって、解の個数は、k1modpのときp1個、k0modpのときpe1個である。その他の場合は0個である。

(x3)20mod49を満たす0x48をすべて求めよ。

(解答)
(x3)20mod7の解はx=3のみ。f(x)=(x3)2として、f(3)0mod7なので、33,10,,457個に分裂して一つの部屋にまとまって落ちる。f(3)0mod49より、これらはすべて0号室に落ちたと分かるから、求める解は3,10,,45である。

おわりに

今回の分類法を用いて、次回の記事で、いよいよ特殊な二項係数の素数のべきで割った余りを求める方法を紹介したいと思います。連載はそれで終わる予定です。
読んでいただきありがとうございました。

投稿日:20201219
OptHub AI Competition

この記事を高評価した人

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

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

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

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

投稿者

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. はじめに
  2. テーマ
  3. 整数係数多項式による整数の分類
  4. おわりに