2016/02/03

円分多項式とその性質

分野: 整数問題  レベル: 数学オリンピック

$\zeta_n=e^{\frac{2\pi i}{n}}=\cos \dfrac{2\pi}{n}+i\sin\dfrac{2\pi}{n}$($n$ 乗して $1$ になる数のうちの一つ)とおく。多項式
$F_n(x)=\displaystyle\prod_{k\in A_n} (x-\zeta_n^k)$
を円分多項式(円周等分多項式)と言う。

ただし,$A_n$ は $1$ 以上 $n$ 以下の整数で,$n$ と互いに素なもの全体の集合です。

具体例

$\zeta_1=1$,$F_1(x)=x-1$
$\zeta_2=-1$,$F_2(x)=x+1$
$\zeta_3=\dfrac{-1+\sqrt{3}i}{2}$,$F_3(x)=(x-\zeta_3)(x-\zeta_3^2)=x^2+x+1$
$\zeta_4=i$,$F_4(x)=(x-\zeta_4)(x-\zeta_4^3)=x^2+1$

円分多項式は整数係数多項式であることが証明されています。また,$F_n(x)$ は最高次の係数が $1$ である $\phi(n)$ 次多項式です。($\phi(n)$ はオイラーのファイ関数

素数に対する円分多項式

素数 $p$ に対する円分多項式は簡単に求まります。

$p$ が素数のとき,$F_p(x)=x^{p-1}+x^{p-2}+\cdots +x+1$

確かに $F_2(x)=x+1$,$F_3(x)=x^2+x+1$ となっています。

証明

円分多項式の定義より,
$F_p(x)=\displaystyle\prod_{k=1}^{p-1}(x-\zeta_p^k)$
である。これと,
$x^p-1=\displaystyle\prod_{k=1}^{p}(x-\zeta_p^k)$ より,
$F_p(x)=\dfrac{x^p-1}{x-1}=x^{p-1}+x^{p-2}+\cdots +x+1$

ただし,最後の等号は因数分解公式(n乗の差、和)

性質

任意の正の整数 $n$ に対して $x^n-1=\displaystyle\prod_{d\mid n}F_d(x)$

右辺の積は,$d$ が $n$ の約数全体を動くという意味です。例えば,$n=4$ の場合,
$F_1(x)F_2(x)F_4(x)=(x-1)(x+1)(x^2+1)=x^4-1$
という式になります。

証明の概略

左辺は,$\displaystyle\prod_{k=1}^n(x-\zeta_n^k)$ である。
「$n$ と $k$ の最大公約数が $\dfrac{n}{d}$」という条件を満たす $k$ の部分のみの積が $F_d(x)$ であることを示せばよい(略)。

既約性

任意の正の整数 $n$ に対して $F_n(x)$ は既約である。つまり,$P(x)Q(x)=F_n(x)$ となるような整数係数多項式 $P(x)$,$Q(x)$ は存在しない。

円分多項式の著しい性質です。一般の場合の証明は少し大変ですが,$n$ が素数の場合は比較的簡単です。

具体的には,アイゼンシュタインの定理と平行移動を用います。
アイゼンシュタインの定理の例2で
$F_5(x)=x^4+x^3+x^2+x+1$ が既約であることを証明しています。一般の素数 $p$ に対しても全く同様に証明できます。

$n\leq 104$ において円分多項式の係数は $0,\pm 1$ のいずれかですが,$F_{105}(x)$ の係数には $-2$ が現れるようです。
分野: 整数問題  レベル: 数学オリンピック