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

n > 0 {\displaystyle n>0} を整数とする。このとき n {\displaystyle n} 乗して1となる数、つまり方程式
1の冪根

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

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

であるから
1の冪根

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

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

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

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

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

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

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

まず、1の n {\displaystyle n} 乗根に対応する X n − 1 {\displaystyle X^{n}-1} の形の多項式の性質を調べることから始める。次の性質が成り立つ。
円分多項式

命題
円分多項式

(i) gcd ( X m − 1 , X n − 1 ) = X gcd ( m , n ) − 1 , {\displaystyle \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 , {\displaystyle \gcd((X^{m}-1)/(X^{\gcd(m,n)}-1),(X^{n}-1)/(X^{\gcd(m,n)}-1))=1,} (iii) d {\displaystyle d} が m {\displaystyle m} の約数のとき gcd ( ( X m − 1 ) / ( X d − 1 ) , X d − 1 ) = 1 , {\displaystyle \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 , {\displaystyle \gcd((X^{m}-1)/(X^{\gcd(m,n)}-1),X^{n}-1)=1,} (v) X n − 1 {\displaystyle X^{n}-1} は平方因数を持たない.
円分多項式

証明 m = a n + r ( 0 ≤ r < n ) {\displaystyle m=an+r(0\leq r<n)} とおくと
円分多項式

となるが、この右辺の中の多項式は
円分多項式

と因数分解できるから X m − 1 {\displaystyle X^{m}-1} を X n − 1 {\displaystyle X^{n}-1} で割った余りは X r − 1 {\displaystyle X^{r}-1} に一致する。よってユークリッドの互除法より
円分多項式

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

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

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

なお、(iii) は直接計算で確かめることもできる。 d {\displaystyle d} が n {\displaystyle n} の約数のとき m = d l {\displaystyle m=dl} とおくと
円分多項式

であるが X k d − 1 {\displaystyle X^{kd}-1} は X d − 1 {\displaystyle X^{d}-1} で割り切れるから各 X k d {\displaystyle X^{kd}} を X d − 1 {\displaystyle X^{d}-1} で割った余りは 1 に等しい。よって X m − 1 X d − 1 {\displaystyle {\frac {X^{m}-1}{X^{d}-1}}} を X d − 1 {\displaystyle X^{d}-1} で割った余りは l {\displaystyle l} に等しいから
円分多項式

となり (iii) が導かれる。
円分多項式

さて、有理式 F n ( X ) {\displaystyle F_{n}(X)} を漸化式
円分多項式

により定義する。すると、 F n ( X ) {\displaystyle F_{n}(X)} はいずれも整数係数の多項式であることが示される。より正確に、次の事実がわかる。
円分多項式

全ての正の整数 n {\displaystyle n} に対し、 F n ( X ) {\displaystyle F_{n}(X)} はいずれもモニックな整数係数の多項式で、次の関係が成り立つ。
円分多項式

証明 まず、数学的帰納法から、一番目の式と二番目の式を確かめる。 n {\displaystyle n} がより小さいときにこの2つの式が正しいと仮定し、 n = m p {\displaystyle n=mp} ( p {\displaystyle p} は素数)とおく。
円分多項式

gcd ( m , p ) = 1 {\displaystyle \gcd(m,p)=1} のとき
円分多項式

より( d | m {\displaystyle d|m} だから gcd ( d , p ) = 1 {\displaystyle \gcd(d,p)=1} である)
円分多項式

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

一方 p | m {\displaystyle p|m} のとき m = l p k , gcd ( l , p ) = 1 {\displaystyle m=lp^{k},\gcd(l,p)=1} とおくと
円分多項式

であるが
円分多項式

であることから
円分多項式

である。よって
円分多項式

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

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

定義より
円分多項式

はすぐにわかる。ここで d < m {\displaystyle d<m} を m {\displaystyle m} の約数とする。 gcd ( m , p ) = 1 {\displaystyle \gcd(m,p)=1} より d p {\displaystyle dp} は m {\displaystyle m} の倍数ではない。よって上記の命題の (iv) より gcd ( F m ( X ) , X d p − 1 ) = 1 {\displaystyle \gcd(F_{m}(X),X^{dp}-1)=1} である。 F d ( X p ) = ( X p ) d − 1 = X d p − 1 {\displaystyle F_{d}(X^{p})=(X^{p})^{d}-1=X^{dp}-1} より
円分多項式

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

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

となる。これで、定理の証明は終わった。
円分多項式

すると、この多項式 F n ( X ) {\displaystyle F_{n}(X)} が円分多項式となる。
円分多項式

F n ( X ) {\displaystyle F_{n}(X)} は1の原始 n {\displaystyle n} 乗根に関する円分多項式である。
円分多項式

証明 ζ {\displaystyle \zeta } を 1の原始 n {\displaystyle n} 乗根の1つとすると、定義より
円分多項式

は明らかである。 F d ( X ) | ( X d − 1 ) {\displaystyle F_{d}(X)|(X^{d}-1)} だから
円分多項式

がすぐに従う。よって F n ( X ) {\displaystyle F_{n}(X)} の定義より F n ( ζ ) = 0 {\displaystyle F_{n}(\zeta )=0} となる。
円分多項式

逆に、 F n ( ζ ) = 0 {\displaystyle F_{n}(\zeta )=0} ならば、 F n ( X ) | X n − 1 {\displaystyle F_{n}(X)|X^{n}-1} だから ζ n − 1 = 0 {\displaystyle \zeta ^{n}-1=0} は明らか。一方、先の定理から
円分多項式

であるから
円分多項式

がすぐに従う。よって ζ {\displaystyle \zeta } は 1の原始 n {\displaystyle n} 乗根。
円分多項式

最後に、性質 (v) から X n − 1 − 1 = 0 {\displaystyle X^{n-1}-1=0} は重解を持たず、よって F n ( X ) {\displaystyle F_{n}(X)} も重解を持たない。これで証明は終了した。
円分多項式

n ≤ 9 {\displaystyle n\leq 9} に対する円分多項式は次のようになる。
円分多項式

一般に p {\displaystyle p} が素数ならば
円分多項式

が成り立つ。上の定理を使うと
円分多項式

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

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

F n ( X ) {\displaystyle F_{n}(X)} の次数を a n {\displaystyle a_{n}} とおくと p {\displaystyle p} が素数のとき
円分多項式

であることがわかる。よって
円分多項式

となるので n = p 1 e 1 p 2 e 2 ⋯ p k e k {\displaystyle n=p_{1}^{e_{1}}p_{2}^{e_{2}}\cdots p_{k}^{e_{k}}} と素因数分解すると
円分多項式

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