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 (and i is the imaginary unit). 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 d th primitive root of unity for some d that divides n.^[1]

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:^[2]

${\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}\\&\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{aligned}}}$

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]

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

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}}$.^[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.

This section does not cite any sources. (April 2014)

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 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 ${\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 divide ${\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 OEIS: A085398 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 OEIS: A206864 for the list of the smallest primes of the form ${\displaystyle \Phi _{n}(b)}$ with n > 2 and b > 1, and, more generally, OEIS: A206942, for the smallest positive integers of this form.

More information ...

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^{2p^{k}}+\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 divide 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).}$

Close

Using ${\displaystyle \Phi _{n}}$, 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.

More information Suppose ...

Proof

Suppose ${\displaystyle p_{1},p_{2},\ldots ,p_{k}}$ is 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<n}$. Since ${\displaystyle \prod _{d\mid m}\Phi _{d}(N)=N^{m}-1\equiv 0{\pmod {q}}}$ we have ${\displaystyle \Phi _{d}(N)\equiv 0{\pmod {q}},}$ for some ${\displaystyle d<n}$. 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}}.}$

Close

• Cyclotomic field
• Aurifeuillean factorization
• Root of unity