Difference between revisions of "User:Ga ohoyt/Cyclotomic polynomials"
| Line 58: | Line 58: | ||
:<math>\Phi_n(z) = \prod_{k=1}^{\varphi(n)}(z-e^{\frac {2\pi k} {n} j})\;</math> | :<math>\Phi_n(z) = \prod_{k=1}^{\varphi(n)}(z-e^{\frac {2\pi k} {n} j})\;</math> | ||
| − | where <math>\phi(n)</math> is [[Euler's totient function]]. | + | where <math>\phi(n)</math> is [[Euler's totient function]]. For example, |
| + | |||
| + | :<math>\Phi_6(z) = (z-e^{\frac {\pi} {3} j})(z-e^{\frac {5\pi} {3} j}) = z^2-z+1.</math> | ||
| + | |||
| + | ==Some special cases== | ||
| + | When p and q are odd primes, | ||
| + | |||
| + | :<math>\Phi_p(z)=\frac{z^p-1}{z-1}=\sum_{k=0}^{p-1} z^k</math> | ||
| + | |||
| + | :<math>\Phi_2p(z)=\frac{z^p+1}{z+1}=\sum_{k=0}^{p-1} {-z}^k</math> | ||
Revision as of 00:59, May 20, 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
- z6−1 = (z−1) (z+1) (z2+z+1) (z2−z+1).
The cyclotomic polynomials are often written as 
. The polynomial has exactly as many of these factors as there are integer factors of n, for example
- z6−1 =
.
In general,
.
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 the following 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.
.
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,
The zeroes of the polynomial
are precisely the nth roots of unity, each with multiplicity 1.
The nth cyclotomic polynomial is defined by the fact that its zeros are precisely the primitive nth roots of unity, each with multiplicity 1:
where z1,...,zφ(n) are the primitive nth roots of unity, and is Euler's totient function. The polynomial has integer coefficients and is an irreducible polynomial over the rational numbers (i.e., cannot be written as a product of two positive-degree polynomials with rational coefficients). (The case of prime n, which is easier than the general assertion, follows from Eisenstein's criterion.)
Every nth root of unity is a primitive dth root of unity for exactly one positive divisor d of n. This implies that
This formula represents the factorization of the polynomial zn - 1 into irreducible factors.
- z1−1 = z−1
- z2−1 = (z−1)(z+1)
- z3−1 = (z−1)(z2+z+1)
- z4−1 = (z−1)(z+1)(z2+1)
- z5−1 = (z−1)(z4+z3+z2+z+1)
- z6−1 = (z−1)(z+1)(z2+z+1)(z2−z+1)
- z7−1 = (z−1)(z6+z5+z4+z3+z2+z+1)
Applying Möbius inversion to the formula gives
where μ is the Möbius function.
So the first few cyclotomic polynomials are
- Φ1(z) = z−1
- Φ2(z) = (z2−1)(z−1)−1 = z+1
- Φ3(z) = (z3−1)(z−1)−1 = z2+z+1
- Φ4(z) = (z4−1)(z2−1)−1 = z2+1
- Φ5(z) = (z5−1)(z−1)−1 = z4+z3+z2+z+1
- Φ6(z) = (z6−1)(z3−1)−1(z2−1)−1(z−1) = z2−z+1
- Φ7(z) = (z7−1)(z−1)−1 = z6+z5+z4+z3+z2+z+1
If p is a prime number, then all pth roots of unity except 1 are primitive pth roots, and we have
. Substituting for 
, this is a base z repunit. Thus a necessary (but not sufficient) condition for a repunit to be prime is that its length be prime.
Note that, contrary to first appearances, not all coefficients of all cyclotomic polynomials are 1, −1, or 0; the first polynomial where this occurs is 
, since 105=3×5×7 is the first product of three odd primes. Many restrictions are known about the values that cyclotomic polynomials can assume at integer values. For example, if 
is prime and 
then 
or 
.
