群論の計算(26) - エレファント・コンピューティング調査報告

円分多項式

$1$ の $n$ 乗根

$x^n - 1 = 0$ の解を $1$ の $n$ 乗根と呼びます。

$\displaystyle \zeta_n = e^{\frac {2\pi i}{n}} = \cos {\frac {2\pi }{n}}+i\sin {\frac {2\pi }{n}}$ とおくと $1$ の $n$ 乗根は $n$ 個存在し、それらは $1, \zeta_n , \zeta_n^2 , \cdots , \zeta_n^{n-1}$ となります。
$x^n - 1 = (x - 1) (x - \zeta_n) (x - \zeta_n^2) \cdots (x - \zeta_n^{n-1})$
が成り立ちます。( $1, \zeta_n , \zeta_n^2 , \cdots , \zeta_n^{n-1}$ は異なる複素数ですべて $n$ 乗すると $1$ になることからこのことがわかります。)

$1$ の $n$ 乗根の中で $n$ 乗して初めて $1$ になる( $m \lt n$ である $m$ では $m$ 乗しても $1$ にならない)ものを $1$ の原始 $n$ 乗根と呼びます。

$m$ を $n$ と互いに素な自然数とすると $\zeta_n^m$ は $1$ の原始 $n$ 乗根となります。逆に $\zeta_n^m$ を $1$ の原始 $n$ 乗根とすると $m$ は $n$ と互いに素となります。 $n$ と互いに素となる $1 \le m \le n$ である自然数 $m$ の個数を $\varphi(n)$ と表します。 $\varphi$ をオイラーの $\varphi$ 関数と呼びます。 $1$ の原始 $n$ 乗根の個数は $\varphi(n)$ となります。

円分多項式

$m$ と $n$ の最大公約数を $(m, n)$ と表します。 $m$ と $n$ が互いに素であることを $(m, n) = 1$ と表します。

円分多項式 $\Phi _{n}$ を $n$ と互いに素なすべての $k$ ( $1 \le k \le n$ )に対する $x -\zeta_n^k$ の積
$\displaystyle \Phi _{n}(x)=\prod _{\stackrel {(k,n)=1}{1\leq k\leq n}}\left(x-e^{\frac{2\pi i}{n}k}\right)$
と定義します。

$n$ が素数のとき、円分多項式 $\Phi_n(x)$ は
$\Phi_n(x) = x^{n-1} + x^{n-2} + \cdots + x + 1$
となります。

[証明] $n$ が素数なので円分多項式 $\Phi_n(x)$ はすべての $k$ ( $1 \le k \le n-1$ )に対する $x -\zeta_n^k$ の積
$\Phi_n(x) = (x - 1) (x - \zeta_n) (x - \zeta_n^2) \cdots (x - \zeta_n^{n-1})$
となります。
$\begin{eqnarray*} x^n - 1 & = & (x - 1) (x - \zeta_n) (x - \zeta_n^2) \cdots (x - \zeta_n^{n-1}) \\ & = & (x - 1)(x^{n-1} + x^{n-2} + \cdots + x + 1) \end{eqnarray*}$
であることから
$\Phi_n(x) = x^{n-1} + x^{n-2} + \cdots + x + 1$
となります。[証明終わり]

$1 \le j \le n$ のとき $\displaystyle \sum_{k=0}^{n-1} \zeta_n^{kj} = 1 + \zeta_n^{j} + \zeta_n^{2j} + \cdots \zeta_n^{(n-1)j} = 0$

[証明]
$x^{n-1} + x^{n-2} + \cdots + x + 1 = (x - \zeta_n) (x - \zeta_n^2) \cdots (x - \zeta_n^{n-1})$
に $x =\zeta_n^j$ を代入すると主張が成り立ちます。[証明終わり]

以下の定理の証明で

二項係数 $\displaystyle \binom{n}{k} = \frac{n!}{k!(n-k)!}$
階乗 $n! = 1 \cdot 2 \cdot \cdots \cdot n$

