初等整数論/円分多項式

多項式の中でも、初等整数論において重要な意味を持つのが円分多項式と呼ばれる多項式である。

1の冪根

$n>0$ を整数とする。このとき $n$乗して1となる数、つまり方程式

$x^n-1=0$

の解を1の $n$ 乗根という。たとえば1の3乗根は $x^3-1=(x-1)(x^2+x+1)$ より $1,\frac{-1\pm \sqrt{-3}}{2}$ で与えられる。 ド・モアブルの定理より

$(\cos \theta +i\sin \theta {)}^n=\cos n\theta +i\sin n\theta$

であり、またオイラーの公式より

$\cos \theta +i\sin \theta =\exp i\theta$

であるから

$\cos \frac{2k\pi }{n}+i\sin \frac{2k\pi }{n}=\exp \frac{2k\pi i}{n}(k=0,1,\dots ,n-1)$

は1の $n$ 乗根である。これらは $n$ 個の相異なる数で、1の $n$ 乗根は高々 $n$ 個であるから、1の $n$ 乗根は上の形のもので全て尽くされている。

さて、1の $n$ 乗根の中でも、特に $n$ 乗してはじめて1となるものを1の原始 $n$ 乗根という。たとえば $\frac{1\pm \sqrt{-3}}{2}=\cos \frac{\pi }{3}\pm \sin \frac{\pi }{3}$ は1の原始6乗根であり、$\pm 1,\frac{-1\pm \sqrt{-3}}{2}=\cos \frac{\pi }{3}\pm \sin \frac{\pi }{3}$ は1の6乗根であるが原始6乗根ではない。

$\cos \frac{2k\pi }{n}+i\sin \frac{2k\pi }{n}=\exp \frac{2k\pi i}{n}$

が1の原始 $n$ 乗根であるための必要十分条件は $\gcd (k,n)=1$ である。実際 $\zeta =\cos \frac{2k\pi }{n}+i\sin \frac{2k\pi }{n}$ とおくと ${\zeta }^m=\cos \frac{2km\pi }{n}+i\sin \frac{2km\pi }{n}$ だから 定理 1.6' より ${\zeta }^m=1⟺n|km⟺n/\gcd (k,n)|m$ となる。

さて、1の原始6乗根は2次方程式 $x^2-x+1=0$ の解であるが、一般に1の原始n乗根をちょうど解に持ち、なおかつ重解を持たない多項式を円分多項式という。つまり

$\prod _{1\le k\le n-1,\gcd (k,n)=1}(x-{\zeta }^k)$

が1の原始n乗根に対する円分多項式である。

基本的な事実は、円分多項式は常に整数係数の多項式となることである。

円分多項式

まず、円分多項式が整数係数の多項式であることを示したいが、ここでは、上の定義から直接示すのではなく、多項式の算術を用いて間接的に、ある特殊な条件を満たす整数係数の多項式を構成し、それが円分多項式に一致することを示す方法を取る。実はこの方法において、多項式を構成する上では1の $n$ 乗根の性質は直接使用せず、有理数上の多項式の範囲で議論することになる。

まず、1の $n$ 乗根に対応する $X^n-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$ が $m$ の約数のとき $\gcd ((X^m-1)/(X^d-1),X^d-1)=1,$
(iv) $\gcd ((X^m-1)/(X^{\gcd (m,n)}-1),X^n-1)=1,$
(v) $X^n-1$ は平方因数を持たない.

