円分多項式

$\newcommand{\N}{\mathbb{N}}$ $\newcommand{\Z}{\mathbb{Z}}$ $\newcommand{\Q}{\mathbb{Q}}$ $\newcommand{\R}{\mathbb{R}}$ $\newcommand{\C}{\mathbb{C}}$ $\newcommand{\LCM}{\mathrm{LCM}}$ $\newcommand{\abs}[1]{\left\lvert#1\right\rvert}$ $\newcommand{\wenvert}[1]{\left\lvert\left\lvert#1\right\rvert\right\rvert}$ $\newcommand{\floor}[1]{\left\lfloor#1\right\rfloor}$ $\newcommand{\mathmod}[1]{\ \left(\mathrm{mod}\ #1\right)}$

この記事では、$1$のべき根を根にもつ多項式と、その値の整除性について考察する。

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$乗根は $$e^{2k\pi/n}=\cos\frac{2k\pi}{n}+i\sin\frac{2k\pi}{n} \quad (k\in\Z) \quad \quad (1.1)$$ の形のものと一致する。実際 $\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$ が存在することである。実際 $(1.1)$ のような整数 $k$ をとると 倍数と約数:定理2.7より $$\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$ の形の多項式の性質を調べることから始める。次の性質が成り立つ。

命題 1

• (i) $\gcd(X^m-1, X^n-1)=X^{\gcd(m, n)}-1$,
• (ii) $\gcd((X^m-1)/(X^{\gcd(m, n)}-1), (X^n-1)/(X^{\gcd(m, n)}-1))=1$,
• (iii) $d\mid m$ ならば $\gcd((X^m-1)/(X^d-1), X^d-1)=1$, さらに $(X^m-1)/(X^d-1)\equiv (m/d)\mathmod{X^d-1}$.
• (iv) $\gcd((X^m-1)/(X^{\gcd(m, n)}-1), X^n-1)=1,$
• (v) $X^n-1$ は平方因数をもたない。

これらは、 $\C$ 上でも $\Z$ 上でも成り立つ。

Proof.

(i) $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) が導かれる。

(ii) (i) の両辺を $X^{\gcd(m, n)}-1$ で割ると (ii) が導かれる。

(iii) $m=kd$ とおくと $\Z$ 上で（よって $\C$ 上でも） $$\frac{X^m-1}{X^d-1}=X^{(k-1)d}+X^{(k-2)d}\cdots +1\equiv k\mathmod{X^d-1}$$ となるから、$(X^m-1)/(X^d-1)$ と $X^d-1$ をともに割り切る多項式は定数しかないので、 (iii) が導かれる。

(iv) (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) が従う。

(v) $\C$ 上で $$\frac{d}{dx}(X^n-1)=nX^{n-1}, \gcd(X^n-1, nX^{n-1})=1$$ となるから、多項式の微分の性質から $X^n-1$ は平方因数をもたない。

□

定理 2

$\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)$ はモニックな整数係数の多項式で、次の関係が成り立つ。 $$\Phi_n(X)=\Phi_{n/p}(X^p)/\Phi_{n/p}(X)\quad (p\mid\mid n), \quad\quad (2.1)$$ $$\Phi_n(X)=\Phi_{n/p}(X^p)\quad (p^2 \mid n), \quad\quad (2.2)$$ $$\gcd(\Phi_m(X), X^n-1)>1 \Longrightarrow m\mid n.$$

Proof.

まず、数学的帰納法から、$(2.1)$と$(2.2)$を確かめる。 $n$ がより小さいときに$(2.1), (2.2)$が正しいと仮定し、$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)$$ となる。よって$(2.1)$は $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)$$ より、$(2.2)$も $n=mp$ に対して成り立つ。

よって、$(2.1), (2.2)$ はすべての正の整数 $n$ に対して成り立つ。 つぎに $\Phi_n(X)$ はいずれもモニックな整数係数の多項式であることを数学的帰納法によって示す。 $n=mp$（$p$ は素数）とし $m$ の約数 $d$ に対して $\Phi_d(X)$ はモニックな整数係数の多項式であると仮定する。

