# 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 ${\displaystyle x^{n}-1}$ and is not a divisor of ${\displaystyle x^{k}-1}$ for any k < n. Its roots are all nth primitive roots of unity ${\displaystyle e^{2i\pi {\frac {k}{n}}}}$, where k runs over the positive integers not greater than n and coprime to n. In other words, the nth cyclotomic polynomial is equal to

${\displaystyle \Phi _{n}(x)=\prod _{\stackrel {1\leq k\leq n}{\gcd(k,n)=1}}\left(x-e^{2i\pi {\frac {k}{n}}}\right).}$

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

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

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

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

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

If n = 2p where p is an odd prime number, then

${\displaystyle \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:[1]

{\displaystyle {\begin{aligned}\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}+x^{11}\\&\qquad \quad +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}+x^{14}\\&\qquad \quad +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{aligned}}}

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:

{\displaystyle {\begin{aligned}\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}\\&\qquad \quad -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{aligned}}}

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

The fact that ${\displaystyle \Phi _{n}}$  is an irreducible polynomial of degree ${\displaystyle \varphi (n)}$  in the ring ${\displaystyle \mathbb {Z} [x]}$  is a nontrivial result due to Gauss.[2] 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

${\displaystyle 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).}$

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 ${\displaystyle \Phi _{n}(x)}$  as an explicit rational fraction:

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

where ${\displaystyle \mu }$  is the Möbius function.

The Fourier transform of functions of the greatest common divisor together with the Möbius inversion formula gives:[3]

${\displaystyle \Phi _{n}(x)=\prod _{k=1}^{n}\left(x^{\gcd(k,n)}-1\right)^{\cos \left({\frac {2\pi k}{n}}\right)}.}$

The cyclotomic polynomial ${\displaystyle \Phi _{n}(x)}$  may be computed by (exactly) dividing ${\displaystyle x^{n}-1}$  by the cyclotomic polynomials of the proper divisors of n previously computed recursively by the same method:

