Cyclotomic polynomial

In mathematics, the nth cyclotomic polynomial, for any positive integer n, is the unique irreducible polynomial with integer coefficients that is a divisor of $x^n-1$ and is not a divisor of $x^k-1$ for any k < n. Its roots are all nth primitive roots of unity $e^{2i\pi \frac{k}{n}}$, where k runs over the positive integers less than n and coprime to n (and i is the imaginary unit). In other words, the nth cyclotomic polynomial is equal to

${\mathrm{\Phi }}_n(x)=\prod _{\stackrel{1\le k\le n}{\gcd (k,n)=1}}(x-e^{2i\pi \frac{k}{n}}).$

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 ($e^{2i\pi /n}$ is an example of such a root). An important relation linking cyclotomic polynomials and primitive roots of unity is

$\prod _{d\mid n}{\mathrm{\Phi }}_d(x)=x^n-1,$

showing that $x$ is a root of $x^n-1$ 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

${\mathrm{\Phi }}_n(x)=1+x+x^2+\cdots +x^{n-1}=\sum _{k=0}^{n-1}{x}^k.$

If n = 2p where p is a prime number other than 2, then

${\mathrm{\Phi }}_{2p}(x)=1-x+x^2-\cdots +x^{p-1}=\sum _{k=0}^{p-1}(-x{)}^k.$

For n up to 30, the cyclotomic polynomials are:

$\begin{array}{rl}{\mathrm{\Phi }}_1(x)& =x-1\\ {\mathrm{\Phi }}_2(x)& =x+1\\ {\mathrm{\Phi }}_3(x)& =x^2+x+1\\ {\mathrm{\Phi }}_4(x)& =x^2+1\\ {\mathrm{\Phi }}_5(x)& =x^4+x^3+x^2+x+1\\ {\mathrm{\Phi }}_6(x)& =x^2-x+1\\ {\mathrm{\Phi }}_7(x)& =x^6+x^5+x^4+x^3+x^2+x+1\\ {\mathrm{\Phi }}_8(x)& =x^4+1\\ {\mathrm{\Phi }}_9(x)& =x^6+x^3+1\\ {\mathrm{\Phi }}_{10}(x)& =x^4-x^3+x^2-x+1\\ {\mathrm{\Phi }}_{11}(x)& =x^{10}+x^9+x^8+x^7+x^6+x^5+x^4+x^3+x^2+x+1\\ {\mathrm{\Phi }}_{12}(x)& =x^4-x^2+1\\ {\mathrm{\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\\ {\mathrm{\Phi }}_{14}(x)& =x^6-x^5+x^4-x^3+x^2-x+1\\ {\mathrm{\Phi }}_{15}(x)& =x^8-x^7+x^5-x^4+x^3-x+1\\ {\mathrm{\Phi }}_{16}(x)& =x^8+1\\ {\mathrm{\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\\ {\mathrm{\Phi }}_{18}(x)& =x^6-x^3+1\\ {\mathrm{\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\\ {\mathrm{\Phi }}_{20}(x)& =x^8-x^6+x^4-x^2+1\\ {\mathrm{\Phi }}_{21}(x)& =x^{12}-x^{11}+x^9-x^8+x^6-x^4+x^3-x+1\\ {\mathrm{\Phi }}_{22}(x)& =x^{10}-x^9+x^8-x^7+x^6-x^5+x^4-x^3+x^2-x+1\\ {\mathrm{\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}\\ & +x^{11}+x^{10}+x^9+x^8+x^7+x^6+x^5+x^4+x^3+x^2+x+1\\ {\mathrm{\Phi }}_{24}(x)& =x^8-x^4+1\\ {\mathrm{\Phi }}_{25}(x)& =x^{20}+x^{15}+x^{10}+x^5+1\\ {\mathrm{\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\\ {\mathrm{\Phi }}_{27}(x)& =x^{18}+x^9+1\\ {\mathrm{\Phi }}_{28}(x)& =x^{12}-x^{10}+x^8-x^6+x^4-x^2+1\\ {\mathrm{\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}\\ & +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\\ {\mathrm{\Phi }}_{30}(x)& =x^8+x^7-x^5-x^4-x^3+x+1.\end{array}$

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:

$\begin{array}{rl}{\mathrm{\Phi }}_{105}(x)=& x^{48}+x^{47}+x^{46}-x^{43}-x^{42}-2x^{41}-x^{40}-x^{39}+x^{36}+x^{35}+x^{34}\\ & +x^{33}+x^{32}+x^{31}-x^{28}-x^{26}-x^{24}-x^{22}-x^{20}+x^{17}+x^{16}+x^{15}\\ & +x^{14}+x^{13}+x^{12}-x^9-x^8-2x^7-x^6-x^5+x^2+x+1.\end{array}$

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 ${\mathrm{\Phi }}_n$, or in other words the number of nth primitive roots of unity, is $\phi (n)$, where $\phi$ is Euler's totient function. The fact that ${\mathrm{\Phi }}_n$ is an irreducible polynomial of degree $\phi (n)$ in the ring $\mathbb{\mathbb{Z}}[x]$ 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

$\begin{array}{rl}{x}^n-1& =\prod _{1⩽k⩽n}(x-e^{2i\pi \frac{k}{n}})\\ & =\prod _{d\mid n}\prod _{\genfrac{}{}{0ex}{}{1⩽k⩽n}{\gcd (k,n)=d}}(x-e^{2i\pi \frac{k}{n}})\\ & =\prod _{d\mid n}{\mathrm{\Phi }}_{\frac{n}{d}}(x)=\prod _{d\mid n}{\mathrm{\Phi }}_d(x).\end{array}$

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 ${\mathrm{\Phi }}_n(x)$ to be expressed as an explicit rational fraction:

${\mathrm{\Phi }}_n(x)=\prod _{d\mid n}(x^d-1{)}^{\mu \left(\frac{n}{d}\right)},$

where $\mu$ is the Möbius function. The cyclotomic polynomial ${\mathrm{\Phi }}_n(x)$ may be computed by (exactly) dividing $x^n-1$ by the cyclotomic polynomials of the proper divisors of n previously computed recursively by the same method:

${\mathrm{\Phi }}_n(x)=\frac{x^n-1}{\prod _{\stackrel{d|n}{{}_{d<n}}}{\mathrm{\Phi }}_d(x)}$

(Recall that ${\mathrm{\Phi }}_1(x)=x-1$.) This formula defines an algorithm for computing ${\mathrm{\Phi }}_n(x)$ 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

${\mathrm{\Phi }}_n(x)=1+x+x^2+\cdots +x^{n-1}=\sum _{k=0}^{n-1}{x}^k.$

If n is an odd integer greater than one, then

${\mathrm{\Phi }}_{2n}(x)={\mathrm{\Phi }}_n(-x).$

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

${\mathrm{\Phi }}_n(x)=1-x+x^2-\cdots +x^{p-1}=\sum _{k=0}^{p-1}(-x{)}^k.$

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

${\mathrm{\Phi }}_n(x)={\mathrm{\Phi }}_p(x^{p^{m-1}})=\sum _{k=0}^{p-1}{x}^{k{p}^{m-1}}.$

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

${\mathrm{\Phi }}_n(x)={\mathrm{\Phi }}_{pr}(x^{p^{m-1}}).$

These formulas may be applied repeatedly to get a simple expression for any cyclotomic polynomial ${\mathrm{\Phi }}_n(x)$ in terms of a cyclotomic polynomial of square free index: If q is the product of the prime divisors of n (its radical), then

${\mathrm{\Phi }}_n(x)={\mathrm{\Phi }}_q(x^{n/q}).$

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

${\mathrm{\Phi }}_{2^h}(x)=x^{2^{h-1}}+1,$

${\mathrm{\Phi }}_{p^k}(x)=\sum _{j=0}^{p-1}{x}^{j{p}^{k-1}},$

${\mathrm{\Phi }}_{2^h{p}^k}(x)=\sum _{j=0}^{p-1}(-1{)}^j{x}^{j{2}^{h-1}{p}^{k-1}}.$

For the other values of n, the computation of the nth cyclotomic polynomial is similarly reduced to that of ${\mathrm{\Phi }}_q(x),$ 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,

${\mathrm{\Phi }}_{np}(x)={\mathrm{\Phi }}_n(x^p)/{\mathrm{\Phi }}_n(x).$

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 ${\mathrm{\Phi }}_n$ are all in the set {1, −1, 0}. The first cyclotomic polynomial for a product of three different odd prime factors is ${\mathrm{\Phi }}_{105}(x);$ it has a coefficient −2 (see its expression above). The converse is not true: ${\mathrm{\Phi }}_{231}(x)={\mathrm{\Phi }}_{3\times 7\times 11}(x)$ 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., ${\mathrm{\Phi }}_{15015}(x)={\mathrm{\Phi }}_{3\times 5\times 7\times 11\times 13}(x)$ has coefficients running from −22 to 23, ${\mathrm{\Phi }}_{255255}(x)={\mathrm{\Phi }}_{3\times 5\times 7\times 11\times 13\times 17}(x)$, 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 $\epsilon >0$, we have

$A(n)<e^{\left(n^{(\log 2+\epsilon )/(\log \log n)}\right)}$

for all sufficiently large positive integers $n$, and on the other hand, we have

$A(n)>e^{\left(n^{(\log 2)/(\log \log n)}\right)}$

for infinitely many positive integers $n$. This implies in particular that univariate polynomials (concretely $x^n-1$ for infinitely many positive integers $n$) can have factors (like ${\mathrm{\Phi }}_n$) 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:

$4{\mathrm{\Phi }}_n(z)=A_n^2(z)-(-1{)}^{\frac{n-1}{2}}n{z}^2{B}_n^2(z)$

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

$\begin{array}{rl}4{\mathrm{\Phi }}_5(z)& =4(z^4+z^3+z^2+z+1)\\ & =(2z^2+z+2{)}^2-5z^2\\ 4{\mathrm{\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{\mathrm{\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{array}$

Lucas's formula

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

${\mathrm{\Phi }}_n(z)=U_n^2(z)-(-1{)}^{\frac{n-1}{2}}nz{V}_n^2(z)$

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

${\mathrm{\Phi }}_n((-1{)}^{\frac{n-1}{2}}z)=C_n^2(z)-nz{D}_n^2(z).$

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

${\mathrm{\Phi }}_{\frac{n}{2}}(-z^2)={\mathrm{\Phi }}_{2n}(z)=C_n^2(z)-nz{D}_n^2(z)$

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:

$\begin{array}{rl}{\mathrm{\Phi }}_3(-z)& ={\mathrm{\Phi }}_6(z)=z^2-z+1\\ & =(z+1{)}^2-3z\\ {\mathrm{\Phi }}_5(z)& =z^4+z^3+z^2+z+1\\ & =(z^2+3z+1{)}^2-5z(z+1{)}^2\\ {\mathrm{\Phi }}_{6/2}(-z^2)& ={\mathrm{\Phi }}_{12}(z)=z^4-z^2+1\\ & =(z^2+3z+1{)}^2-6z(z+1{)}^2\end{array}$

Sister Beiter conjecture

The Sister Beiter conjecture is concerned with the maximal size (in absolute value) $A(pqr)$ of coefficients of ternary cyclotomic polynomials ${\mathrm{\Phi }}_{pqr}(x)$ where $3\le p\le q\le r$ are three prime numbers.

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

See also: Finite field § Roots of unity

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 ${\mathrm{\Phi }}_n$ factorizes into $\frac{\phi (n)}{d}$ irreducible polynomials of degree d, where $\phi (n)$ is Euler's totient function and d is the multiplicative order of p modulo n. In particular, ${\mathrm{\Phi }}_n$ 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 $\phi (n)$, the degree of ${\mathrm{\Phi }}_n$. 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 ${\mathrm{\Phi }}_n(x)>0$ 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 ${\mathrm{\Phi }}_1(x)=x-1$ and ${\mathrm{\Phi }}_2(x)=x+1$). For n ≥ 2, one has

${\mathrm{\Phi }}_n(0)=1,$

${\mathrm{\Phi }}_n(1)=1$ if n is not a prime power,

${\mathrm{\Phi }}_n(1)=p$ if $n=p^k$ is a prime power with k ≥ 1.

The values that a cyclotomic polynomial ${\mathrm{\Phi }}_n(x)$ 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 $b^n-1.$ 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 ${\mathrm{\Phi }}_n(b).$ 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)

${\mathrm{\Phi }}_n(b)=2^{k}gh,$

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 ${\mathrm{\Phi }}_n(b),$ then either n is a divisor of p − 1 or p is a divisor of n. In the latter case, $p^2$ does not divide ${\mathrm{\Phi }}_n(b).$ Zsigmondy's theorem implies that the only cases where b > 1 and h = 1 are

$\begin{array}{rl}{\mathrm{\Phi }}_1(2)& =1\\ {\mathrm{\Phi }}_2(2^k-1)& =2^k& & k>0\\ {\mathrm{\Phi }}_6(2)& =3\end{array}$

It follows from above factorization that the odd prime factors of

$\frac{{\mathrm{\Phi }}_n(b)}{\gcd (n,{\mathrm{\Phi }}_n(b))}$

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 ${\mathrm{\Phi }}_n(b)$ is prime. In fact, Bunyakovsky conjecture implies that, for every n, there are infinitely many b > 1 such that ${\mathrm{\Phi }}_n(b)$ is prime. See OEIS: A085398 for the list of the smallest b > 1 such that ${\mathrm{\Phi }}_n(b)$ is prime (the smallest b > 1 such that ${\mathrm{\Phi }}_n(b)$ is prime is about $\gamma \cdot \phi (n)$, where $\gamma$ is Euler–Mascheroni constant, and $\phi$ is Euler's totient function). See also OEIS: A206864 for the list of the smallest primes of the form ${\mathrm{\Phi }}_n(b)$ with n > 2 and b > 1, and, more generally, OEIS: A206942, for the smallest positive integers of this form.

Proofs

Values of ${\mathrm{\Phi }}_n(1).$ If $n=p^{k+1}$ is a prime power, then ${\mathrm{\Phi }}_n(x)=1+x^{p^k}+x^{2p^k}+\cdots +x^{(p-1)p^k}\text{and}{\mathrm{\Phi }}_n(1)=p.$ If n is not a prime power, let $P(x)=1+x+\cdots +x^{n-1},$ we have $P(1)=n,$ and P is the product of the ${\mathrm{\Phi }}_k(x)$ for k dividing n and different of 1. If p is a prime divisor of multiplicity m in n, then ${\mathrm{\Phi }}_p(x),{\mathrm{\Phi }}_{p^2}(x),\cdots ,{\mathrm{\Phi }}_{p^m}(x)$ divide P(x), and their values at 1 are m factors equal to p of $n=P(1).$ As m is the multiplicity of p in n, p cannot divide the value at 1 of the other factors of $P(x).$ Thus there is no prime that divides ${\mathrm{\Phi }}_n(1).$ If n is the multiplicative order of b modulo p, then $p\mid {\mathrm{\Phi }}_n(b).$ By definition, $p\mid b^n-1.$ If $p\nmid {\mathrm{\Phi }}_n(b),$ then p would divide another factor ${\mathrm{\Phi }}_k(b)$ of $b^n-1,$ and would thus divide $b^k-1,$ showing that, if there would be the case, n would not be the multiplicative order of b modulo p. The other prime divisors of ${\mathrm{\Phi }}_n(b)$ are divisors of n. Let p be a prime divisor of ${\mathrm{\Phi }}_n(b)$ 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 ${\mathrm{\Phi }}_n(b)$ and ${\mathrm{\Phi }}_k(b).$ The resultant of ${\mathrm{\Phi }}_n(x)$ and ${\mathrm{\Phi }}_k(x)$ may be written $P{\mathrm{\Phi }}_k+Q{\mathrm{\Phi }}_n,$ 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 $n^n$ of $x^n-1.$ Thus p divides n. g and h are coprime. In other words, if p is a prime common divisor of n and ${\mathrm{\Phi }}_n(b),$ 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 ${\mathrm{\Phi }}_n(b),$ then $p^2$ does not divide ${\mathrm{\Phi }}_n(b).$ Let n = pm. It suffices to prove that $p^2$ does not divide S(b) for some polynomial S(x), which is a multiple of ${\mathrm{\Phi }}_n(x).$ We take $S(x)=\frac{x^n-1}{x^m-1}=1+x^m+x^{2m}+\cdots +x^{(p-1)m}.$ 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, $S(b)=\frac{(1+c{)}^p-1}{c}=p+(\genfrac{}{}{0ex}{}{p}{2})c+\cdots +(\genfrac{}{}{0ex}{}{p}{p})c^{p-1}.$ As p is prime and greater than 2, all the terms but the first one are multiples of $p^2.$ This proves that $p^2\nmid {\mathrm{\Phi }}_n(b).$

Applications

Using ${\mathrm{\Phi }}_n$, 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 $p_1,p_2,\dots ,p_k$ is a finite list of primes congruent to $1$ modulo $n.$ Let $N=n{p}_1{p}_2\cdots p_k$ and consider ${\mathrm{\Phi }}_n(N)$. Let $q$ be a prime factor of ${\mathrm{\Phi }}_n(N)$ (to see that ${\mathrm{\Phi }}_n(N)\ne \pm 1$ decompose it into linear factors and note that 1 is the closest root of unity to $N$). Since ${\mathrm{\Phi }}_n(x)\equiv \pm 1(\mathrm{mod}x),$ we know that $q$ is a new prime not in the list. We will show that $q\equiv 1(\mathrm{mod}n).$ Let $m$ be the order of $N$ modulo $q.$ Since ${\mathrm{\Phi }}_n(N)\mid N^n-1$ we have $N^n-1\equiv 0(\mathrm{mod}q)$. Thus $m\mid n$. We will show that $m=n$. Assume for contradiction that $m<n$. Since $\prod _{d\mid m}{\mathrm{\Phi }}_d(N)=N^m-1\equiv 0(\mathrm{mod}q)$ we have ${\mathrm{\Phi }}_d(N)\equiv 0(\mathrm{mod}q),$ for some $d<n$. Then $N$ is a double root of $\prod _{d\mid n}{\mathrm{\Phi }}_d(x)\equiv x^n-1(\mathrm{mod}q).$ Thus $N$ must be a root of the derivative so ${\frac{d(x^n-1)}{dx}|}_N\equiv n{N}^{n-1}\equiv 0(\mathrm{mod}q).$ But $q\nmid N$ and therefore $q\nmid n.$ This is a contradiction so $m=n$. The order of $N(\mathrm{mod}q),$ which is $n$, must divide $q-1$. Thus $q\equiv 1(\mathrm{mod}n).$

See also

• Cyclotomic field
• Aurifeuillean factorization
• Root of unity

Further reading

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.

• Gauss, Carl Friedrich (1801), Disquisitiones Arithmeticae (in Latina), Leipzig: Gerh. Fleischer
• Gauss, Carl Friedrich (1807) [1801], Recherches Arithmétiques (in français), translated by Poullet-Delisle, A.-C.-M., Paris: Courcier
• Gauss, Carl Friedrich (1889) [1801], Carl Friedrich Gauss' Untersuchungen über höhere Arithmetik (in Deutsch), translated by Maser, H., Berlin: Springer; Reprinted 1965, New York: Chelsea, ISBN 0-8284-0191-8
• Gauss, Carl Friedrich (1966) [1801], Disquisitiones Arithmeticae, translated by Clarke, Arthur A., New Haven: Yale, doi:10.12987/9780300194258, ISBN 978-0-300-09473-2; Corrected ed. 1986, New York: Springer, doi:10.1007/978-1-4939-7560-0, ISBN 978-0-387-96254-2
• Lemmermeyer, Franz (2000), Reciprocity Laws: from Euler to Eisenstein, Berlin: Springer, doi:10.1007/978-3-662-12893-0, ISBN 978-3-642-08628-1

External links

• Weisstein, Eric W., "Cyclotomic polynomial", MathWorld
• "Cyclotomic polynomials", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• 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)