$p\mid m$ のときは $(2.2)$ から $\Phi_n(X)=\Phi_m(X^p)$ はモニックな整数係数の多項式である。 $\gcd(m, p)=1$ のとき $\Phi_m(X^p)/\Phi_m(X)$ がモニックな整数係数の多項式となることを示す。 定義より $$\Phi_m(X) | (X^m-1) | (X^{mp}-1) \quad\quad (2.3)$$ はすぐにわかる。ここで $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$$ より $$\gcd (\Phi_m(X), \Phi_d(X^p))=1 \quad\quad (2.4)$$ である。$(2.3), (2.4)$ から、多項式の一意分解より $\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$$ となる。

□

定理 3

$\Phi_n(X)$ は1の原始 $n$ 乗根に関する円分多項式である。

Proof.

$\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$乗根である。

最後に、(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)$ であることが導かれる）。

定理 4

$\mu(n)$ を、$n$ が平方因数をもたないとき $(-1)^{\omega(n)}$, $n$ が平方因数をもつとき $0$ と定義すると $$\Phi_n(X)=\prod_{d\mid n}(X^{n/d}-1)^{\mu(d)}$$ となる。

Proof.

$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$ についても定理は正しいから、数学的帰納法より任意の正の整数に対して定理が成り立つ。

□

円分多項式の値

円分多項式の素因数

定理 2より、円分多項式 $\Phi_n(X) (n=1, 2, \ldots)$ は整数係数の多項式であるから $a$ が整数ならば $\Phi_n(a)$ の値も整数である。

やや一般化された円分多項式の値について考察する。 $$\Phi_n(X, Y)=(X^n-Y^n)/\prod_{d<n, d\mid n}\Phi_d(X, Y)$$ により$2$変数多項式 $\Phi_n(X, Y)$ を定めると $$\Phi_n(X, Y)=Y^{\deg \Phi_n}\Phi_n(X/Y, 1)=Y^{\varphi(n)}\Phi_n(X/Y, 1)$$ となる。つまり $\Phi_n(X)=a_d X^d+a_{d-1} X^{d-1}+\cdots +a_0$ とおくと $$\Phi_n(X, Y)=a_d X^d+a_{d-1} X^{d-1} Y+\cdots +a_0 Y^d$$ となる。よって$a, b$ が整数ならば $\Phi_n(a, b)$ の値も整数である。

$\mathrm{LTE}$ (Lifting The Exponent)と呼ばれる、次の定理から証明する。

定理 5 (Lifting the exponent)

$a, b$ を互いに素な整数とし、$p$ を $a, b$ のどちらも割り切らない素数とする。 $bc\equiv a\mathmod{p}$ となる $c$ をとり、$p$ を法とする $c$ の位数 を $g$ とおく。 このとき $n=p^e m, \gcd(m, p)=1$ とおくと $$p\mid (a^n-b^n)\Longleftrightarrow g\mid n\Longleftrightarrow g\mid m$$ となる。さらに $$p^f\mid\mid (a^g-b^g)$$ となる $f$ をとると、$g\mid m$ かつ $p$ が奇素数 のとき $$p^{f+e}\mid\mid (a^n-b^n)$$ が成り立つ。

Proof.

まず $g$ は $p-1$ を割り切るので $\gcd(g, p)=1$ だから $$g\mid m\Longleftrightarrow g\mid n\Longleftrightarrow p\mid (c^n-1)$$ となる。 $$c^n\equiv 1\mathmod{p}\Longleftrightarrow a^n\equiv (bc)^n\equiv b^n\mathmod{p}$$ だから $$p\mid (a^n-b^n)\Longleftrightarrow g\mid m$$ となる。

そこで $m$ が $g$ で割り切れるとして $m=kg$ つまり $$n=p^e kg$$ とおく。また $c$ を $$bc\equiv a\mathmod{p^{f+e+1}}$$ となるようにとる（$p$ は $a, b$ のどちらも割り切らないから $\gcd(b, p^{f+e+1}=1)$ も成り立つので、 このような $c$ をとることができる）。