を使います。二項係数 $\displaystyle \binom{n}{k} = \binom{n}{n-k}$ は $(x+1)^n$ の $x^k$ の係数となります。
$\displaystyle (x+1)^n = \binom{n}{0} x^n + \binom{n}{1} x^{n-1} + \cdots + \binom{n}{n-1} x + \binom{n}{n}$
$\displaystyle \binom{p}{1} = \binom{p}{p-1} = p$ となります。
$p$ を素数、 $1 \le k \le p-1$ とすると $\displaystyle \binom{p}{k} = \frac{p!}{k!(p-k)!}$ の分子は $p$ で割り切れて、分母は $p$ で割り切れないので、 $\displaystyle \binom{p}{k}$ は $p$ の倍数となります。

$p$ を素数とするとき
$f(x) = x^{p-1} + x^{p-2} + \cdots + x + 1$
は整数係数の範囲で既約多項式となります。

[証明] $f(x) = \cfrac{x^p-1}{x-1}$ より
$\displaystyle f(x+1) = \cfrac{(x+p)^p-1}{x} = x^{p-1} + \binom{p}{1} x^{p-2} + \cdots + \binom{p}{p-2} x + \binom{p}{p-1}$
となります。 $\displaystyle \binom{p}{k}$ は $1 \le k \le p-1$ のとき $p$ の倍数となり $\displaystyle \binom{p}{p-1} = p$ なのでアイゼンシュタインの既約判定法の条件を満たします。よって $f(x+1)$ は既約多項式となります。
$f(x) = g(x)h(x)$ とすると $f(x+1) = g(x+1)h(x+1)$ となって $g(x+1)$ または $h(x+1)$ のどちらかの次数は $0$ となります。よって $g(x)$ または $h(x)$ のどちらかの次数は $0$ となるので $f(x)$ は既約多項式となります。[証明終わり]

整数係数の多項式 $h$ の係数がすべて素数 $p$ で割り切れるとします。整数係数の範囲で $h = fg$ と因数分解されているとき $f$ 、 $g$ のいずれか一方はすべての係数が $p$ で割り切れます。

[証明] $f = a_n X^n + \cdots + a_0 \in \mathbb{Z}[X]$ 、 $g = b_m X^m + \cdots + b_0 \in \mathbb{Z}[X]$ 、 $fg \in p \mathbb{Z}[X]$ とします。

$n + m = 0$ のとき $fg = a_0 b_0 \in p \mathbb{Z}[X]$ となって $a_0 b_0 \in p \mathbb{Z}$ となります。 $p$ は素数なので $f = a_0 \in p \mathbb{Z}$ または $g = b_0 \in p \mathbb{Z}$ となります。よって $f \in p \mathbb{Z}[X]$ または $g \in p \mathbb{Z}[X]$ となります。

$n + m - 1$ のとき成り立っていると仮定します。 $fg = a_n b_m X^{n+m} + \cdots + a_0 b_0 \in p \mathbb{Z}[X]$ より $a_n b_m \in p \mathbb{Z}$ となり $a_n \in p \mathbb{Z}$ または $b_m \in p \mathbb{Z}$ となります。 $a_n \in p \mathbb{Z}$ のとき $h = f - a_n X^n$ とおくと $hg = fg - a_n X^n g \in p \mathbb{Z}[X]$ となって帰納法の仮定より $h \in p \mathbb{Z}[X]$ または $g \in p \mathbb{Z}[X]$ となります。 $h \in p \mathbb{Z}[X]$ のときは $f = h + a_n X^n \in p \mathbb{Z}[X]$ となります。 $b_m \in p \mathbb{Z}$ のときも同様となります。[証明終わり]

整数係数の多項式 $f$ が有理数係数で因数分解できれば、整数係数でも因数分解できます。

