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

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,