はじめに
この記事は、二項係数の連載のPart3です。
Part1
,
Part2
を読んでいない方は、ぜひ先にご覧ください。
テーマ
今回は、二項係数からは外れますが、「整数係数多項式による整数の分類」というものについて書いていきます。整数係数多項式が与えられたとき、が等しいを同値とみなす同値類を考えるということです。
整数係数多項式による整数の分類
以下、を素数とします。整数係数多項式が与えられると、
として、
と、を互いに交わらない個の集合に分けることができます。さらに、
であるので、
と、をさらに互いに交わらない個の集合に分けることができます。このような分類を次のような図で捉えます。
分類
一番上を段目として数えることにします。また、各を部屋と考え、「段目の号室」などと表すことにします。
さて、例えば段目では、とを区別する必要はありません。そこで、次のような比喩を考えたいと思います。すなわち、段目からが落ちてきて、段目の然るべき部屋に入ります。はの個に分裂して段目の然るべき部屋に入り、他の数も同様にして、無限に下の方に落ちてゆくのです。
このとき、各数の落ち方には規則があるのです。その規則を知ることで、与えられたに対して、がどの部屋に入るのか、すなわちを求められる場合があるということです。その最も重要な規則は次のものです。
落下の規則
に対し、ならば、が分裂してできた個は一段下の個の部屋に一つずつバラバラに落ちる。以降を先祖に持つものはすべて同じ落ち方をする。
一方、ならば、が分裂してできた個は一段下の個の部屋のいずれか一つにまとまって落ちる。以降を先祖に持つものはすべて同じ落ち方をする。
つまり、について知りたかったら、がか否かを調べるとよいわけです。それがいわばの遺伝子であり、でないなら常にバラバラに落ちてきたこと、なら常にまとまって落ちてきたことが分かるのです。
これは整数論の初等的な定理であり、特に難しい証明は要しませんが、きちんと書くと長くなりますし、本記事の趣旨から外れますので、証明は省きます。
例
例として、次の問題を考えてみましょう。
(解答)
フェルマーの小定理より、のときは自明(のとき1個,のとき個,他個)。のときを考える。とすると、であり、これがを法としてとなるのはのみだから、は以降常にバラバラに落ち、は以降常にまとまって落ちる。したがって、解の個数は、のとき個、のとき個である。その他の場合は個である。
(解答)
の解はのみ。として、なので、はの個に分裂して一つの部屋にまとまって落ちる。より、これらはすべて号室に落ちたと分かるから、求める解はである。
おわりに
今回の分類法を用いて、次回の記事で、いよいよ特殊な二項係数の素数のべきで割った余りを求める方法を紹介したいと思います。連載はそれで終わる予定です。
読んでいただきありがとうございました。