円分多項式
1のべき根
正の整数 $n>0$ に対して、$n$乗して1となる数、つまり方程式
$$x^n-1=0$$
の解を$1$の$n$乗根という。
たとえば$1$の$4$乗根は $\pm 1, \pm i$ で与えられる。また$1$の$6$乗根は
$$x^6-1=(x-1)(x+1)(x^2-x+1)(x^2+x+1)=0$$
の解なので、$1, (\pm 1\pm\sqrt{-3})/2$ で与えられる。
$\alpha$ が$1$の$n$乗根のとき
$$\abs{\alpha}^n=\abs{\alpha^n}=1$$
だから$\abs{\alpha}=1$となる。とくに実数の$1$のべき根は $\pm 1$ しかない。
$1$の$n$乗根は
$$\tag{1.1} e^{2k\pi/n}=\cos\frac{2k\pi}{n}+i\sin\frac{2k\pi}{n} \quad (k\in\Z) \label{eq11}$$
の形のものと一致する。実際 $\alpha$ が$1$の$n$乗根ならば $\abs{\alpha}=1$ なので $\alpha=\cos\theta+i\sin\theta$ とかけるが、
$$\alpha^n=\cos(n\theta)+i\sin(n\theta)=1$$
より $n\theta=2k\pi$ となる $k\in\Z$ がとれる。
$d\mid n$ ならば、$1$の$d$乗根は$1$の$n$乗根ともなる。$1$の$n$乗根のうち、$n$乗してはじめて$1$となるものを$1$の原始$n$乗根という。たとえば
$$\frac{1\pm \sqrt{-3}}{2}=\cos\frac{\pi}{3}\pm \sin\frac{\pi}{3}=e^{\pi i/3}$$
は$1$の原始$6$乗根である。一方
$$\pm 1, \frac{-1\pm \sqrt{-3}}{2}=\cos\frac{\pi}{3}\pm \sin\frac{\pi}{3}=e^{\pm 2\pi i/3}$$
は$1$の$6$乗根であるが原始$6$乗根ではない。$1$の原始$6$乗根は$2$次方程式 $x^2-x+1=0$ の解と一致する。
$\zeta$ が$1$の原始$n$乗根となるための必要十分条件は
$$\zeta=e^{2k\pi/n}=\cos\frac{2k\pi}{n}+i\sin\frac{2k\pi}{n}, \gcd(k, n)=1$$
となる整数 $k$ が存在することである。実際 \eqref{eq11} のような整数 $k$ をとると
倍数と約数:定理6
より
$$\zeta^d=1\Longleftrightarrow n\mid (kd)\Longleftrightarrow n/\gcd(k, n)\mid d$$
となる。
円分多項式
一般に $1$ の原始 $n$ 乗根をちょうど解に持ち、なおかつ重解を持たない多項式を円分多項式という。つまり
$$\prod_{1\leq k\leq n-1, \gcd(k, n)=1} (X-\zeta^k)$$
が$1$の原始$n$乗根に対する円分多項式である。したがって、$1$の原始$n$乗根に対する円分多項式は$\varphi(n)$次の多項式である。たとえば$1$の原始$6$乗根に対する円分多項式は $X^2-X+1$ であたえられる。
円分多項式の重要な性質は、円分多項式は必ず整数係数の多項式となることである。本節では、円分多項式の定義から直接示すのではなく、再帰的に整数係数の多項式の列を構成し、それが円分多項式に一致することを示す方法を取る。
まず、$1$の $n$ 乗根に対応する $X^n-1$ の形の多項式の性質を調べることから始める。次の性質が成り立つ。
- $\gcd(X^m-1, X^n-1)=X^{\gcd(m, n)}-1$,
- $\gcd((X^m-1)/(X^{\gcd(m, n)}-1), (X^n-1)/(X^{\gcd(m, n)}-1))=1$,
- $d\mid m$ ならば $\gcd((X^m-1)/(X^d-1), X^d-1)=1$, さらに $(X^m-1)/(X^d-1)\equiv (m/d)\pmod{X^d-1}$.
- $\gcd((X^m-1)/(X^{\gcd(m, n)}-1), X^n-1)=1,$
- $X^n-1$ は平方因数をもたない。
これらは、 $\C$ 上でも $\Z$ 上でも成り立つ。
- $m=an+r (0\leq r< n)$ とおくと
$$X^m-1=X^{an+r}-1=X^r(X^{an}-1)+X^r-1$$
となるが、
$$X^{an}-1=(X^n-1)(X^{(a-1)n}+X^{(a-2)n}+ \cdots +X+1)$$
と因数分解できるから $X^m-1$ を $X^n-1$ で割った余りは $X^r-1$ に一致する。よって 多項式のEuclidの互除法 と 自然数のEuclidの互除法 より $\C$ 上で
$$\gcd(X^m-1, X^n-1)=X^{\gcd(m, n)}-1$$
となり（右辺は $\Z$ においても $X^m-1, X^n-1$ を割り切るので、$\Z$ 上でもこれが成り立つ）、(i) が導かれる。 - 1の両辺を $X^{\gcd(m, n)}-1$ で割ると (ii) が導かれる。
- $m=kd$ とおくと $\Z$ 上で（よって $\C$ 上でも）
$$\frac{X^m-1}{X^d-1}=X^{(k-1)d}+X^{(k-2)d}\cdots +1\equiv k\pmod{X^d-1}$$
となるから、$(X^m-1)/(X^d-1)$ と $X^d-1$ をともに割り切る多項式は定数しかないので、(iii) が導かれる。 - (iii) より
$$\gcd\left(\frac{X^m-1}{X^{\gcd(m, n)}-1}, X^{\gcd(m, n)}-1\right)=1$$
である。一方 (ii) より
$$\gcd\left(\frac{X^m-1}{X^{\gcd(m, n)}-1}, \frac{X^n-1}{X^{\gcd(m, n)}-1}\right)=1$$
であるから、 Gaussの補題 より (iv) が従う。 - $\C$ 上で
$$\frac{d}{dx}(X^n-1)=nX^{n-1}, \gcd(X^n-1, nX^{n-1})=1$$
となるから、多項式の微分の性質から $X^n-1$ は平方因数をもたない。
$\Phi_n(X)\in \Q(X) (n=0, 1, \ldots)$ を漸化式
$$\begin{split}
\Phi_1(X)= & X-1, \\
\Phi_n(X)= & \frac{X^n-1}{\prod_{d< n, d\mid n}\Phi_d(X)}
\end{split}$$
により定義する。すると、 $\Phi_n(X)$ はいずれも整数係数の多項式であることが示される。より正確に、次の事実がわかる。
すべての正の整数 $n$ に対し、$\Phi_n(X)$ はモニックな整数係数の多項式で、次の関係が成り立つ。
$$\tag{2.1} \Phi_n(X)=\Phi_{n/p}(X^p)/\Phi_{n/p}(X)\quad (p\mid\mid n),\label{eq21}$$
$$\Phi_n(X)=\Phi_{n/p}(X^p)\quad (p^2 \mid n),$$
$$\gcd(\Phi_m(X), X^n-1)>1 \Longrightarrow m\mid n. \label{eq22} \tag{2.2}$$
まず、数学的帰納法から、\eqref{eq21}, \eqref{eq22}を確かめる。 $n$ がより小さいときに\eqref{eq21}, \eqref{eq22}が正しいと仮定し、$n=mp$（$p$ は素数）とおく。
$\gcd(m, p)=1$ のとき、$d\mid m$ ならば $d, p$ も互に素なので
$$\Phi_m(X^p)=\frac{X^{mp}-1}{\prod_{d\mid m, d< m} \Phi_d(X^p)}=\frac{X^{mp}-1}{\prod_{d\mid m, d< m}(\Phi_d(X)\Phi_{dp}(X))}=\frac{X^{mp}-1}{\prod_{d\mid mp, d\neq m, mp}\Phi_d(X)}$$
より
$$\frac{\Phi_m(X^p)}{\Phi_m(X)}=\frac{X^{mp}-1}{\prod_{d\mid mp, d< mp} \Phi_d(X)}=\Phi_{mp}(X)$$
となる。よって\eqref{eq21}は $n=mp$ に対して成り立つ。
一方 $p\mid m$ のとき $m=\ell p^k, \gcd(\ell, p)=1$ とおくと
$$\prod_{d\mid m, d< m} \Phi_d(X^p)=\left(\prod_{d\mid\ell, d<\ell}\prod_{s=0}^k\Phi_{dp^s}(X^p)\right)\left(\prod_{s=0}^{k-1}\Phi_{\ell p^s}(X^p)\right)$$
であるが
$$\prod_{s=0}^k\Phi_{dp^s}(X^p)=\Phi_d(X)\prod_{s=0}^k \Phi_{dp^{s+1}}(X)=\prod_{s=0}^{k+1}\Phi_{dp^s}(X)$$
であることから
$$\prod_{d\mid m, d< m} \Phi_d(X^p)=\left(\prod_{d\mid\ell, d<\ell}\prod_{s=0}^{k+1}\Phi_{dp^s}(X)\right)\left(\prod_{s=0}^k(\Phi_{\ell p^s}(X))\right)=\prod_{d\mid mp, d< mp}\Phi_d(X)$$
である。よって
$$\Phi_m(X^p)=\frac{X^{mp}-1}{\prod_{d\mid m, d< m} \Phi_d(X^p)}=\frac{X^{mp}-1}{\prod_{d\mid mp, d< mp}\Phi_d(X)}=\Phi_{mp}(X)$$
より、\eqref{eq22}も $n=mp$ に対して成り立つ。
よって、\eqref{eq21}, \eqref{eq22} はすべての正の整数 $n$ に対して成り立つ。
つぎに $\Phi_n(X)$ はいずれもモニックな整数係数の多項式であることを数学的帰納法によって示す。 $n=mp$（$p$ は素数）とし $m$ の約数 $d$ に対して $\Phi_d(X)$ はモニックな整数係数の多項式であると仮定する。
$p\mid m$ のときは\eqref{eq22}から $\Phi_n(X)=\Phi_m(X^p)$ はモニックな整数係数の多項式である。
$\gcd(m, p)=1$ のとき $\Phi_m(X^p)/\Phi_m(X)$ がモニックな整数係数の多項式となることを示す。
定義より
$$\tag{2.3} \Phi_m(X) | (X^m-1) | (X^{mp}-1)\label{eq23}$$
はすぐにわかる。ここで $d< m$ を $m$ の約数とする。
$\gcd (m, p)=1$ より $dp$ は $m$ の倍数ではない。よって
命題1
の (iv) より
$\gcd (\Phi_m(X), X^{dp}-1)=1$ である。
$$\Phi_d(X^p)=(X^p)^d-1=X^{dp}-1$$ より
$$\tag{2.4} \gcd (\Phi_m(X), \Phi_d(X^p))=1\label{eq24}$$
である。\eqref{eq23}, \eqref{eq24}から、
多項式の一意分解
より $\Phi_m(X)\mid \Phi_m(X^p)$ となる。
$\Phi_m(X), \Phi_m(X^p)$ はともにモニックな整数係数の多項式だから、$\Phi_m(X^p)/\Phi_m(X)$ もモニックな整数係数の多項式である。
最後に、$m\mid n$ でないとき $\gcd(m, n)< m$ より $\Phi_m(X)$ は $(X^m-1)/(X^{\gcd(m, n)}-1)$ の因数となる。よって上記の
命題1
の (iv) より
$$\gcd(\Phi_m(X), X^n-1)\mid \gcd\left(\frac{X^m-1}{X^{\gcd(m, n)}-1}, X^n-1\right)=1$$
となる。
$\Phi_n(X)$ は1の原始 $n$ 乗根に関する円分多項式である。
$\zeta$ を$1$の原始$n$乗根の1つとする。$d< n$ ならば、定義より
$$\zeta^n-1=0, \zeta^d-1\neq 0$$
は明らかだから $\Phi_d(X)\mid (X^d-1)$ より $\Phi_d(\zeta)$ も $0$ ではない。よって $\Phi_n(X)$ の定義より $\Phi_n(\zeta)=0$ となる。
逆に、$\Phi_n(\zeta)=0$ ならば、$\Phi_n(X)\mid(X^n-1)$ だから $\zeta^n-1=0$
は明らか。一方、先の定理から
$$\gcd(\Phi_n(X), X^d-1)=1 (d< n)$$
であるから
$$\zeta^n-1=0, \zeta^d-1\neq 0 (d< n)$$
がすぐに従う。よって $\zeta$ は$1$の原始$n$乗根である。
最後に、 命題1 の (v) から $X^{n-1}-1=0$ は重解を持たず、よって $\Phi_n(X)$ も重解を持たない。
$n\leq 9$ に対する円分多項式は次のようになる。
$$
\begin{align}
\Phi_1(X) & = X-1, \\
\Phi_2(X) & = (X^2-1)/\Phi_1(X) = X+1, \\
\Phi_3(X) & = (X^3-1)/\Phi_1(X) = X^2+X+1, \\
\Phi_4(X) & = (X^4-1)/\Phi_1(X)\Phi_2(X)=(X^4-1)/(X-1)(X+1) = X^2+1, \\
\Phi_5(X) & = (X^5-1)/\Phi_1(X) = X^4+X^3+X^2+X+1, \\
\Phi_6(X) & = (X^6-1)/\Phi_1(X)\Phi_2(X)\Phi_3(X)=(X^6-1)/(X-1)(X+1)(X^2+X+1) = X^2-X+1, \\
\Phi_7(X) & = (X^7-1)/\Phi_1(X) = X^6+X^5+X^4+X^3+X^2+X+1, \\
\Phi_8(X) & = (X^8-1)/\Phi_1(X)\Phi_2(X)\Phi_4(X)=(X^8-1)/(X-1)(X+1)(X^2+1) = X^4+1, \\
\Phi_9(X) & = (X^9-1)/\Phi_1(X)\Phi_3(X) = X^6+X^3+1.\\
\end{align}
$$
一般に $p$ が素数ならば
$$\Phi_p(X)=\frac{X^p-1}{X-1}=X^{p-1}+X^{p-2}+\cdots +X+1$$
が成り立つ。上の定理を使うと
$$
\begin{align}
\Phi_{10}(X) & = \Phi_2(X_5)/\Phi_2(X)= (X^5+1)/(X+1) = X^4-X^3+X^2-X+1 \\
\Phi_{11}(X) & = (X^{11}-1)/(X-1) = X^{10}+X^9+X^8+X^7+X^6+X^5+X^4+X^3+X^2+X+1 \\
\Phi_{12}(X) & = \Phi_6(X^2) = X^4-X^2+1 \\
\Phi_{13}(X) & = (X^{13}-1)/(X-1) = X^{12}+X^{11}+X^{10}+X^9+X^8+X^7+X^6+X^5+X^4+X^3+X^2+X+1 \\
\Phi_{14}(X) & = \Phi_2(X^7)/\Phi_2(X)=(X^7+1)/(X+1) = X^6-X^5+X^4-X^3+X^2-X+1 \\
\Phi_{15}(X) & = \Phi_3(X^5)/\Phi_3(X)=(X^{10}+X^5+1)/(X^2+X+1) = X^8-X^7+X^5-X^4+X^3-X+1 \\
\Phi_{16}(X) & = \Phi_8(X^2) = X^8+1
\end{align}
$$
が求められる。
これらの例は係数が $1, -1, 0$ しか現れないが、必ずそうなるわけではない。そうでない最小の例は $\Phi_{105}(X)=\Phi_{15}(X^7)/\Phi_{15}(X)$ で $X^7, X^{41}$ の係数に $-2$ があらわれる。
$\Phi_n(X)$ の次数を $a_n$ とおくと $p$ が素数のとき
$$a_p=p-1,$$
$$\gcd(m, p)=1 \Longrightarrow a_{mp}=(p-1)a_m,$$
$$p\mid m \Longrightarrow a_{mp}=pa_m$$
であることがわかる。よって
$$ \gcd(m, p)=1 \Longrightarrow a_{mp^e}=p^{e-1}(p-1)a_m$$
となるので $n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$ と素因数分解すると
$$a_n=\prod_{i=1}^k p_i^{e_i-1}(p_i-1)$$
となり、$\varphi(n)$ の公式によらずに円分多項式の次数が求められる
（逆に言えば、このことからも $\varphi(n)=\prod_{i=1}^k p_i^{e_i-1}(p_i-1)$ であることが導かれる）。
$\mu(n)$ を、$n$ が平方因数をもたないとき $(-1)^{\omega(n)}$, $n$ が平方因数をもつとき $0$ と定義すると
$$\Phi_n(X)=\prod_{d\mid n}(X^{n/d}-1)^{\mu(d)}$$
となる。
$n=1$ のとき両辺とも $X-1$ なので定理は正しい。
$n$ の素因数 $p$ をひとつとり、$n=mp$ とおく。
$n$ の代わりに $m$ について定理が正しいとする。$p\mid m$ のとき
$$\Phi_{mp}(X)=\Phi_m(X^p)=\prod_{d\mid m}(X^{mp/d}-1)^{\mu(d)}.$$
$p\not\mid m$ のとき
$$\begin{split}
\Phi_{mp}(X)= & \frac{\Phi_m(X^p)}{\Phi_m(X)} \\
= & \prod_{d\mid m}\frac{(X^{mp/d}-1)^{\mu(d)}}{(X^{m/d}-1)^{\mu(d)}} \\
= & \prod_{d\mid m}(X^{mp/d}-1)^{\mu(d)}(X^{mp/(dp)}-1)^{\mu(dp)} \\
= & \prod_{d\mid (mp)}(X^{mp/d}-1)^{\mu(d)}.
\end{split}$$
よって、$n$ についても定理は正しいから、数学的帰納法より任意の正の整数に対して定理が成り立つ。
参考文献