${\displaystyle \Phi _{n}(x)={\frac {x^{n}-1}{\prod _{\stackrel {d|n}{{}_{d

(Recall that ${\displaystyle \Phi _{1}(x)=x-1}$ .)

This formula allows computation of ${\displaystyle \Phi _{n}(x)}$  on a computer for any n, as soon as integer factorization and division of polynomials are available. Many computer algebra systems have a built in function to compute the cyclotomic polynomials. For example, this function is called by typing cyclotomic_polynomial(n,x) in SageMath, numtheory[cyclotomic](n,x); in Maple, and Cyclotomic[n,x] in Mathematica.

### Easy cases for computation

As noted above, if n is a prime number, then

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

If n is an odd integer greater than one, then

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

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

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

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

${\displaystyle \Phi _{n}(x)=\Phi _{p}(x^{p^{m-1}})=\sum _{i=0}^{p-1}x^{ip^{m-1}}.}$

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

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

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

${\displaystyle \Phi _{n}(x)=\Phi _{q}(x^{n/q}).}$

This allows to give formulas 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:

${\displaystyle \Phi _{2^{h}}(x)=x^{2^{h-1}}+1}$
${\displaystyle \Phi _{p^{k}}(x)=\sum _{i=0}^{p-1}x^{ip^{k-1}}}$
${\displaystyle \Phi _{2^{h}p^{k}}(x)=\sum _{i=0}^{p-1}(-1)^{i}x^{i2^{h-1}p^{k-1}}}$

For the other values of n, the computation of the nth cyclotomic polynomial is similarly reduced to that of ${\displaystyle \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,[5]

${\displaystyle \Phi _{np}(x)=\Phi _{n}(x^{p})/\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.

If n has at most two distinct odd prime factors, then Migotti showed that the coefficients of ${\displaystyle \Phi _{n}}$  are all in the set {1, −1, 0}.[6]

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

### Gauss's formula

Let n be odd, square-free, and greater than 3. Then:[8][9]

${\displaystyle 4\Phi _{n}(z)=A_{n}^{2}(z)-(-1)^{\frac {n-1}{2}}nz^{2}B_{n}^{2}(z)}$

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

{\displaystyle {\begin{aligned}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{aligned}}}

### Lucas's formula

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

${\displaystyle \Phi _{n}(z)=U_{n}^{2}(z)-(-1)^{\frac {n-1}{2}}nzV_{n}^{2}(z)}$

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

${\displaystyle \Phi _{n}\left((-1)^{\frac {n-1}{2}}z\right)=C_{n}^{2}(z)-nzD_{n}^{2}(z).}$

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

${\displaystyle \Phi _{\frac {n}{2}}\left(-z^{2}\right)=\Phi _{2n}(z)=C_{n}^{2}(z)-nzD_{n}^{2}(z)}$

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:

{\displaystyle {\begin{aligned}\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{aligned}}}

## Cyclotomic polynomials over a finite field and over 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 ${\displaystyle \Phi _{n}}$  factorizes into ${\displaystyle {\frac {\varphi (n)}{d}}}$  irreducible polynomials of degree d, where ${\displaystyle \varphi (n)}$  is Euler's totient function, and d is the multiplicative order of p modulo n. In particular, ${\displaystyle \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 ${\displaystyle \varphi (n),}$  the degree of ${\displaystyle \Phi _{n}}$ .[citation needed]

These results are also true over the p-adic integers, since Hensel's lemma allows lifting a factorization over the field with p of elements to a factorization over the p-adic integers.

## Polynomial values

If x takes any real value, then ${\displaystyle \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 ${\displaystyle \Phi _{1}(x)=x-1}$  and ${\displaystyle \Phi _{2}(x)=x+1}$ ).

For n ≥ 2, one has

${\displaystyle \Phi _{n}(0)=1,}$
${\displaystyle \Phi _{n}(1)=1}$  if n is not a prime power,
${\displaystyle \Phi _{n}(1)=p}$  if ${\displaystyle n=p^{k}}$  is a prime power with k ≥ 1.

The values that a cyclotomic polynomial ${\displaystyle \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 ${\displaystyle x^{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 ${\displaystyle \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)

${\displaystyle \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 ${\displaystyle \Phi _{n}(b),}$  then either n is a divisor of p − 1 or p is a divisor of n. In the latter case ${\displaystyle p^{2}}$  does not divides ${\displaystyle \Phi _{n}(b).}$

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

{\displaystyle {\begin{aligned}\Phi _{1}(2)&=1\\\Phi _{2}\left(2^{k}-1\right)&=2^{k}&&k>0\\\Phi _{6}(2)&=3\end{aligned}}}

It follows from above factorization that the odd prime factors of

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

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

## Applications

Using ${\displaystyle \Phi _{n}}$ , one can give an elementary proof for the infinitude of primes congruent to 1 modulo n,[11] which is a special case of Dirichlet's theorem on arithmetic progressions.

Proof

Suppose ${\displaystyle p_{1},p_{2},\ldots ,p_{k}}$  are a finite list of primes congruent to ${\displaystyle 1}$  modulo ${\displaystyle n.}$  Let ${\displaystyle N=np_{1}p_{2}\cdots p_{k}}$  and consider ${\displaystyle \Phi _{n}(N)}$ . Let ${\displaystyle q}$  be a prime factor of ${\displaystyle \Phi _{n}(N)}$  (to see that ${\displaystyle \Phi _{n}(N)\neq \pm 1}$  decompose it into linear factors and note that 1 is the closest root of unity to ${\displaystyle N}$ ). Since ${\displaystyle \Phi _{n}(x)\equiv \pm 1{\pmod {x}},}$  we know that ${\displaystyle q}$  is a new prime not in the list. We will show that ${\displaystyle q\equiv 1{\pmod {n}}.}$

Let ${\displaystyle m}$  be the order of ${\displaystyle N}$  modulo ${\displaystyle q.}$  Since ${\displaystyle \Phi _{n}(N)\mid N^{n}-1}$  we have ${\displaystyle N^{n}-1\equiv 0{\pmod {q}}}$ . Thus ${\displaystyle m\mid n}$ . We will show that ${\displaystyle m=n}$ .

Assume for contradiction that ${\displaystyle m . Since

${\displaystyle N^{m}-1\equiv \prod _{d\mid m}\Phi _{d}(N)\equiv 0{\pmod {q}}}$

we have

${\displaystyle \Phi _{d}(N)\equiv 0{\pmod {q}},}$

for some ${\displaystyle d . Then ${\displaystyle N}$  is a double root of

${\displaystyle \prod _{d\mid n}\Phi _{d}(x)\equiv x^{n}-1{\pmod {q}}.}$

Thus ${\displaystyle N}$  must be a root of the derivative so

${\displaystyle \left.{\frac {d(x^{n}-1)}{dx}}\right|_{N}\equiv nN^{n-1}\equiv 0{\pmod {q}}.}$

But ${\displaystyle q\nmid N}$  and therefore ${\displaystyle q\nmid n.}$  This is a contradiction so ${\displaystyle m=n}$ . The order of ${\displaystyle N{\pmod {q}},}$  which is ${\displaystyle n}$ , must divide ${\displaystyle q-1}$ . Thus ${\displaystyle q\equiv 1{\pmod {n}}.}$

## Notes

1. ^ Sloane, N. J. A. (ed.). "Sequence A013595". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
2. ^ Lang, Serge (2002), Algebra, Graduate Texts in Mathematics, 211 (Revised third ed.), New York: Springer-Verlag, ISBN 978-0-387-95385-4, MR 1878556
3. ^ Schramm, Wolfgang (2015). "Eine alternative Produktdarstellung für die Kreisteilungspolynome". Elemente der Mathematik. Swiss Mathematical Society. 70 (4): 137–143. Archived from the original on 2015-12-22. Retrieved 2015-10-10.
4. ^ Cox, David A. (2012), "Exercise 12", Galois Theory (2nd ed.), John Wiley & Sons, p. 237, doi:10.1002/9781118218457, ISBN 978-1-118-07205-9.
5. ^ Weisstein, Eric W. "Cyclotomic Polynomial". Retrieved 12 March 2014.
6. ^ Isaacs, Martin (2009). Algebra: A Graduate Course. AMS Bookstore. p. 310. ISBN 978-0-8218-4799-2.
7. ^ Meier (2008)
8. ^ Gauss, DA, Articles 356-357
9. ^ Riesel, pp. 315-316, p. 436
10. ^ Riesel, pp. 309-315, p. 443
11. ^ S. Shirali. Number Theory. Orient Blackswan, 2004. p. 67. ISBN 81-7371-454-1

## 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.

• Gauss, Carl Friedrich (1986) [1801]. Disquisitiones Arithmeticae. Translated into English by Clarke, Arthur A. (2nd corr. ed.). New York: Springer. ISBN 0387962549.
• Gauss, Carl Friedrich (1965) [1801]. 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. Berlin: Springer. doi:10.1007/978-3-662-12893-0. ISBN 978-3-642-08628-1.
• Maier, Helmut (2008), "Anatomy of integers and cyclotomic polynomials", in De Koninck, Jean-Marie; Granville, Andrew; Luca, Florian (eds.), Anatomy of integers. Based on the CRM workshop, Montreal, Canada, March 13-17, 2006, CRM Proceedings and Lecture Notes, 46, Providence, RI: American Mathematical Society, pp. 89–95, ISBN 978-0-8218-4406-9, Zbl 1186.11010
• Riesel, Hans (1994). Prime Numbers and Computer Methods for Factorization (2nd ed.). Boston: Birkhäuser. ISBN 0-8176-3743-5.