Cyclotomic polynomial

In mathematics, the "n"th cyclotomic polynomial, for any positive integer "n", is the unique irreducible polynomial with integer coefficients that is a divisor of formula_1 and is not a divisor of formula_2 for any Its roots are all "n"th primitive roots of unity 
formula_3, 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 "n"th 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 "n"th-root of unity (formula_5 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 formula_7 if and only if it is a "d"th primitive root of unity for some "d" that divides "n".
Examples.
If "n" is a prime number, then 
If "n" = 2"p" 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 lowest 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 palindromics of even degree.
The degree of formula_12, or in other words the number of "n"th primitive roots of unity, is formula_13, where formula_14 is Euler's totient function.
The fact that formula_12 is an irreducible polynomial of degree formula_13 in the ring formula_17 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 formula_19 as an explicit rational fraction:
where formula_21 is the Möbius function.
The cyclotomic polynomial formula_22 may be computed by (exactly) dividing formula_1 by the cyclotomic polynomials of the proper divisors of "n" previously computed recursively by the same method:
This formula allows computation of formula_19 on a computer for any "n", as soon as 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 formula_19 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 formula_37 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.
If "n" has at most two distinct odd prime factors, then Migotti showed that the coefficients of formula_12 are all in the set {1, −1, 0}.
The first cyclotomic polynomial for a product of three different odd prime factors is formula_40 it has a coefficient −2 (see its expression above). The converse is not true: formula_41 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., formula_42 has coefficients running from −22 to 23, formula_43, the smallest "n" with 6 different odd primes, has coefficients of magnitude up to 532.
Let "A"("n") denote the maximum absolute value of the coefficients of Φ"n". It is known that for any positive "k", the number of "n" up to "x" with "A"("n") > "n""k" is at least "c"("k")⋅"x" for a positive "c"("k") depending on "k" and "x" sufficiently large. In the opposite direction, for any function ψ("n") tending to infinity with "n" we have "A"("n") bounded above by "n"ψ("n") for almost all "n".
Gauss's formula.
Let "n" be odd, square-free, and greater than 3. Then:
where both "An"("z") and "Bn"("z") have integer coefficients, "An"("z") has degree "φ"("n")/2, and "Bn"("z") has degree "φ"("n")/2 − 2. Furthermore, "An"("z") is palindromic when its degree is even; if its degree is odd it is antipalindromic. Similarly, "Bn"("z") is palindromic unless "n" is composite and ≡ 3 (mod 4), in which case it is antipalindromic.
The first few cases are
Lucas's formula.
Let "n" be odd, square-free and greater than 3. Then
where both "Un"("z") and "Vn"("z") have integer coefficients, "Un"("z") has degree "φ"("n")/2, and "Vn"("z") has degree "φ"("n")/2 − 1. This can also be written
If "n" is even, square-free and greater than 2 (this forces "n"/2 to be odd),
where both "Cn"("z") and "Dn"("z") have integer coefficients, "Cn"("z") has degree "φ"("n"), and "Dn"("z") has degree "φ"("n") − 1. "Cn"("z") and "Dn"("z") are both palindromic.
The first few cases are:
Cyclotomic polynomials over a finite field and over the -adic integers.
Over a finite field with a prime number of elements, for any integer that is not a multiple of , the cyclotomic polynomial formula_12 factorizes into formula_51 irreducible polynomials of degree , where formula_13 is Euler's totient function and is the multiplicative order of modulo . In particular, formula_12 is irreducible if and only if is a primitive root modulo, that is, does not divide , and its multiplicative order modulo is formula_54, the degree of formula_12.
These results are also true over the -adic integers, since Hensel's lemma allows lifting a factorization over the field with elements to a factorization over the -adic integers.
Polynomial values.
If takes any real value, then formula_56 for every (this follows from the fact that the roots of a cyclotomic polynomial are all non-real, for ).
For studying the values that a cyclotomic polynomial may take when is given an integer value, it suffices to consider only the case , as the cases and are trivial (one has formula_57 and formula_58). 
For , one has
The values that a cyclotomic polynomial formula_19 may take for other integer values of is strongly related with the multiplicative order modulo a prime number. 
More precisely, given a prime number and an integer coprime with , the multiplicative order of modulo , is the smallest positive integer such that is a divisor of formula_64 For , the multiplicative order of modulo is also the shortest period of the representation of in the numeral base (see Unique prime; this explains the notation choice). 
The definition of the multiplicative order implies that, if is the multiplicative order of modulo , then is a divisor of formula_65 The converse is not true, but one has the following.
If is a positive integer and is an integer, then (see below for a proof)
where 
This implies that, if is an odd prime divisor of formula_67 then either is a divisor of or is a divisor of . In the latter case, formula_68 does not divide formula_65
Zsigmondy's theorem implies that the only cases where and are
It follows from above factorization that the odd prime factors of
are exactly the odd primes such that is the multiplicative order of modulo . This fraction may be even only when is odd. In this case, the multiplicative order of modulo is always .
There are many pairs with such that formula_72 is prime. In fact, Bunyakovsky conjecture implies that, for every , there are infinitely many such that formula_72 is prime. See for the list of the smallest such that formula_72 is prime (the smallest such that formula_72 is prime is about formula_76, where formula_77 is Euler–Mascheroni constant, and formula_14 is Euler's totient function). See also for the list of the smallest primes of the form formula_72 with and , and, more generally, , for the smallest positive integers of this form.
Applications.
Using formula_12, one can give an elementary proof for the infinitude of primes congruent to 1 modulo "n", which is a special case of Dirichlet's theorem on arithmetic progressions.
Suppose formula_116 is a finite list of primes congruent to formula_117 modulo formula_118 Let formula_119 and consider formula_120. Let formula_121 be a prime factor of formula_120 (to see that formula_123 decompose it into linear factors and note that 1 is the closest root of unity to formula_124). Since formula_125 we know that formula_121 is a new prime not in the list. We will show that formula_127
Let formula_128 be the order of formula_124 modulo formula_130 Since formula_131 we have formula_132. Thus formula_133. We will show that formula_134.
Assume for contradiction that formula_135. Since 
we have 
for some formula_138. Then formula_124 is a double root of 
Thus formula_124 must be a root of the derivative so 
But formula_143 and therefore formula_144 This is a contradiction so formula_134. The order of formula_146 which is formula_147, must divide formula_148. Thus formula_127
References.
Gauss's book "Disquisitiones Arithmeticae" has been translated from Latin into English and German. The German edition includes all of his papers on number theory: all the proofs of quadratic reciprocity, the determination of the sign of the Gauss sum, the investigations into biquadratic reciprocity, and unpublished notes.