User:Ga ohoyt/Cyclotomic polynomials
Cyclotomic (or "circle dividing") polynomials are the irreducible factors of 
when the polynomial coefficients are restricted to the field of rational numbers. For example
.
The cyclotomic polynomials are often written as 
. The polynomial has exactly as many of these factors as there are integer factors of n:
.
Contents
Finding cyclotomic polynomials
Recursive method
Cyclotomic polynomials are defined by the equation
.
Solving for , one obtains
.
One can then construct any polynomial recursively, given that 
:
.
Direct method
For larger values of n, it is easier to use the direct formula, based on the Möbius inversion of the above formula:
where μ is the Möbius function. For example, one would follow these steps for n = 60:
- 1. Factor n.
- 2. Determine the square-free divisors of n, and classify them according to whether their number of prime factors are even or odd.
(Odd)
(Even)
(Even)
(Even)
(Odd)
(Odd)
(Odd)
(Even, since 1 is not a prime)
- 3. Form the factors
, putting the factors from the even class in the numerator and those from the odd class in the denominator.
.
Construction from complex roots
It is also possible to construct a cyclotomic polynomial from the complex roots of 1:
where 
is Euler's totient function. For example,
Some special cases
When p and q are odd primes,
