Difference between revisions of "Cyclotomic polynomials"
| Line 78: | Line 78: | ||
:<math>\Phi_{pq}(z)=\frac{(z^{pq}-1) (z-1)}{(z^p-1) (z^q-1)}=\frac {\sum_{k=0}^{q-1} z^{pk} } {\sum_{k=0}^{q-1} z^k}</math> | :<math>\Phi_{pq}(z)=\frac{(z^{pq}-1) (z-1)}{(z^p-1) (z^q-1)}=\frac {\sum_{k=0}^{q-1} z^{pk} } {\sum_{k=0}^{q-1} z^k}</math> | ||
| + | |||
| + | [[Category:Mathematics]] | ||
Revision as of 16:03, 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,
