円分多項式のmod pにおける因数分解
今回は、円分多項式が\(\bmod{p}\)でどのように因数分解されるか考えます。一般的に整数係数多項式は整数係数多項式上既約（これ以上因数分解できない）場合でも、\(\bmod{p}\)をすると因数分解できるときがあります。
たとえば、\( x^{2}+1 \) は整数係数多項式としては既約ですが\(\bmod{5}\)では
\[\begin{align} x^{2}+1&=x^{2}-4 & \pmod{5} \\ &=(x-2)(x+2) &\pmod{5} \end{align}\] と因数分解できます。
\(\Phi_{5}(x)\)の\(\bmod{p}\)での因数分解
\(\Phi_{5}(x)=x^{4}+x^{3}+x^{2}+x+1\)が\(\bmod{p}\)でどのように因数分解されるか見てみましょう。手計算で行うのは限界があるので、数式処理ソフトのsageを使いました。sageを使ったのはパソコンにインストールをしなくてもオンライン上で使えるからです。その結果は下記のとおりです。因数分解の型に合わせて色分けしました。
| 素数 | \( x^{4} + x^{3} + x^{2} + x + 1\)の因数分解 |
|---|---|
| \( 3 \) | \( (x^{4} + x^{3} + x^{2} + x + 1)\) |
| \( 5 \) | \( (x -1)^{4} \) |
| \( 7 \) | \( (x^{4} + x^{3} + x^{2} + x + 1) \) |
| \( 11 \) | \( (x + 2) (x + 6) (x + 7) (x + 8) \) |
| \( 13 \) | \( (x^{4} + x^{3} + x^{2} + x + 1) \) |
| \( 17 \) | \( (x^{4} + x^{3} + x^{2} + x + 1) \) |
| \( 19 \) | \( (x^{2} + 5 x + 1) (x^{2} + 15 x + 1) \) |
| \( 23 \) | \( (x^{4} + x^{3} + x^{2} + x + 1) \) |
| \( 29 \) | \( (x^{2} + 6 x + 1) (x^{2} + 24 x + 1) \) |
| \( 31 \) | \( (x + 15) (x + 23) (x + 27) (x + 29) \) |
| \( 37 \) | \( (x^{4} + x^{3} + x^{2} + x + 1) \) |
| \( 41 \) | \( (x + 4) (x + 23) (x + 25) (x + 31) \) |
| \( 43 \) | \( (x^{4} + x^{3} + x^{2} + x + 1) \) |
| \( 47 \) | \( (x^{4} + x^{3} + x^{2} + x + 1) \) |
| \( 53 \) | \( (x^{4} + x^{3} + x^{2} + x + 1) \) |
| \( 59 \) | \( (x^{2} + 26 x + 1) (x^{2} + 34 x + 1) \) |
| \( 61 \) | \( (x + 3) (x + 27) (x + 41) (x + 52) \) |
| \( 67 \) | \( (x^{4} + x^{3} + x^{2} + x + 1) \) |
| \( 71 \) | \( (x + 14) (x + 17) (x + 46) (x + 66) \) |
| \( 73 \) | \( (x^{4} + x^{3} + x^{2} + x + 1) \) |
| \( 79 \) | \( (x^{2} + 30 x + 1) (x^{2} + 50 x + 1) \) |
| \( 83 \) | \( (x^{4} + x^{3} + x^{2} + x + 1) \) |
| \( 89 \) | \( (x^{2} + 10 x + 1) (x^{2} + 80 x + 1) \) |
| \( 97 \) | \( (x^{4} + x^{3} + x^{2} + x + 1) \) |
これを見ると、
赤（重根あり）は\(p=5\)の1つだけ
青（4つの1次式に分解）は\(p\equiv 1\pmod{5}\)のとき
緑（2つの2次式に分解）は\(p\equiv 4\pmod{5}\)のとき
それ以外は既約（因数分解できない）とわかります。
以上をまとめると次の通りです。
円分多項式\(\Phi_{5}(x)\)の\(\bmod{p}\)における因数分解の法則は以下のとおり。
重根をもつのは\(\bmod{5}\)の場合のみ。このとき、\(\Phi_{5}(x)=(x-1)^{4}\pmod{5}\)と因数分解する。
\(p\equiv 1\pmod{5}\)のとき\(\Phi_{5}(x)\)は\(\bmod{p}\)で4つの異なる1次式に分解する。
\(p\equiv 4\pmod{5}\)のとき\(\Phi_{5}(x)\)は\(\bmod{p}\)で2つの異なる2次式に分解する。
\(p\equiv 2,3\pmod{5}\)のとき\(\Phi_{5}(x)\)は\(\bmod{p}\)で既約（因数分解できない）である。
1次式のみに分解することを完全分解するといいます。上の例で、完全分解するのは \(p\equiv 1\pmod{5}\)のときだけと分かります。
ここで、上の\(p\pmod{5}\)の分類は、\(p\)の\( (\mathbb{Z}/5\mathbb{Z})^{\times}\)の中で位数と関連しそうです。
つまり、\(p\equiv 4\pmod{5}\)は、\(\bmod{5}\)で２乗して初めて１になる素数と考えることができます。
また、\(p\equiv 2,3\pmod{5}\)は、\(\bmod{5}\)で4乗してはじめて1になる素数と考えることができます。
以上より上の2．以下は次のように書くことができます。
\(p\ne 5\)のとき\(p\)の\(\bmod{5}\)での位数を\(f\)とするとき（つまり\(f\)乗してはじめて1になるとするとき）\(\Phi_{5}(x)\)は\(\bmod{p}\)で\(f\)次式に分解する。
\(\Phi_{7}(x)\)の\(\bmod{p}\)での因数分解
同様に\(\Phi_{7}(x)=x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1\)を\(\bmod{p}\)で因数分解してみます。 やはりsageを使います。分かりやすいように、表の中に素数の\(\bmod{7}\)を記載しました。
| 素数 | \(\bmod{7}\) | \( x^{6} + x^{5} + x^{4} + x^{3} + x^{2} + x + 1 \)の因数分解 |
|---|---|---|
| \( 3 \) | \( 3 \) | \( (x^{6} + x^{5} + x^{4} + x^{3} + x^{2} + x + 1) \) |
| \( 5 \) | \( 5 \) | \( (x^{6} + x^{5} + x^{4} + x^{3} + x^{2} + x + 1) \) |
| \( 7 \) | \( 0 \) | \( (x -1)^{6} \) |
| \( 11 \) | \( 4 \) | \( (x^{3} + 5 x^{2} + 4 x + 10) (x^{3} + 7 x^{2} + 6 x + 10) \) |
| \( 13 \) | \( 6 \) | \( (x^{2} + 3 x + 1) (x^{2} + 5 x + 1) (x^{2} + 6 x + 1) \) |
| \( 17 \) | \( 3 \) | \( (x^{6} + x^{5} + x^{4} + x^{3} + x^{2} + x + 1) \) |
| \( 19 \) | \( 5 \) | \( (x^{6} + x^{5} + x^{4} + x^{3} + x^{2} + x + 1) \) |
| \( 23 \) | \( 2 \) | \( (x^{3} + 10 x^{2} + 9 x + 22) (x^{3} + 14 x^{2} + 13 x + 22) \) |
| \( 29 \) | \( 1 \) | \( (x + 4) (x + 5) (x + 6) (x + 9) (x + 13) (x + 22) \) |
| \( 31 \) | \( 3 \) | \( (x^{6} + x^{5} + x^{4} + x^{3} + x^{2} + x + 1) \) |
| \( 37 \) | \( 2 \) | \( (x^{3} + 9 x^{2} + 8 x + 36) (x^{3} + 29 x^{2} + 28 x + 36) \) |
| \( 41 \) | \( 6 \) | \( (x^{2} + 4 x + 1) (x^{2} + 11 x + 1) (x^{2} + 27 x + 1) \) |
| \( 43 \) | \( 1 \) | \( (x + 2) (x + 8) (x + 22) (x + 27) (x + 32) (x + 39) \) |
| \( 47 \) | \( 5 \) | \( (x^{6} + x^{5} + x^{4} + x^{3} + x^{2} + x + 1) \) |
| \( 53 \) | \( 4 \) | \( (x^{3} + 15 x^{2} + 14 x + 52) (x^{3} + 39 x^{2} + 38 x + 52) \) |
| \( 59 \) | \( 3 \) | \( (x^{6} + x^{5} + x^{4} + x^{3} + x^{2} + x + 1) \) |
| \( 61 \) | \( 5 \) | \( (x^{6} + x^{5} + x^{4} + x^{3} + x^{2} + x + 1) \) |
| \( 67 \) | \( 4 \) | \( (x^{3} + 12 x^{2} + 11 x + 66) (x^{3} + 56 x^{2} + 55 x + 66) \) |
| \( 71 \) | \( 1 \) | \( (x + 23) (x + 26) (x + 34) (x + 39) (x + 41) (x + 51) \) |
| \( 73 \) | \( 3 \) | \( (x^{6} + x^{5} + x^{4} + x^{3} + x^{2} + x + 1) \) |
| \( 79 \) | \( 2 \) | \( (x^{3} + 13 x^{2} + 12 x + 78) (x^{3} + 67 x^{2} + 66 x + 78) \) |
| \( 83 \) | \( 6 \) | \( (x^{2} + 26 x + 1) (x^{2} + 68 x + 1) (x^{2} + 73 x + 1) \) |
| \( 89 \) | \( 5 \) | \( (x^{6} + x^{5} + x^{4} + x^{3} + x^{2} + x + 1) \) |
| \( 97 \) | \( 6 \) | \( (x^{2} + 56 x + 1) (x^{2} + 67 x + 1) (x^{2} + 72 x + 1) \) |
これを同じようにまとめると次の通りになります。
円分多項式\(\Phi_{7}(x)\)の\(\bmod{p}\)における因数分解の法則は以下のとおり。
重根をもつのは\(\bmod{7}\)の場合のみ。このとき、\(\Phi_{7}(x)=(x-1)^{6}\pmod{7}\)と因数分解する。
\(p\equiv 1\pmod{7}\)のとき\(\Phi_{7}(x)\)は\(\bmod{p}\)で6つの異なる1次式に分解する。つまり、完全分解する。
\(p\equiv 6\pmod{7}\)のとき\(\Phi_{7}(x)\)は\(\bmod{p}\)で3つの異なる2次式に分解する。
\(p\equiv 2,4\pmod{7}\)のとき\(\Phi_{7}(x)\)は\(\bmod{p}\)で2つの異なる3次式に分解する。
\(p\equiv 3,5\pmod{7}\)のとき\(\Phi_{7}(x)\)は\(\bmod{p}\)で既約（因分解できない）である。
\(\bmod{5}\)の場合と同様に、\( (\mathbb{Z}/7\mathbb{Z})^{\times}\)の中で位数で場合わけができそうです。
つまり、\(p\equiv 6\pmod{7}\)は、\(\bmod{7}\)で２乗して初めて１になる素数と考えることができます。また、\(p\equiv 2,4\pmod{7}\)は、\(\bmod{7}\)で3乗してはじめて1になる素数と考えることができ、\(p\equiv 3,5\pmod{7}\)は、\(\bmod{7}\)で6乗してはじめて1になる素数と考えることができます。
以上より
\(p\ne 7\)のとき\(p\)の\(\bmod{7}\)での位数を\(f\)とするとき（つまり\(f\)乗してはじめて1になるとするとき）\(\Phi_{7}(x)\)は\(\bmod{p}\)で\(f\)次式に分解する。
一般の素数\(q\)の場合
\(q\)を奇素数とするとき、円分多項式\(\Phi_{q}(x)\)は\(\bmod{p}\)でどのように分解されるでしょうか。上で見た\(q=5,7\)の場合から想像すると、重根を持つのは、\(p=q\)の場合に限定されそうです。
また、次のことが予想されます。
\(p\ne q\)のとき\(p\)の\(\bmod{q}\)での位数を\(f\)とするとき（つまり\(f\)乗してはじめて1になるとするとき）\(\Phi_{q}(x)\)は\(\bmod{q}\)で\(f\)次式に分解する。
つまり、これは、
円分多項式\(\Phi_{q}(x)\)の\(\bmod{p}\)での分解
と
\(p\)の\( (\mathbb{Z}/q\mathbb{Z})^{\times}\)の中での位数
が関連していることを示しています。
ここで、modが入れ替わっていることに注意しましょう。円分多項式\(\Phi_{q}(x)\)の\(\bmod{p}\)での分解は、もちろん\(\bmod{p}\)の世界です。他方、\( (\mathbb{Z}/q\mathbb{Z})^{\times}\)は\(\bmod{q}\)の世界です。このように、円分多項式の世界では、modが入れ替わってしまうのです。なぜ、このようなことになるのかについては、次々回以降に解説するとして、これが如何に異例で、美しいことなのか次回解説します。
これが、如何に異例なことなのかは、例えば\(x^{3}=2\)や\(x^{4}=2\)を\(\bmod{p}\)で因数分解することで分かります。次回は、きれいにならない事例として\(x^{3}=2\)や\(x^{4}=2\)を\(\bmod{p}\)で因数分解してみます。
