In mathematics, the nth cyclotomic polynomial, for any positive integer n, is the unique irreducible polynomial with integer coefficients that is a divisor of and is not a divisor of for any Its roots are all nth primitive roots of unity , where k runs over the positive integers not greater than n and coprime to n (and i is the imaginary unit). In other words, the nth cyclotomic polynomial is equal to
It may also be defined as the monic polynomial with integer coefficients that is the minimal polynomial over the field of the rational numbers of any primitive nth-root of unity ( is an example of such a root).
An important relation linking cyclotomic polynomials and primitive roots of unity is
showing that is a root of if and only if it is a dth primitive root of unity for some d that divides n.
Examples
If n is a prime number, then
If n = 2p where p is an odd prime number, then
For n up to 30, the cyclotomic polynomials are:
The case of the 105th cyclotomic polynomial is interesting because 105 is the least positive integer that is the product of three distinct odd prime numbers (3*5*7) and this polynomial is the first one that has a coefficient other than 1, 0, or −1:
Properties
Fundamental tools
The cyclotomic polynomials are monic polynomials with integer coefficients that are irreducible over the field of the rational numbers. Except for n equal to 1 or 2, they are palindromes of even degree.
The degree of , or in other words the number of nth primitive roots of unity, is , where is Euler's totient function.
The fact that is an irreducible polynomial of degree in the ring is a nontrivial result due to Gauss. Depending on the chosen definition, it is either the value of the degree or the irreducibility which is a nontrivial result. The case of prime n is easier to prove than the general case, thanks to Eisenstein's criterion.
A fundamental relation involving cyclotomic polynomials is
which means that each n-th root of unity is a primitive d-th root of unity for a unique d dividing n.
The Möbius inversion formula allows the expression of as an explicit rational fraction:
where is the Möbius function.
The cyclotomic polynomial may be computed by (exactly) dividing by the cyclotomic polynomials of the proper divisors of n previously computed recursively by the same method:
(Recall that .)
This formula defines an algorithm for computing for any n, provided integer factorization and division of polynomials are available. Many computer algebra systems, such as SageMath, Maple, Mathematica, and PARI/GP, have a built-in function to compute the cyclotomic polynomials.
Easy cases for computation
As noted above, if is a prime number, then
If n is an odd integer greater than one, then
In particular, if is twice an odd prime, then (as noted above)
If is a prime power (where p is prime), then
More generally, if with relatively prime to , then
These formulas may be applied repeatedly to get a simple expression for any cyclotomic polynomial in term of a cyclotomic polynomial of square free index: If is the product of the prime divisors of (its radical), then
This allows to give formulas for the th cyclotomic polynomial when has at most one odd prime factor: If is an odd prime number, and and are positive integers, then:
For the other values of , the computation of the th cyclotomic polynomial is similarly reduced to that of where is the product of the distinct odd prime divisors of . To deal with this case, one has that, for prime and not dividing ,
Integers appearing as coefficients
The problem of bounding the magnitude of the coefficients of the cyclotomic polynomials has been the object of a number of research papers. Several survey papers give an overview.
If n has at most two distinct odd prime factors, then Migotti showed that the coefficients of are all in the set { 1, −1, 0}.
The first cyclotomic polynomial for a product of three different odd prime factors is it has a coefficient −2 (see its expression above). The converse is not true: only has coefficients in { 1, −1, 0}.
If n is a product of more different odd prime factors, the coefficients may increase to very high values. E.g., has coefficients running from −22 to 23, , the smallest n with 6 different odd primes, has coefficients of magnitude up to 532.