エレファント・コンピューティング調査報告

極限に関する順序を論理プログラミングの手法を使って指定することを目指すブロクです。

群論の計算(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 となります。

 1 \le k\le n である  k に対して  \zeta_n^{k} は異なるため  \Phi _{n} \ | \ f となります。 f は既約多項式 なので  \Phi _{n} は既約多項式となります。[証明終わり]