$\ell=0, 1, \ldots, e-1$ に対し、 $$c^{p^\ell g}\equiv 1\mathmod{p}$$ が明らかに成り立つ。そこで $$c^{p^\ell g}=Ap+1$$ とおくと $$\begin{split} \frac{c^{p^{\ell +1}g}-1}{c^{p^\ell g}-1}= & \sum_{i=0}^{p-1} c^{i p^\ell g}=\sum_{i=0}^{p-1} (Ap+1)^i \\ = & p+\frac{p(p+1)}{2}Ap+(Ap^2)\sum_{i=2}^{p-1}\binom{i}{2}+\cdots \end{split}$$ より、 $$\frac{c^{p^{\ell +1}g}-1}{c^{p^\ell g}-1}\equiv p\mathmod{p^2}$$ となるから $$p\mid\mid \frac{c^{p^{\ell +1}g}-1}{c^{p^\ell g}-1} \quad\quad (3.1)$$ が成り立つ。よって $$p^e\mid\mid \frac{c^{p^e g}-1}{c^g-1}$$ となるから $$p^{f+e}\mid\mid (c^{p^e g}-1)$$ となる。命題 1の (iii) より $$\gcd((c^n-1)/(c^{p^e g}-1), c^{p^e g}-1)\mid \frac{n}{p^e g}=k$$ だが、$k$ は $p$ で割り切れないから $$p^{f+e}\mid\mid (c^n-1)$$ が成り立つ。 $$a^n-b^n\equiv b^n(c^n-1)\mathmod{p^{f+e+1}}$$ で $b$ は $p$ で割り切れないから $$p^{f+e}\mid\mid (a^n-b^n)$$ も成り立つ。

□

定理 6

$a, b$ を互いに素な整数とし、$p$ を $a, b$ のどちらも割り切らない素数とする。 $bc\equiv a\mathmod{p}$ となる $c$ をとり、$p$ を法とする $c$ の位数 を $g$ とおき $$p^f\mid\mid (a^g-b^g)$$ となる $f$ をとる。 $p\mid \Phi_n(a, b)$ となる必要十分条件は $n=p^e g$ となる整数 $e\geq 0$ が存在することである。 さらに $p^f\mid\mid \Phi_g(a, b)$ となり $p$ が奇素数で $e\geq 1$ あるいは $p=2$ で $e\geq 2$ のとき $p\mid\mid\Phi_{p^e g}(a, b)$ となる。

Proof.

$d<g$ のとき $p$ は $a^d-b^d$ を割り切らないので $\Phi_d(a, b)$ も割り切らない。 $p^f\mid\mid (a^g-b^g)$ となるから $$p^f\mid\mid (a^g-b^g)/\prod_{d\mid g, d<g}\Phi_d(a, b)=\Phi_g(a, b)$$ となる。

$e\geq 1$ とする。 $1\leq d<g$ のとき $p$ は $a^{p^{e-1} d}-b^{p^{e-1} d}$ を割り切らないので $\Phi_{p^{e-1} d}(a, b)$ も割り切らない。 $p$ が奇素数のとき $(3.1)$ より $$p\mid\mid \frac{a^{p^e g}-b^{p^e g}}{a^{p^{e-1} g}-b^{p^{e-1} g}}=\prod_{d\mid g}\Phi_{p^e d}(a, b)$$ となるから、$\mathrm{LTE}$より $p\mid\mid \Phi_{p^e g}(a, b)$ となる。 $p=2, e\geq 2$ のとき $g=1$ で $a, b$ は奇数なので $$\Phi_{p^e g}(a, b)=\frac{a^{2^e}-b^{2^e}}{a^{2^{e-1} g}-b^{2^{e-1} g}}=a^{2^{e-1} g}+b^{2^{e-1} g}\equiv 2\mathmod{4}$$ だから $p\mid\mid \Phi_{p^e g}(a, b)$ となる。

一方 $n=p^e m, \gcd(m, p)=1$ となる整数 $e\geq 0$ と整数 $m$ をとると $p\mid\Phi_{p^e m}(a, b)$ ならば $p\mid (a^{p^e m}-b^{p^e m})$ だから $g$ は $m$ を割り切る。$m>g$ のとき$\mathrm{LTE}$より $p^{e+f}\mid\mid (a^{p^e m}-b^{p^e m}), p^{e+f}\mid\mid (a^{p^e g}-b^{p^e g})$ となるから $p$ は $(a^{p^e m}-b^{p^e m})/(a^{p^e g}-b^{p^e g})$ を割り切らない。 よって $\Phi_{p^e m}(a, b)$ も $p$ で割り切れない。

□

Remark.

