Cyclotomic polynomial

Short description: Irreducible polynomial whose roots are nth roots of unity

In mathematics, the nth cyclotomic polynomial, for any positive integer n, is the unique irreducible polynomial with integer coefficients that is a divisor of [math]\displaystyle{ x^n-1 }[/math] and is not a divisor of [math]\displaystyle{ x^k-1 }[/math] for any k < n. Its roots are all nth primitive roots of unity [math]\displaystyle{ e^{2i\pi\frac{k}{n}} }[/math], 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

[math]\displaystyle{ \Phi_n(x) = \prod_\stackrel{1\le k\le n}{\gcd(k,n)=1} \left(x-e^{2i\pi\frac{k}{n}}\right). }[/math]

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 ([math]\displaystyle{ e^{2i\pi/n} }[/math] is an example of such a root).

An important relation linking cyclotomic polynomials and primitive roots of unity is

[math]\displaystyle{ \prod_{d\mid n}\Phi_d(x) = x^n - 1, }[/math]

showing that x is a root of [math]\displaystyle{ x^n - 1 }[/math] if and only if it is a d th primitive root of unity for some d that divides n.

[math]\displaystyle{ \begin{align} \Phi_1(x) &= x - 1 \\ \Phi_2(x) &= x + 1 \\ \Phi_3(x) &= x^2 + x + 1 \\ \Phi_4(x) &= x^2 + 1 \\ \Phi_5(x) &= x^4 + x^3 + x^2 + x +1 \\ \Phi_6(x) &= x^2 - x + 1 \\ \Phi_7(x) &= x^6 + x^5 + x^4 + x^3 + x^2 + x + 1 \\ \Phi_8(x) &= x^4 + 1 \\ \Phi_9(x) &= x^6 + x^3 + 1 \\ \Phi_{10}(x) &= x^4 - x^3 + x^2 - x + 1 \\ \Phi_{11}(x) &= x^{10} + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1 \\ \Phi_{12}(x) &= x^4 - x^2 + 1 \\ \Phi_{13}(x) &= x^{12} + x^{11} + x^{10} + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1 \\ \Phi_{14}(x) &= x^6 - x^5 + x^4 - x^3 + x^2 - x + 1 \\ \Phi_{15}(x) &= x^8 - x^7 + x^5 - x^4 + x^3 - x + 1 \\ \Phi_{16}(x) &= x^8 + 1 \\ \Phi_{17}(x) &= x^{16} + x^{15} + x^{14} + x^{13} + x^{12} + x^{11} + x^{10} + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1\\ \Phi_{18}(x) &= x^6 - x^3 + 1 \\ \Phi_{19}(x) &= x^{18} + x^{17} + x^{16} + x^{15} + x^{14} + x^{13} + x^{12} + x^{11} + x^{10} + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1\\ \Phi_{20}(x) &= x^8 - x^6 + x^4 - x^2 + 1 \\ \Phi_{21}(x) &= x^{12} - x^{11} + x^9 - x^8 + x^6 - x^4 + x^3 - x + 1 \\ \Phi_{22}(x) &= x^{10} - x^9 + x^8 - x^7 + x^6 - x^5 + x^4 - x^3 + x^2 - x + 1 \\ \Phi_{23}(x) &= x^{22} + x^{21} + x^{20} + x^{19} + x^{18} + x^{17} + x^{16} + x^{15} + x^{14} + x^{13} + x^{12} \\ & \qquad\quad + x^{11} + x^{10} + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1 \\ \Phi_{24}(x) &= x^8 - x^4 + 1 \\ \Phi_{25}(x) &= x^{20} + x^{15} + x^{10} + x^5 + 1 \\ \Phi_{26}(x) &= x^{12} - x^{11} + x^{10} - x^9 + x^8 - x^7 + x^6 - x^5 + x^4 - x^3 + x^2 - x + 1 \\ \Phi_{27}(x) &= x^{18} + x^9 + 1 \\ \Phi_{28}(x) &= x^{12} - x^{10} + x^8 - x^6 + x^4 - x^2 + 1 \\ \Phi_{29}(x) &= x^{28} + x^{27} + x^{26} + x^{25} + x^{24} + x^{23} + x^{22} + x^{21} + x^{20} + x^{19} + x^{18} + x^{17} + x^{16} + x^{15} \\ & \qquad\quad + x^{14} + x^{13} + x^{12} + x^{11} + x^{10} + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1 \\ \Phi_{30}(x) &= x^8 + x^7 - x^5 - x^4 - x^3 + x + 1. \end{align} }[/math]

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:

[math]\displaystyle{ \begin{align} \Phi_{105}(x) &= x^{48} + x^{47} + x^{46} - x^{43} - x^{42} - 2 x^{41} - x^{40} - x^{39} + x^{36} + x^{35} + x^{34} + x^{33} + x^{32} + x^{31} - x^{28} - x^{26} \\ &\qquad\quad - x^{24} - x^{22} - x^{20} + x^{17} + x^{16} + x^{15} + x^{14} + x^{13} + x^{12} - x^9 - x^8 - 2 x^7 - x^6 - x^5 + x^2 + x + 1. \end{align} }[/math]

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 [math]\displaystyle{ \Phi_n }[/math], or in other words the number of nth primitive roots of unity, is [math]\displaystyle{ \varphi (n) }[/math], where [math]\displaystyle{ \varphi }[/math] is Euler's totient function.

The fact that [math]\displaystyle{ \Phi_n }[/math] is an irreducible polynomial of degree [math]\displaystyle{ \varphi (n) }[/math] in the ring [math]\displaystyle{ \Z[x] }[/math] 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

[math]\displaystyle{ \begin{align} x^n - 1 &=\prod_{1\leqslant k\leqslant n} \left(x- e^{2i\pi\frac{k}{n}} \right) \\ &= \prod_{d \mid n} \prod_{1 \leqslant k \leqslant n \atop \gcd(k, n) = d} \left(x- e^{2i\pi\frac{k}{n}} \right) \\ &=\prod_{d \mid n} \Phi_{\frac{n}{d}}(x) = \prod_{d\mid n} \Phi_d(x).\end{align} }[/math]

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 [math]\displaystyle{ \Phi_n(x) }[/math] as an explicit rational fraction:

[math]\displaystyle{ \Phi_n(x)=\prod_{d\mid n}(x^d-1)^{\mu \left (\frac{n}{d} \right )}, }[/math]

where [math]\displaystyle{ \mu }[/math] is the Möbius function.

The cyclotomic polynomial [math]\displaystyle{ \Phi_{n}(x) }[/math] may be computed by (exactly) dividing [math]\displaystyle{ x^n-1 }[/math] by the cyclotomic polynomials of the proper divisors of n previously computed recursively by the same method:

[math]\displaystyle{ \Phi_n(x)=\frac{x^{n}-1}{\prod_{\stackrel{d|n}{{}_{d\lt n}}}\Phi_{d}(x)} }[/math]

(Recall that [math]\displaystyle{ \Phi_{1}(x)=x-1 }[/math].)

This formula defines an algorithm for computing [math]\displaystyle{ \Phi_n(x) }[/math] 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 n is a prime number, then

[math]\displaystyle{ \Phi_n(x) = 1+x+x^2+\cdots+x^{n-1}=\sum_{k=0}^{n-1}x^k. }[/math]

If n is an odd integer greater than one, then

[math]\displaystyle{ \Phi_{2n}(x) = \Phi_n(-x). }[/math]

In particular, if n = 2p is twice an odd prime, then (as noted above)

[math]\displaystyle{ \Phi_n(x) = 1-x+x^2-\cdots+x^{p-1}=\sum_{k=0}^{p-1}(-x)^k. }[/math]

If n = p^m is a prime power (where p is prime), then

[math]\displaystyle{ \Phi_n(x) = \Phi_p(x^{p^{m-1}}) =\sum_{k=0}^{p-1}x^{kp^{m-1}}. }[/math]

More generally, if n = p^mr with r relatively prime to p, then

[math]\displaystyle{ \Phi_n(x) = \Phi_{pr}(x^{p^{m-1}}). }[/math]

These formulas may be applied repeatedly to get a simple expression for any cyclotomic polynomial [math]\displaystyle{ \Phi_n(x) }[/math] in term of a cyclotomic polynomial of square free index: If q is the product of the prime divisors of n (its radical), then

[math]\displaystyle{ \Phi_{np}(x)=\Phi_{n}(x^p)/\Phi_n(x). }[/math]

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 [math]\displaystyle{ \Phi_n }[/math] are all in the set {1, −1, 0}.

