Difference between revisions of "Cyclotomic polynomials"
m |
|||
| Line 1: | Line 1: | ||
| − | '''Cyclotomic''' (or "circle dividing") '''polynomials''' are the irreducible factors of <math>z^n - 1\!</math> when the polynomial coefficients are restricted to the field of [[rational | + | '''Cyclotomic''' (or "circle dividing") '''polynomials''' are the irreducible factors of <math>z^n - 1\!</math> when the polynomial coefficients are restricted to the field of [[rational number]]s. For example |
:<math> z^6-1 = (z^2-z+1) (z^2+z+1) (z+1) (z-1) </math>. | :<math> z^6-1 = (z^2-z+1) (z^2+z+1) (z+1) (z-1) </math>. | ||
Revision as of 16:21, May 21, 2007
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 divisors 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,