$\Phi_{p^e m}(a, b)$ も $p$ で割り切れないことは、命題 1の (iii) と同様にして $$\frac{X^m-Y^m}{X^d-Y^d}=X^{(k-1)d}Y^d+X^{(k-2)d}Y^{2d}\cdots +Y^{(k-1)d}\equiv kX^{kd}\mathmod{X^d-Y^d}$$ となるから $$\frac{a^{p^e m}-b^{p^e m}}{a^{p^e g}-b^{p^e g}}\equiv \frac{m}{g}\times a^{p^e m}\mathmod{a^{p^e g}-b^{p^e g}}$$ が成り立つことから直接示すこともできる。

□

原始素因数

$n$ が $p\mid \Phi_n(a, b)$ となる最小の $n$ であるとき $p$ を $\Phi_n(a, b)$ の原始素因数という。 定理 6より $p$ が $\Phi_n(a, b)$ の原始素因数であることは $n$ が $p$ を法とする $a$ の位数 $g$ であることと同値である。

一方 $p$ が $\Phi_n(a, b)$ の原始素因数でなければ、 $p\mid n$ であり、かつ $n=p^e g$ となる。$g\mid (p-1)$ であるから $p$ は $n$ の最大の素因数となる。さらに $n\geq 3$ のとき $p\mid\mid \Phi_n(a, b)$ である。よって $$u_n(a, b)=\prod_{p\mid\Phi_n(a, b), p\mid n} p$$ とおくと $u_n(a, b)=1$ または $n$ の最大の素因数で $\Phi_n(a, b)/u_n(a, b)$ の素因数は $\Phi_n(a, b)$ の原始素因数であることがわかる。

原始素因数を用いて、初項$1$の等差数列には素数が無限に存在することが示される。

定理 7

任意の正の整数 $n$ に対し、$kn+1$ の形の素数は無数に存在する。

Proof.

$n=1, 2$ のときは単に素数の無限性と同値である。そこで $n\geq 3$ とする。 $m$ を $n$ の倍数とする。 $$\Phi_m(a)=\prod_{\gcd(k, m)=1, 1\leq k\leq m-1} (a-e^{2\pi i k/m})\geq (a-1)^{\varphi(m)}$$ であるから、$a$ が大きいとき $\Phi_m(a)>m\geq u_m(a)$ となる。よって $\Phi_m(a)$ は原始素因数 $p$ をもつ。 $m$ は $p$ を法とする $a$ の位数だから $p$ は $km+1$ の形の素数である。 $m$ は $n$ の倍数だから $p$ は $kn+1$ の形の素数である。 $m$ はいくらでも大きくとれるから、$kn+1$ の形の素数でいくらでも大きいものが存在する。

□

原始素因数については、より強く、以下のZsigmondyの定理が成り立つ。 Zsigmondy1によって証明され、その後 Kanold2などにより、再証明が行われている。

$b=1$ のとき、つまり $\Phi_n(a)$ の原始素因数に関してはBang3によって証明され、Dickson4がより簡単な証明を与えている。

定理 8 (Zsigmondyの定理)

$a>b>0$ かつ $\gcd(a, b)=1$ のとき $\Phi_n(a, b)$ は $(a, b, n)=(2, 1, 6)$, $(a+b, n)=(2^m, 2)$, $(a-b, n)=(1, 1)$ の場合を除いて原始素因数をもつ。

Proof.

