In mathematics, the nth cyclotomic polynomial, for any positive integer n, is the unique irreducible polynomial with integer coefficients that is a divisor of
, where k runs over the positive integers less than n and coprime to n (and i is the imaginary unit).
An important relation linking cyclotomic polynomials and primitive roots of unity is showing that
if and only if it is a d th primitive root of unity for some d that divides n.[1] If n is a prime number, then If n = 2p where p is a prime number other than 2, then For n up to 30, the cyclotomic polynomials are:[2] 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:[3] The cyclotomic polynomials are monic polynomials with integer coefficients that are irreducible over the field of the rational numbers.
, or in other words the number of nth primitive roots of unity, is
[4] Depending on the chosen definition, it is either the value of the degree or the irreducibility which is a nontrivial result.
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
in terms of a cyclotomic polynomial of square free index: If q is the product of the prime divisors of n (its radical), then[5] This allows formulas to be given for the nth cyclotomic polynomial when n has at most one odd prime factor: If p is an odd prime number, and h and k are positive integers, then For other values of n, the computation of the nth cyclotomic polynomial is similarly reduced to that of
where q is the product of the distinct odd prime divisors of n. To deal with this case, one has that, for p prime and not dividing n,[6] The problem of bounding the magnitude of the coefficients of the cyclotomic polynomials has been the object of a number of research papers.
[7] If n has at most two distinct odd prime factors, then Migotti showed that the coefficients of
[8] The first cyclotomic polynomial for a product of three different odd prime factors is
If n is a product of more different odd prime factors, the coefficients may increase to very high values.
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.[9] A combination of theorems of Bateman and Vaughan states that[7]: 10 on the one hand, for every
Similarly, Bn(z) is palindromic unless n is composite and n ≡ 3 (mod 4), in which case it is antipalindromic.
This can also be written If n is even, square-free and greater than 2 (this forces n/2 to be odd), for Cn(z) and Dn(z) with integer coefficients, Cn(z) of degree φ(n), and Dn(z) of degree φ(n) − 1.
The first few cases are: The Sister Beiter conjecture is concerned with the maximal size (in absolute value)
[12] Over a finite field with a prime number p of elements, for any integer n that is not a multiple of p, the cyclotomic polynomial
is Euler's totient function and d is the multiplicative order of p modulo n. In particular,
[13] These results are also true over the p-adic integers, since Hensel's lemma allows lifting a factorization over the field with p elements to a factorization over the p-adic integers.
for every n ≥ 3 (this follows from the fact that the roots of a cyclotomic polynomial are all non-real, for n ≥ 3).
may take for other integer values of x is strongly related with the multiplicative order modulo a prime number.
For b > 1, the multiplicative order of b modulo p is also the shortest period of the representation of 1/p in the numeral base b (see Unique prime; this explains the notation choice).
with n > 2 and b > 1, and, more generally, OEIS: A206942, for the smallest positive integers of this form.
, one can give an elementary proof for the infinitude of primes congruent to 1 modulo n,[14] which is a special case of Dirichlet's theorem on arithmetic progressions.
decompose it into linear factors and note that 1 is the closest root of unity to
The constant-coefficient linear recurrences which are periodic are precisely the power series coefficients of rational functions whose denominators are products of cyclotomic polynomials.
In the theory of combinatorial generating functions, the denominator of a rational function determines a linear recurrence for its power series coefficients.
, and the sequence has period 6 with initial values given by the coefficients of the numerator.
Gauss's book Disquisitiones Arithmeticae [Arithmetical Investigations] has been translated from Latin into French, German, and English.
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.