View source for Cyclotomic polynomials

<!--
c0275801.png
$#A+1 = 56 n = 0
$#C+1 = 56 : ~/encyclopedia/old_files/data/C027/C.0207580 Cyclotomic polynomials,
Automatically converted into TeX, above some diagnostics.
Please remove this comment and the {{TEX|auto}} line below,
if TeX found to be correct.
-->

{{TEX|auto}}
{{TEX|done}}

''circular polynomials''

The polynomials  $  \Phi _ {1} , \Phi _ {2}, \dots $
that satisfy the relation

$$ 
x  ^ {n} - 1  =  \prod _ {d \mid  n } \Phi _ {d} ( x),
$$

where the product is taken over all positive divisors  $  d $
of the number  $  n $, 
including  $  n $
itself. Over the field of complex numbers one has

$$ 
\Phi _ {n} ( x)  = \ 
\prod _  \zeta  ( x - \zeta ),
$$

where  $  \zeta $
ranges over the primitive  $  n $-th roots of unity (cf. [[Primitive root|Primitive root]]). The degree of  $  \Phi _ {n} ( x) $
is the number of integers  $  k $
among  $  1, \dots, n $
that are relatively prime with  $  n $. 
The polynomials  $  \Phi _ {n} ( x) $
can be computed recursively by dividing the polynomial  $  x  ^ {n} - 1 $
by the product of all  $  \Phi _ {d} ( x) $, 
$  d < n $, 
$  d \mid  n $. 
The coefficients lie in the prime field  $  \mathbf Q $; 
in case of characteristic zero, they are integers. Thus,

$$ 
\Phi _ {1} ( x)  =  x - 1 ,\  \Phi _ {2} ( x)  =  x + 1 ,\ \ 
\Phi _ {3} ( x)  =  x  ^ {2} + x + 1 .
$$

If, moreover,  $  n= p $
is prime, then

$$ 
\Phi _ {p} ( x)  =  
\frac{x  ^ {p} - 1 }{x - 1 }
  =  x ^ {p - 1 }
+ \dots + x + 1 .
$$

The polynomial  $  \Phi _ {n} ( x) $
can be explicitly expressed using the [[Möbius function|Möbius function]]  $  \mu $:

$$ 
\Phi _ {n} ( x)  =  \prod _ {d \mid  n }
( x  ^ {d} - 1 ) ^ {\mu ( n / d ) } .
$$

For example,

$$ 
\Phi _ {12} ( x) =
$$

$$ 
= \ 
( x  ^ {12} - 1) ( x  ^ {6} - 1)  ^ {-1} ( x  ^ {4} - 1)  ^ {-1} ( x  ^ {3} - 1)  ^ {0} ( x  ^ {2} - 1) ( x - 1)  ^ {0 } =
$$

$$ 
= \ 

\frac{x  ^ {6} + 1 }{x  ^ {2} + 1 }
  =  x  ^ {4} - x  ^ {2} + 1 .
$$

All the polynomials  $  \Phi _ {n} ( x) $
are irreducible over the field of rational numbers, but they may be reducible over finite prime fields. Thus, the relation

$$ 
\Phi _ {12} ( x)  =  x  ^ {4} - x  ^ {2} + 1  =  ( x  ^ {2} + 5x + 1 )
( x  ^ {2} - 5x + 1 )
$$

is valid over the field of residues modulo 11.

The equation  $  \Phi _ {n} ( x) = 0 $, 
which gives all primitive  $  n $-th roots of unity, is known as the equation of division of the circle. The solution of this equation in trigonometric form is

$$ 
r _ {k}  =  \cos  
\frac{2 k \pi }{n}
 + i  \sin  
\frac{2 k \pi }{n}
  = \ 
e ^ {2 k \pi i /n } ,
$$

where the fraction  $  k / n $
is irreducible, i.e.  $  k $
and  $  n $
are relatively prime. The solution of the equation of division of the circle by radicals is closely connected with the problem of constructing a regular  $  n $-gon, or with the equivalent problem of subdividing the circle into  $  n $
equal parts; the latter problem can be solved using a straightedge and a pair of compasses if and only if the equation  $  \Phi _ {n} ( x) = 0 $
is solvable in quadratic radicals. It was shown by C.F. Gauss in 1801 that this condition is satisfied if and only if

$$ 
n  =  2  ^ {m} p _ {1} \cdots p _ {s} ,
$$

where  $  m $
is a non-negative integer and  $  p _ {1}, \dots, p _ {s} $
are pairwise different prime numbers of the form  $  2 ^ {2  ^ {k} } + 1 $, 
where  $  k $
is a non-negative integer.

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  B.L. van der Waerden,   "Algebra" , '''1–2''' , Springer  (1967–1971)  (Translated from German)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  A.K. Sushkevich,   "Foundations of higher algebra" , Moscow-Leningrad  (1941)  (In Russian)</TD></TR></table>

====Comments====
The degree of  $  \Phi _ {n} ( x) $
is equal to  $  \phi ( n) $, 
the value (at  $  n $) 
of the Euler  $  \phi $-function (cf. [[Euler function|Euler function]]).

Prime numbers of the form  $  2 ^ {2  ^ {k} } + 1 $
with  $  k $
a non-negative integer are called Fermat primes, these numbers are related to a problem of Fermat: When is the number  $  F _ {k} = 2 ^ {2  ^ {k} } + 1 $, 
with  $  k $
as before, prime? The only small Fermat primes are  $  F _ {0} $, 
$  F _ {1} $, 
$  F _ {2} $, 
$  F _ {3} $, 
$  F _ {4} $ (cf. [[#References|[a1]]], pp. 183-185).

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  I. Stewart,   "Galois theory" , Chapman &amp; Hall  (1973)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  H. Davenport,   "Multiplicative number theory" , Springer  (1980)</TD></TR></table>