定理 4の証明と同様に $$\begin{split} \Phi_n(a, b)= & \prod_{d\mid n}(a^{n/d}-b^{n/d})^{\mu(d)}=a^{\varphi(n)}\prod_{d\mid n}\left(1-\left(\frac{b}{a}\right)^{n/d}\right)^{\mu(d)} \\ \geq & a^{\varphi(n)}\left(1-\frac{b}{a}\right)\prod_{k\geq 2, k\mid n, \mu(n/k)=1}\left(1-\left(\frac{b}{a}\right)^k\right) \end{split}$$ となる。 $$n=\prod_{i=1}^r p_i^{e_i}, p_1<p_2<\ldots<p_r$$ と素因数分解すると、$\mu(k)=\pm 1$ となる $n$ の約数の個数は $2^r$ である。 $p_1$ が $k$ を割り切らないとき $\mu(k)=1\Longleftrightarrow \mu(p_1 k)=-1$ であるから $\mu(k)=1$ となる $n$ の約数の個数は $2^{r-1}$ 個である。また $$\varphi(n)\geq \prod_{i=1}^r (p_i-1)\geq \prod_{i=2}^r (p_i-1)\geq 2^{r-1}$$ であるから $$\begin{split} \Phi_n(a, b)\geq & a^{\varphi(n)}\left(1-\frac{b}{a}\right)\left(1-\left(\frac{b}{a}\right)^2\right)^{\varphi(n)-1} \\ \geq & (a-b)\left(a\left(1-\left(\frac{b}{a}\right)^2\right)\right)^{\varphi(n)-1} \end{split}$$ となる。 $$1-\left(\frac{a-1}{a}\right)^2=1-\frac{a^2-2a+1}{a^2}=\frac{2a-1}{a^2}$$ かつ $b\leq a-1$ より $$\Phi_n(a, b)\geq \left(2-\frac{1}{a}\right)^{\varphi(n)-1}$$ であることがわかる。$a\geq 2$ だから $p_r\geq 5$ のとき $$\Phi_n(a, b)\geq \left(\frac{3}{2}\right)^{p_r-1}>p_r\geq u_n(a, b),$$ $a\geq 4$ かつ $p_r=3$ のとき $$\Phi_n(a, b)\geq \left(\frac{7}{4}\right)^2>p_r\geq u_n(a, b),$$ $2\leq a\leq 3$ で $p_r=3$ のとき $r=1, n=3^e$ ならば $$\begin{split} \Phi_n(a, b)= & \frac{a^n-b^n}{a^{n/3}-b^{n/3}} \\ = & a^{2\times 3^{e_1-1}}+a^{3^{e_1-1}}b^{3^{e_1-1}}+b^{2\times 3^{e_1-1}} \geq a^2+ab+b^2 \\ = & 7>p_r>u_n(a, b) \end{split}$$ となる。さらに $r=2, p_1=2, p_2=3$ ならば $$\begin{split} \Phi_n(a, b)= & \left(\frac{a^n-b^n}{a^{n/3}-b^{n/3}}\right)/\left(\frac{a^{n/2}-b^{n/2}}{a^{n/6}-b^{n/6}}\right) \\ = & a^{2^{e_1-1}\times 3^{e_2-1}}-a^{2^{e_1-1}\times 3^{e_2-1}}b^{2^{e_1-1}\times 3^{e_2-1}}+b^{2^{e_1-1}\times 3^{e_2-1}} \end{split}$$ となるので $a\geq 3$ ならば $$\Phi_n(a, b)\geq a^2-ab+b^2\geq 7>p_r>u_n(a, b),$$ $a=2, b=1$ で $n>6$ ならば $$\Phi_n(a, b)\geq a^4-a^2+1\geq 13>p_r>u_n(a, b),$$ となる。 $r=1, p_1=2$ のとき $e_1\geq 2$ ならば $$\Phi_n(a, b)=a^{2^{e_1-1}}+b^{2^{e_1-1}}\geq a^2+b^2>2\geq u_n(a, b)$$ となる。以上より $n\geq 3$ のときは $(a, b, n)=(2, 1, 6)$ の場合を除いて、$\Phi_n(a, b)$ は原始素因数をもつ。

$n=2$ のとき $$\Phi_n(a, b)=a+b, \Phi_1(a, b)=a-b$$ だから $p$ が $\Phi_1(a, b), \Phi_2(a, b)$ をともに割り切るとき $p$ は $$2a=\Phi_2(a, b)+\Phi_1(a, b), 2b=\Phi_2(a, b)-\Phi_1(a, b)$$ をともに割り切るが $\gcd(a, b)=1$ なので $p=2$, よって $a+b$ が $2$ の累乗でなければ $\Phi_n(a, b)$ は原始素因数をもつ。

$n=1$ のとき $a-b=1$ でなければ $a-b$ の素因数が $\Phi_1(a, b)$ の原始素因数となる。

□

参考文献

この項目については、上記論文のほか Trygve Nagell, Introduction to Number Theory, John Wiley & Sons, Inc. New York, 1951, Chapter V, Harold N. Shapiro, Introduction to the Theory of Numbers, John Wiley & Sons, Inc. New York, 1983, Section 6.4A を参考とした。

またW. Sierpinski, Elementary Number Theory, 2nd English edition, edited by A. Schinzel, North-Holland, Amsterdam, 1988, Chapter 6, Section 6.5 では円分多項式を使わずに直接 $$\prod_{d\mid n}(n^d-1)^{\mu(n/d)}$$ の形の積の素因数について論じている。