証明
$m=an+r(0\le 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$ に一致する。よってユークリッドの互除法より

$\gcd (X^m-1,X^n-1)=X^{\gcd (m,n)}-1$

となり (i) が導かれる。そうすると、$X^{\gcd (m,n)}-1$ で割ることで (ii) も導かれる。

(v)を先に証明すると、$\frac{d}{dx}(X^n-1)=n{X}^{n-1},\gcd (X^n-1,n{X}^{n-1})=1$ より、多項式の微分の性質から $X^n-1$ は平方因数を持たない。

そうすると $P(x)=\gcd ((X^m-1)/(X^d-1),X^d-1)$ とおくと $P(x{)}^2\mid (X^d-1)[(X^m-1)/(X^d-1)]=X^m-1$ となり (v) から $P(x)$ は定数でなければならないから (iii) が導かれる。因数分解の一意性より (ii)(iii) （$d=\gcd (m,n)$ とする）から (iv) が直ちに従う。

なお、(iii) は直接計算で確かめることもできる。$d$ が $n$ の約数のとき $m=dl$ とおくと

\frac{X^m-1}{X^d-1}=\frac{X^{dl}-1}{X^d-1}=X^{(l-1)d}+X^{(l-2)d}+ \cdots +X^d+1

であるが $X^{kd}-1$ は $X^d-1$ で割り切れるから各 $X^{kd}$ を $X^d-1$ で割った余りは 1 に等しい。よって $\frac{X^m-1}{X^d-1}$ を $X^d-1$ で割った余りは $l$ に等しいから

$\gcd ((X^m-1)/(X^d-1),X^d-1)=1$

となり (iii) が導かれる。

さて、有理式 $F_n(X)$ を漸化式

$F_1(X)=X-1$

$F_n(X)=(X^n-1)/\prod _{d<n,d|n}{F}_d(X)$

により定義する。すると、 $F_n(X)$ はいずれも整数係数の多項式であることが示される。より正確に、次の事実がわかる。

定理 1

全ての正の整数 $n$ に対し、$F_n(X)$ はいずれもモニックな整数係数の多項式で、次の関係が成り立つ。

$F_n(X)=F_{n/p}(X^p)/F_{n/p}(X)(p||n),$

$F_n(X)=F_{n/p}(X^p)(p^2|n),$

$\gcd (F_m(X),X^n-1)>1$ のとき $m|n.$

証明
まず、数学的帰納法から、一番目の式と二番目の式を確かめる。 $n$ がより小さいときにこの2つの式が正しいと仮定し、$n=mp$（$p$ は素数）とおく。

$\gcd (m,p)=1$ のとき

$F_m(X^p)=(X^{mp}-1)/\prod _{d|m,d<m}{F}_d(X^p)=(X^{mp}-1)/\prod _{d|m,d<m}(F_d(X)F_{dp}(X))=(X^{mp}-1)/\prod _{d|mp,d\ne m,mp}{F}_d(X)$

より（$d|m$ だから $\gcd (d,p)=1$ である）

$F_m(X^p)/F_m(X)=(X^{mp}-1)/\prod _{d|mp,d<mp}{F}_d(X)=F_{mp}(X)$

となる。よって一番目の式は成り立つ。

一方 $p|m$ のとき $m=l{p}^k,\gcd (l,p)=1$ とおくと

$\prod _{d|m,d<m}{F}_d(X^p)=\prod _{d|l,d<l}\prod _{s=0}^k(F_{d{p}^s}(X^p))\prod _{s=0}^{k-1}(F_{l{p}^s}(X^p))$

であるが

$\prod _{s=0}^k(F_{d{p}^s}(X^p))=F_d(X)\prod _{s=0}^k(F_{d{p}^{s+1}}(X))=\prod _{s=0}^{k+1}(F_{d{p}^s}(X))$

であることから

$\prod _{d|m,d<m}{F}_d(X^p)=\prod _{d|l,d<l}\prod _{s=0}^{k+1}(F_{d{p}^s}(X))\prod _{s=0}^k(F_{l{p}^s}(X))=\prod _{d|mp,d<mp}{F}_d(X)$

である。よって

$F_m(X^p)=(X^{mp}-1)/\prod _{d|m,d<m}{F}_d(X^p)=(X^{mp}-1)/\prod _{d|mp,d<mp}{F}_d(X)=F_{mp}(X)$

より、二番目の式も確かめられる。

さて $F_n(X)$ はいずれもモニックな整数係数の多項式であることを示す。数学的帰納法より示す。 $n=mp$（$p$ は素数）とし $m$ の約数 $d$ に対して $F_d(X)$ はモニックな整数係数の多項式であると仮定する。2つの式を確かめた今、問題となるのは $\gcd (m,p)=1$ のとき $F_m(X^p)/F_m(X)$ がモニックな整数係数の多項式となるかどうかである。

定義より

$F_m(X)|(X^m-1)|(X^{mp}-1)\cdots (\mathrm{\#})$

はすぐにわかる。ここで $d<m$ を $m$ の約数とする。 $\gcd (m,p)=1$ より $dp$ は $m$ の倍数ではない。よって上記の命題の (iv) より $\gcd (F_m(X),X^{dp}-1)=1$ である。$F_d(X^p)=(X^p{)}^d-1=X^{dp}-1$ より

$\gcd (F_m(X),F_d(X^p))=1\cdots (\mathrm{♭})$

である。$(\mathrm{\#})(\mathrm{♭})$ から、因数分解の一意性より $F_m(X)|F_m(X^p)$ である。また、多項式の除法の原理から、整数係数の多項式をモニックな整数係数の多項式で割った商と剰余は整数係数の多項式でなければならない。帰納法の仮定より、$F_m(X)$ はモニックな整数係数の多項式だから $F_m(X^p)/F_m(X)$ は整数係数の多項式である。さらに $F_m(X^p)$ もモニックな整数係数の多項式だから、$F_m(X^p)/F_m(X)$ はモニックな多項式である。

最後に、三番目の性質だが、 $m|n$ でなければ $\gcd (m,n)<m$ より $F_m(X)$ は $(X^m-1)/(X^{\gcd (m,n)}-1)$ の因数となる。よって上記の命題の (iv) より

$\gcd (F_m(X),X^n-1)=\gcd ((X^m-1)/(X^{\gcd (m,n)}-1),X^n-1)=1$

となる。これで、定理の証明は終わった。

すると、この多項式 $F_n(X)$ が円分多項式となる。

定理 2

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

証明
$\zeta$ を 1の原始 $n$ 乗根の1つとすると、定義より

${\zeta }^n-1=0,{\zeta }^d-1\ne 0(d<n)$

は明らかである。 $F_d(X)|(X^d-1)$ だから

$F_d(\zeta )\ne 0(d<n)$

がすぐに従う。よって $F_n(X)$ の定義より $F_n(\zeta )=0$ となる。

逆に、$F_n(\zeta )=0$ ならば、$F_n(X)|X^n-1$ だから ${\zeta }^n-1=0$ は明らか。一方、先の定理から

$\gcd (F_n(X),X^d-1)=1(d<n)$

であるから

${\zeta }^n-1=0,{\zeta }^d-1\ne 0(d<n)$

がすぐに従う。よって $\zeta$ は 1の原始 $n$ 乗根。

最後に、性質 (v) から $X^{n-1}-1=0$ は重解を持たず、よって $F_n(X)$ も重解を持たない。これで証明は終了した。

$n\le 9$ に対する円分多項式は次のようになる。

$\begin{array}{cccc}{F}_1(X)& & & =X-1,\\ F_2(X)& =(X^2-1)/F_1& & =X+1,\\ F_3(X)& =(X^3-1)/F_1& & =X^2+X+1,\\ F_4(X)& =(X^4-1)/F_1{F}_2& & =(X^4-1)/(X-1)(X+1)=X^2+1,\\ F_5(X)& =(X^5-1)/F_1& & =X^4+X^3+X^2+X+1,\\ F_6(X)& =(X^6-1)/F_1{F}_2{F}_3& & =(X^6-1)/(X-1)(X+1)(X^2+X+1)=X^2-X+1,\\ F_7(X)& =(X^7-1)/F_1& & =X^6+X^5+X^4+X^3+X^2+X+1,\\ F_8(X)& =(X^8-1)/F_1{F}_2{F}_4& & =(X^8-1)/(X-1)(X+1)(X^2+1)=X^4+1,\\ F_9(X)& =(X^9-1)/F_1{F}_3& & =X^6+X^3+1.\\ \end{array}$

一般に $p$ が素数ならば

$F_p(X)=(X^p-1)/(X-1)=X^{p-1}+X^{p-2}+\cdots +X+1$

が成り立つ。上の定理を使うと

$\begin{array}{cccc}{F}_{10}(X)& =F_2(X_5)/F_2(X)& & =(X^5+1)/(X+1)=X^4-X^3+X^2-X+1\\ F_{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\\ F_{12}(X)& =F_6(X^2)& & =X^4-X^2+1\\ F_{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\\ F_{14}(X)& =F_2(X^7)/F_2(X)& & =(X^7+1)/(X+1)=X^6-X^5+X^4-X^3+X^2-X+1\\ F_{15}(X)& =F_3(X^5)/F_3(X)& & =(X^{10}+X^5+1)/(X^2+X+1)=X^8-X^7+X^5-X^4+X^3-X+1\\ F_{16}(X)& =F_8(X^2)& & =X^8+1\end{array}$

が求められる。 これらの例は係数が 1, -1, 0 しか現れないが、必ずそうなるわけではない。そうでない最小の例は $F_{105}(X)=F_{15}(X^7)/F_{15}(X)$ で $X^7,X^{41}$ の係数に -2 が現れる。

円分多項式は既約多項式であるが、この証明は後に合同多項式を用いて行うことにする。

$F_n(X)$ の次数を $a_n$ とおくと $p$ が素数のとき

• $a_p=p-1,$
• $\gcd (m,p)=1$ のとき $a_{mp}=(p-1)a_m,$
• $p|m$ のとき $a_{mp}=p{a}_m$

であることがわかる。よって

$\gcd (m,p)=1$ のとき $a_{m{p}^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)$

が従う。この右辺の数は重要な意味を持つが、それは合同式と関連して議論することにする。