[証明] $f = gh$ 、 $g, h \in \mathbb{Q}[x]$ とします。 $g$ の係数の分母の最小公倍数を $a \in \mathbb{Z}$ 、 $h$ の係数の分母の最小公倍数を $b \in \mathbb{Z}$ とおきます。 $g' = ag \in \mathbb{Z}[x]$ 、 $h' = bh \in \mathbb{Z}[x]$ とおきます。 $abf = g'h'$ となります。 $ab = p_1 p_2 \cdots p_n$ となる素数 $p_1, p_2, \cdots , p_n$ が存在します。 $p_i$ は $g'$ を割るか $h'$ を割るかどちらかとなります。両辺を $p_i$ で割ると $p_1 p_2 \cdots p_{n-1} f = g''h''$ という $p_i$ が1つ減った形にすることができます。これを $p_i$ がなくなるまで繰り返すと $f = uv$ ( $u, v \in \mathbb{Z}[x]$ )という形になります。このとき $g = cu$ 、 $h = \frac{1}{c}v$ となる $c \in \mathbb{Q}$ が存在します。[証明終わり]

$p$ が素数のとき $\mathbb{F}_p = \mathbb{Z} / p \mathbb{Z}$ は体となります。 $\mathbb{F}_p^\times = \mathbb{F}_p \setminus 0$ ( $0$ の剰余類を除いた集合)は積に関して位数 $p-1$ の群となります。

$a$ を整数、 $p$ を素数とするとき $a^p \equiv a \ ( \operatorname{mod} p)$ となります。

[証明] $\mathbb{F}_p^\times$ は積に関して位数 $p-1$ の群となるので、この群での $a$ の剰余類の位数は $p-1$ の約数となります。よって $a^{p-1} \equiv 1 \ ( \operatorname{mod} p)$ となって $a^{p} \equiv a \ ( \operatorname{mod} p)$ となります( $a \not \equiv 0 \ ( \operatorname{mod} p)$ のとき)。 $a \equiv 0 \ ( \operatorname{mod} p)$ のときも $a^{p} \equiv a \ ( \operatorname{mod} p)$ となります。[証明終わり]

$a_1, a_2, \cdots , a_n$ を整数、 $p$ を素数とするとき
$(a_1 + a_2 + \cdots + a_n)^p \equiv a_1^p + a_2^p + \cdots + a_n^p \ ( \operatorname{mod} p)$
となります。

[証明] 上の結果より
$(a_1 + a_2 + \cdots + a_n)^p \equiv a_1 + a_2 + \cdots + a_n \equiv a_1^p + a_2^p + \cdots + a_n^p \ ( \operatorname{mod} p)$
となります。[証明終わり]

$R$ 、 $S$ を環、 $\psi : R \to S$ を環の準同型とします。このとき任意の $s \in S$ に対して環の準同型 $\sigma_s : R [ X ] \to S$ で

任意の $a \in R$ に対して $\sigma_s (a) = \psi(a)$
$\sigma_s (X) = s$

を満たすものが一意的に存在します。 $f \in R [ X ]$ に対して $\sigma_s(f)$ を $f(s)$ と表します。 $\sigma_s$ を代入射と呼びます。

$R$ を環とします。 $a \in R$ で生成される $R$ のイデアルを $(a)$ と表します。 $a \in R$ と $b \in R$ で生成される $R$ のイデアルを $(a, b) = (a) + (b)$ と表します。 $a \in R$ と $b \in R$ に対して $b \in (a)$ であるとき $a \ | \ b$ と表します。

$R$ が単項イデアル整域であるとき $R [ X ]$ は単項イデアル整域となります。

$R$ を単項イデアル整域、 $a$ を $R$ の既約元とすると $(a)$ は $R$ の極大イデアルとなります。

$R$ を単項イデアル整域、 $a$ を $R$ の既約元、 $b \in R$ とすると $(a, b) = (1)$ または $b \in (a)$ となります。

$\zeta_n$ を $1$ の原始 $n$ 乗根とします。 $f \in \mathbb{Q}[X]$ を $\mathbb{Q}$ 上の既約多項式で、 $f(\zeta_n) = 0$ であるものとします。このとき $n$ と互いに素な素数 $p$ に対して $f(\zeta_n^p) = 0$ となります。

