x^n-1の因数分解
さて、前々回、前回からの問題の回答です。。
問題は、
多項式 \[ x^{n}-1\] を整数係数多項式の中で因数分解したときの、因子の数を求めよというものでした。
\(n\)が1から11までについてやってみると次のようになりました。
| \(n\) | 因数分解 | 因子の数 | 最高次数 |
|---|---|---|---|
| 2 | \((x-1)(x+1)\) | 2 | 1 |
| 3 | \((x-1)(x^{2}+x+1)\) | 2 | 2 |
| 4 | \((x-1)(x+1)(x^{2}+1)\) | 3 | 2 |
| 5 | \((x-1)(x^{4}+x^{3}+x^{2}+x+1)\) | 2 | 4 |
| 6 | \((x-1)(x+1)(x^{2}+x+1)(x^{2}-x+1)\) | 4 | 2 |
| 7 | \((x-1)(x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1)\) | 2 | 6 |
| 8 | \((x-1)(x+1)(x^{2}+1)(x^{4}+1)\) | 4 | 4 |
| 9 | \((x-1)(x^{2}+x+1)(x^{6}+x^{3}+1)\) | 3 | 6 |
| 10 | \((x-1)(x+1)(x^{4}+x^{3}+x^{2}+x+1)(x^{4}-x^{3}+x^{2}-x+1)\) | 4 | 4 |
| 11 | \((x-1)(x^{10}+x^{9}+x^{8}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1)\) | 2 | 10 |
既にお気づきだと思いますが、\(x^{n}-1\)の因数分解は\(n\)が大きくなるほど複雑になるわけではなく、むしろ、\(n\)の約数が多ければ多いほど、\(x^{n}-1\)を因数分解した際の因子も多いと言うことが分かります。そこで、\(n\)の約数をカウントしてみます。
| \(n\) | \(n\)の約数 | 約数の数 | \(x^{n}-1\)の因子の数 |
|---|---|---|---|
| 2 | 1,2 | 2 | 2 |
| 3 | 1,3 | 2 | 2 |
| 4 | 1,2,4 | 3 | 3 |
| 5 | 1,5 | 2 | 2 |
| 6 | 1,2,3,4 | 4 | 4 |
| 7 | 1,7 | 2 | 2 |
| 8 | 1,2,4,8 | 4 | 4 |
| 9 | 1,3,9 | 3 | 3 |
| 10 | 1,2,5,10 | 4 | 4 |
| 11 | 1,11 | 2 | 2 |
このように見事\(n\)の約数と\(x^{n}-1\)を因数分解したときの因子の数が一致していますね。
それでは、最高次数はどうでしょうか。上の表から分かることは、\(n\)が素数の場合に\(n-1\)となっていること、\(n\)の約数が多いほど少なくなっていることが分かります。このような性質を持った数は、\(n\)と互いに素な\(n\)以下の自然数の数を表す\(\varphi(n)\)がありますね。\(\varphi(n)\)と最高次数を比べてみると次のようになります。
| \(n\) | \(\varphi(n)\) | \(x^{n}-1\)を因数分解した際の最高次数 |
|---|---|---|
| 2 | 1 | 1 |
| 3 | 2 | 2 |
| 4 | 2 | 2 |
| 5 | 4 | 4 |
| 6 | 2 | 2 |
| 7 | 6 | 6 |
| 8 | 4 | 4 |
| 9 | 6 | 6 |
| 10 | 4 | 4 |
| 11 | 10 | 10 |
一致していますね。
つまり、次が言えそうです。
\(x^{n}-1\)を整数係数多項式で因数分解したときの因子の数は、\(n\)の約数の数と一致する。また、因子の最高次数は\(\varphi(n)\)である。
このように、\(x^{n}-1\)の因数分解と\(n\)の素因数分解は密接に関わっています。一般的に多項式は因数分解の一位性があるなど、整数の性質に似た側面が多くありますが、これほどピッタリと一致する多項式の一群は、私の知る限りは\(x^{n}-1\)以外にはないのではないかと思います。それほど、\(x^{n}-1\)が特殊だということですね。
円分多項式とは
円分多項式が既約であることを前提とすれば、上の性質は比較的容易に証明できます。その前に、円分多項式とは何かから始めます。
\(x^{n}-1=0\)の解は、\(n\)乗して1になります。つまり、1の\(n\)乗根です。1の\(n\)乗根の中で、\(n\)乗してはじめて1になるもの（そのようなものを原始\(n\)乗根といいます。）の全てを解とする方程式で、原始\(n\)乗根以外を解としないものを円分多項式（cyclotomic polynomial)といい、\(\Phi_{n}(x)\)と書きます。
(例）\(n=p\)（素数）とするとき、1の原始\(p\)乗根は、\(\varphi(p)=p-1\)個あります。
一方、\((x^{p}-1)=(x-1)(x^{p-1}+x^{p-2}+\cdots+x+1)\)の\(x^{p-1}+x^{p-2}+\cdots+x+1\)は、\(p-1\)次式です。したがって、\(x^{p-1}+x^{p-2}+\cdots+x+1=0\)の解は全ての1の原始\(p\)乗根であることが分かりますので、\(\Phi_{p}(x)=x^{p-1}+x^{p-2}+\cdots+x+1\)であることが分かります。
（円分多項式の既約性）
円分多項式\(\Phi_{n}(x)\)は、既約な、整数係数多項式である。
証明は、①ガロアの理論を用いる方法、②Eisensteinの判定法を用いる方法、③有限体の分離性を用いる方法があるようです。
\(x^{n}-1\)の因数分解
さてこれを前提とすると、\(x^{n}-1\)の因数分解は簡単に分かります。
\(n=12\)の具体例で考えると、1の12乗根は、12乗してはじめて1になるもの、6乗してはじめて1になるもの、4乗してはじめて1になるもの、3乗してはじめて1になるもの、2乗してはじめて1になるもの、1乗してはじめて1になるもの（つまり、1）からなり、これらは重複しません。したがって、
\[ x^{12}-1=\Phi_{1}(x)\Phi_{2}(x)\Phi_{3}(x)\Phi_{4}(x)\Phi_{6}(x)\Phi_{12}(x)\]
となります。そして、1の原始\(d\)乗根は、\(\varphi(d)\)個ありますので\(\Phi_{d}(x)\)の次数は\(d\)であることが分かります。これを、具体的に書くと、 \[ x^{12}-1=(x-1)(x+1)(x^{2}+x+1)(x^{2}+1)(x^{2}-x+1)(x^{4}-x^{2}+1)\] です。\(n=12\)以外でも同様に示せます。
\(x^{n}-1\)を整数係数多項式で因数分解したときの因子の数は、\(n\)の約数の数と一致する。また、因子の最高次数は\(\varphi(n)\)である。
このように、私が高校生のときに悩んだ問題は、1の\(n\)乗根を使うことにより、\(n\)の約数と関連があることを示すことができました。（といっても、円分多項式の既約性は証明していませんが。）
それでは、この\(x^{n}-1\)は\(\bmod{p}\)でどのように因数分解できるでしょうか？これが、次の問題です。整数係数で因数分解を考える際に整数の範囲だけ考えていてはダメだったように、\(\bmod{p}\)で因数分解する場合も、\(\bmod{p}\)の世界だけ考えていてはなかなか前に進めません。そんなお話です。
