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:
Finding cyclotomic polynomials
Cyclotomic polynomials are defined by the equation
Solving for , one obtains
One can then construct any polynomial recursively, given that :
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.
- (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,