[証明] $h = X^n - 1 \in \mathbb{Q}[X]$ とおくと $h(\zeta_n) = 0$ となります。 $\mathbb{Q}[X]$ は単項イデアル整域、 $f$ は $\mathbb{Q}[X]$ の既約多項式であるから $h \in (f)$ または $(f, h) = (1)$ となります。 $(f, h) = (1)$ とすると $1 \in (f, h)$ となるので $1 = fu + hv$ となる $u, v \in \mathbb{Q}[X]$ が存在します。 $1 = f(\zeta_n)u(\zeta_n) + h(\zeta_n)v(\zeta_n) = 0$ となってこれは矛盾となります。よって $h \in (f)$ となります。

$h = fg$ となる $g \in \mathbb{Q}[X]$ が存在します。このとき $af, \frac{1}{a}g \in \mathbb{Z}[X]$ となる $a \in \mathbb{Q}$ が存在します。 $af, \frac{1}{a}g$ を $f, g$ と書くことにより $f, g \in \mathbb{Z}[X]$ と考えることができます。

$h(\zeta_n^p) = 0$ となるので $f(\zeta_n^p) = 0$ または $g(\zeta_n^p) = 0$ となります。

$g = a_m X^m + a_{m-1} X^{m-1} + \cdots + a_{1} X + a_{0}$ とおくと
$\begin{eqnarray*} g^p & = & (a_m X^m + a_{m-1} X^{m-1} + \cdots + a_{1} X + a_{0})^p \\ & \in & ( a_m^p X^{mp} + a_{m-1}^p X^{(m-1)p} + \cdots + a_{1}^p X^p + a_{0}^p ) + p \mathbb{Z}[X] \\ & = & ( a_m X^{mp} + a_{m-1} X^{(m-1)p} + \cdots + a_{1} X^p + a_{0} ) + p \mathbb{Z}[X] \\ & = & g(X^p) + p \mathbb{Z}[X] \end{eqnarray*}$
となります。

$g(\zeta_n^p) = 0$ と仮定すると $g^p(\zeta_n) \in g(\zeta_n^p) + p \mathbb{Z}[\zeta_n] = p \mathbb{Z}[\zeta_n]$ となります。 $\mathbb{Q}[X]$ は単項イデアル整域、 $f$ は $\mathbb{Q}[X]$ の既約多項式であるから $g^p \in (f)$ または $(f, g^p) = (1)$ となります。 $(f, g^p) = (1)$ とすると $1 \in (f, g^p)$ となるので $1 = fs + g^pt$ となる $s, t \in \mathbb{Q}[X]$ が存在します。 $1 = f(\zeta_n)s(\zeta_n) + g^p(\zeta_n)t(\zeta_n) \in p \mathbb{Z}[\zeta_n]$ となってこれは矛盾となります。よって $g^p \in (f)$ となります。

$f$ は既約多項式なので $(f)$ は素イデアルとなり $g \in (f)$ となります。 $h = fg \in (f^2)$ となって $h$ は重根を持つことになりますが $h = X^n - 1$ は重根を持たないので矛盾が生じます。

よって $f(\zeta_n^p) = 0$ となります。[証明終わり]

円分多項式 $\Phi_n$ は $\mathbb{Q}$ 上既約となります。

[証明] 円分多項式 $\Phi _{n}$ は
$\displaystyle \Phi _{n}=\prod _{\stackrel {(k,n)=1}{1\leq k\leq n}}\left(X-\zeta_n^k\right)$
と定義されています。

$X^n - 1$ の既約な因子の1つは $1$ の原始 $n$ 乗根が根となります。そのようなものを $f$ とおきます。 $f \in \mathbb{Q}$ は既約多項式で $f(\zeta_n) = 0$ であるものとなります。

$1 \le k\le n$ 、 $(k, n) = 1$ とします。 $k = p_1 p_2 \cdots p_m$ となる素数 $p_1, p_2, \cdots , p_m$ が存在します。 $p_1, p_2, \cdots , p_m$ は $n$ と互いに素となります。

前の定理より $f(\zeta_n^{p_i}) = 0$ となります。 $(p_i, n) = 1$ より $\zeta_n^{p_i}$ も $1$ の原始 $n$ 乗根となります。よって $i = 1, 2, \cdots , m$ と繰り返すことにより $f(\zeta_n^{k}) = 0$ となります。