The first cyclotomic polynomial for a product of three different odd prime factors is [math]\displaystyle{ \Phi_{105}(x); }[/math] it has a coefficient −2 (see its expression above). The converse is not true: [math]\displaystyle{ \Phi_{231}(x)=\Phi_{3\times 7\times 11}(x) }[/math] 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., [math]\displaystyle{ \Phi_{15015}(x) =\Phi_{3\times 5\times 7\times 11\times 13}(x) }[/math] has coefficients running from −22 to 23, [math]\displaystyle{ \Phi_{255255}(x)=\Phi_{3\times 5\times 7\times 11\times 13\times 17}(x) }[/math], 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.

A combination of theorems of Bateman resp. Vaughan states that on the one hand, for every [math]\displaystyle{ \varepsilon\gt 0 }[/math], we have

[math]\displaystyle{ A(n) \lt e^{\left(n^{(\log 2+\varepsilon)/(\log\log n)}\right)} }[/math]

for all sufficiently large positive integers [math]\displaystyle{ n }[/math], and on the other hand, we have

[math]\displaystyle{ A(n) \gt e^{\left(n^{(\log 2)/(\log\log n)}\right)} }[/math]

for infinitely many positive integers [math]\displaystyle{ n }[/math]. This implies in particular that univariate polynomials (concretely [math]\displaystyle{ x^n-1 }[/math] for infinitely many positive integers [math]\displaystyle{ n }[/math]) can have factors (like [math]\displaystyle{ \Phi_n }[/math]) whose coefficients are superpolynomially larger than the original coefficients. This is not too far from the general Landau-Mignotte bound.

Gauss's formula

Let n be odd, square-free, and greater than 3. Then:

[math]\displaystyle{ 4\Phi_n(z) = A_n^2(z) - (-1)^{\frac{n-1}{2}}nz^2B_n^2(z) }[/math]

where both A_n(z) and B_n(z) have integer coefficients, A_n(z) has degree φ(n)/2, and B_n(z) has degree φ(n)/2 − 2. Furthermore, A_n(z) is palindromic when its degree is even; if its degree is odd it is antipalindromic. Similarly, B_n(z) is palindromic unless n is composite and ≡ 3 (mod 4), in which case it is antipalindromic.

The first few cases are

[math]\displaystyle{ \begin{align} 4\Phi_5(z) &=4(z^4+z^3+z^2+z+1)\\ &= (2z^2+z+2)^2 - 5z^2 \\[6pt] 4\Phi_7(z) &=4(z^6+z^5+z^4+z^3+z^2+z+1)\\ &= (2z^3+z^2-z-2)^2+7z^2(z+1)^2 \\ [6pt] 4\Phi_{11}(z) &=4(z^{10}+z^9+z^8+z^7+z^6+z^5+z^4+z^3+z^2+z+1)\\ &= (2z^5+z^4-2z^3+2z^2-z-2)^2+11z^2(z^3+1)^2 \end{align} }[/math]

Lucas's formula

Let n be odd, square-free and greater than 3. Then

[math]\displaystyle{ \Phi_n(z) = U_n^2(z) - (-1)^{\frac{n-1}{2}}nzV_n^2(z) }[/math]

where both U_n(z) and V_n(z) have integer coefficients, U_n(z) has degree φ(n)/2, and V_n(z) has degree φ(n)/2 − 1. This can also be written

[math]\displaystyle{ \Phi_n \left ((-1)^{\frac{n-1}{2}}z \right ) = C_n^2(z) - nzD_n^2(z). }[/math]

If n is even, square-free and greater than 2 (this forces n/2 to be odd),

[math]\displaystyle{ \Phi_{\frac{n}{2}} \left (-z^2 \right ) = \Phi_{2n}(z)= C_n^2(z) - nzD_n^2(z) }[/math]

where both C_n(z) and D_n(z) have integer coefficients, C_n(z) has degree φ(n), and D_n(z) has degree φ(n) − 1. C_n(z) and D_n(z) are both palindromic.

The first few cases are:

[math]\displaystyle{ \begin{align} \Phi_3(-z) &=\Phi_6(z) =z^2-z+1 \\ &= (z+1)^2 - 3z \\[6pt] \Phi_5(z) &=z^4+z^3+z^2+z+1 \\ &= (z^2+3z+1)^2 - 5z(z+1)^2 \\[6pt] \Phi_{6/2}(-z^2) &=\Phi_{12}(z)=z^4-z^2+1 \\ &= (z^2+3z+1)^2 - 6z(z+1)^2 \end{align} }[/math]

Sister Beiter conjecture

The Sister Beiter conjecture is concerned with the maximal size (in absolute value) [math]\displaystyle{ A(pqr) }[/math] of coefficients of ternary cyclotomic polynomials [math]\displaystyle{ \Phi_{pqr}(x) }[/math] where [math]\displaystyle{ 3\leq p\leq q\leq r }[/math] are three prime numbers.

Cyclotomic polynomials over a finite field and over the p-adic integers

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 [math]\displaystyle{ \Phi_n }[/math] factorizes into [math]\displaystyle{ \frac{\varphi (n)}{d} }[/math] irreducible polynomials of degree d, where [math]\displaystyle{ \varphi (n) }[/math] is Euler's totient function and d is the multiplicative order of p modulo n. In particular, [math]\displaystyle{ \Phi_n }[/math] is irreducible if and only if p is a primitive root modulo n, that is, p does not divide n, and its multiplicative order modulo n is [math]\displaystyle{ \varphi(n) }[/math], the degree of [math]\displaystyle{ \Phi_n }[/math].

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.

Polynomial values

If x takes any real value, then [math]\displaystyle{ \Phi_n(x)\gt 0 }[/math] for every n ≥ 3 (this follows from the fact that the roots of a cyclotomic polynomial are all non-real, for n ≥ 3).

For studying the values that a cyclotomic polynomial may take when x is given an integer value, it suffices to consider only the case n ≥ 3, as the cases n = 1 and n = 2 are trivial (one has [math]\displaystyle{ \Phi_1(x)=x-1 }[/math] and [math]\displaystyle{ \Phi_2(x)=x+1 }[/math]).

For n ≥ 2, one has

[math]\displaystyle{ \Phi_n(0) =1, }[/math]

[math]\displaystyle{ \Phi_n(1) =1 }[/math] if n is not a prime power,

[math]\displaystyle{ \Phi_n(1) =p }[/math] if [math]\displaystyle{ n=p^k }[/math] is a prime power with k ≥ 1.

The values that a cyclotomic polynomial [math]\displaystyle{ \Phi_n(x) }[/math] may take for other integer values of x is strongly related with the multiplicative order modulo a prime number.

More precisely, given a prime number p and an integer b coprime with p, the multiplicative order of b modulo p, is the smallest positive integer n such that p is a divisor of [math]\displaystyle{ b^n-1. }[/math] 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).

The definition of the multiplicative order implies that, if n is the multiplicative order of b modulo p, then p is a divisor of [math]\displaystyle{ \Phi_n(b). }[/math] The converse is not true, but one has the following.

If n > 0 is a positive integer and b > 1 is an integer, then (see below for a proof)

[math]\displaystyle{ \Phi_n(b)=2^kgh, }[/math]

where

• k is a non-negative integer, always equal to 0 when b is even. (In fact, if n is neither 1 nor 2, then k is either 0 or 1. Besides, if n is not a power of 2, then k is always equal to 0)
• g is 1 or the largest odd prime factor of n.
• h is odd, coprime with n, and its prime factors are exactly the odd primes p such that n is the multiplicative order of b modulo p.

This implies that, if p is an odd prime divisor of [math]\displaystyle{ \Phi_n(b), }[/math] then either n is a divisor of p − 1 or p is a divisor of n. In the latter case, [math]\displaystyle{ p^2 }[/math] does not divide [math]\displaystyle{ \Phi_n(b). }[/math]

Zsigmondy's theorem implies that the only cases where b > 1 and h = 1 are

[math]\displaystyle{ \begin{align} \Phi_1(2) &=1 \\ \Phi_2 \left (2^k-1 \right ) & =2^k && k \gt 0 \\ \Phi_6(2) &=3 \end{align} }[/math]

It follows from above factorization that the odd prime factors of

[math]\displaystyle{ \frac{\Phi_n(b)}{\gcd(n,\Phi_n(b))} }[/math]

are exactly the odd primes p such that n is the multiplicative order of b modulo p. This fraction may be even only when b is odd. In this case, the multiplicative order of b modulo 2 is always 1.

There are many pairs (n, b) with b > 1 such that [math]\displaystyle{ \Phi_n(b) }[/math] is prime. In fact, Bunyakovsky conjecture implies that, for every n, there are infinitely many b > 1 such that [math]\displaystyle{ \Phi_n(b) }[/math] is prime. See OEIS: A085398 for the list of the smallest b > 1 such that [math]\displaystyle{ \Phi_n(b) }[/math] is prime (the smallest b > 1 such that [math]\displaystyle{ \Phi_n(b) }[/math] is prime is about [math]\displaystyle{ \lambda \cdot \varphi(n) }[/math], where [math]\displaystyle{ \lambda }[/math] is Euler–Mascheroni constant, and [math]\displaystyle{ \varphi }[/math] is Euler's totient function). See also OEIS: A206864 for the list of the smallest primes of the form [math]\displaystyle{ \Phi_n(b) }[/math] with n > 2 and b > 1, and, more generally, OEIS: A206942, for the smallest positive integers of this form.

Proofs

Values of [math]\displaystyle{ \Phi_n(1). }[/math] If [math]\displaystyle{ n=p^{k+1} }[/math] is a prime power, then [math]\displaystyle{ \Phi_n(x)=1+x^{p^k}+x^{2p^{k}}+\cdots+x^{(p-1)p^k} \qquad \text{and} \qquad \Phi_n(1)=p. }[/math] If n is not a prime power, let [math]\displaystyle{ P(x)=1+x+\cdots+x^{n-1}, }[/math] we have [math]\displaystyle{ P(1)=n, }[/math] and P is the product of the [math]\displaystyle{ \Phi_k(x) }[/math] for k dividing n and different of 1. If p is a prime divisor of multiplicity m in n, then [math]\displaystyle{ \Phi_p(x), \Phi_{p^2}(x), \cdots, \Phi_{p^m}(x) }[/math] divide P(x), and their values at 1 are m factors equal to p of [math]\displaystyle{ n=P(1). }[/math] As m is the multiplicity of p in n, p cannot divide the value at 1 of the other factors of [math]\displaystyle{ P(x). }[/math] Thus there is no prime that divides [math]\displaystyle{ \Phi_n(1). }[/math] If n is the multiplicative order of b modulo p, then [math]\displaystyle{ p \mid \Phi_n(b). }[/math] By definition, [math]\displaystyle{ p \mid b^n-1. }[/math] If [math]\displaystyle{ p \nmid \Phi_n(b), }[/math] then p would divide another factor [math]\displaystyle{ \Phi_k(b) }[/math] of [math]\displaystyle{ b^n-1, }[/math] and would thus divide [math]\displaystyle{ b^k-1, }[/math] showing that, if there would be the case, n would not be the multiplicative order of b modulo p. The other prime divisors of [math]\displaystyle{ \Phi_n(b) }[/math] are divisors of n. Let p be a prime divisor of [math]\displaystyle{ \Phi_n(b) }[/math] such that n is not be the multiplicative order of b modulo p. If k is the multiplicative order of b modulo p, then p divides both [math]\displaystyle{ \Phi_n(b) }[/math] and [math]\displaystyle{ \Phi_k(b). }[/math] The resultant of [math]\displaystyle{ \Phi_n(x) }[/math] and [math]\displaystyle{ \Phi_k(x) }[/math] may be written [math]\displaystyle{ P\Phi_k+Q\Phi_n, }[/math] where P and Q are polynomials. Thus p divides this resultant. As k divides n, and the resultant of two polynomials divides the discriminant of any common multiple of these polynomials, p divides also the discriminant [math]\displaystyle{ n^n }[/math] of [math]\displaystyle{ x^n-1. }[/math] Thus p divides n. g and h are coprime. In other words, if p is a prime common divisor of n and [math]\displaystyle{ \Phi_n(b), }[/math] then n is not the multiplicative order of b modulo p. By Fermat's little theorem, the multiplicative order of b is a divisor of p − 1, and thus smaller than n. g is square-free. In other words, if p is a prime common divisor of n and [math]\displaystyle{ \Phi_n(b), }[/math] then [math]\displaystyle{ p^2 }[/math] does not divide [math]\displaystyle{ \Phi_n(b). }[/math] Let n = pm. It suffices to prove that [math]\displaystyle{ p^2 }[/math] does not divide S(b) for some polynomial S(x), which is a multiple of [math]\displaystyle{ \Phi_n(x). }[/math] We take [math]\displaystyle{ S(x)=\frac{x^n-1}{x^m-1} = 1 + x^m + x^{2m} + \cdots + x^{(p-1)m}. }[/math] The multiplicative order of b modulo p divides gcd(n, p − 1), which is a divisor of m = n/p. Thus c = bm − 1 is a multiple of p. Now, [math]\displaystyle{ S(b) = \frac{(1+c)^p-1}{c} = p+ \binom{p}{2}c + \cdots + \binom{p}{p}c^{p-1}. }[/math] As p is prime and greater than 2, all the terms but the first one are multiples of [math]\displaystyle{ p^2. }[/math] This proves that [math]\displaystyle{ p^2 \nmid \Phi_n(b). }[/math]

Applications

Using [math]\displaystyle{ \Phi_n }[/math], 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.

Proof

Suppose [math]\displaystyle{ p_1, p_2, \ldots, p_k }[/math] is a finite list of primes congruent to [math]\displaystyle{ 1 }[/math] modulo [math]\displaystyle{ n. }[/math] Let [math]\displaystyle{ N = np_1p_2\cdots p_k }[/math] and consider [math]\displaystyle{ \Phi_n(N) }[/math]. Let [math]\displaystyle{ q }[/math] be a prime factor of [math]\displaystyle{ \Phi_n(N) }[/math] (to see that [math]\displaystyle{ \Phi_n(N) \neq \pm 1 }[/math] decompose it into linear factors and note that 1 is the closest root of unity to [math]\displaystyle{ N }[/math]). Since [math]\displaystyle{ \Phi_n(x) \equiv \pm 1 \pmod x, }[/math] we know that [math]\displaystyle{ q }[/math] is a new prime not in the list. We will show that [math]\displaystyle{ q \equiv 1 \pmod n. }[/math] Let [math]\displaystyle{ m }[/math] be the order of [math]\displaystyle{ N }[/math] modulo [math]\displaystyle{ q. }[/math] Since [math]\displaystyle{ \Phi_n(N) \mid N^n - 1 }[/math] we have [math]\displaystyle{ N^n -1 \equiv 0 \pmod{q} }[/math]. Thus [math]\displaystyle{ m \mid n }[/math]. We will show that [math]\displaystyle{ m = n }[/math]. Assume for contradiction that [math]\displaystyle{ m \lt n }[/math]. Since [math]\displaystyle{ \prod_{d \mid m} \Phi_d(N) = N^m - 1 \equiv 0 \pmod q }[/math] we have [math]\displaystyle{ \Phi_d(N) \equiv 0 \pmod q, }[/math] for some [math]\displaystyle{ d \lt n }[/math]. Then [math]\displaystyle{ N }[/math] is a double root of [math]\displaystyle{ \prod_{d \mid n} \Phi_d(x) \equiv x^n -1 \pmod q. }[/math] Thus [math]\displaystyle{ N }[/math] must be a root of the derivative so [math]\displaystyle{ \left.\frac{d(x^n -1)}{dx}\right|_N \equiv nN^{n-1} \equiv 0 \pmod q. }[/math] But [math]\displaystyle{ q \nmid N }[/math] and therefore [math]\displaystyle{ q \nmid n. }[/math] This is a contradiction so [math]\displaystyle{ m = n }[/math]. The order of [math]\displaystyle{ N \pmod q, }[/math] which is [math]\displaystyle{ n }[/math], must divide [math]\displaystyle{ q-1 }[/math]. Thus [math]\displaystyle{ q \equiv 1 \pmod n. }[/math]

See also

• Cyclotomic field
• Aurifeuillean factorization
• Root of unity

Further reading

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.

• Gauss, Carl Friedrich (1986), Disquisitiones Arithmeticae, Translated into English by Clarke, Arthur A. (2nd corr. ed.), New York: Springer, ISBN 0387962549 
• Gauss, Carl Friedrich (1965), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithmeticae & other papers on number theory), Translated into German by Maser, H. (2nd ed.), New York: Chelsea, ISBN 0-8284-0191-8 
• Lemmermeyer, Franz (2000), Reciprocity Laws: from Euler to Eisenstein, Springer Monographs in Mathematics, Berlin: Springer, doi:10.1007/978-3-662-12893-0, ISBN 978-3-642-08628-1 

External links

• Weisstein, Eric W.. "Cyclotomic polynomial". http://mathworld.wolfram.com/CyclotomicPolynomial.html. 
• Hazewinkel, Michiel, ed. (2001), "Cyclotomic polynomials", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4, https://www.encyclopediaofmath.org/index.php?title=p/c027580 
• OEIS sequence A013595 (Triangle of coefficients of cyclotomic polynomial Phi_n(x) (exponents in increasing order))
• OEIS sequence A013594 (Smallest order of cyclotomic polynomial containing n or −n as a coefficient)