# Cyclotomic polynomial

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

$\Phi_n(x) = \prod_\stackrel{1\le k\le 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, which 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).

Another important equation, linking the cyclotomic polynomials and primitive roots of unity, is the following one.

$x^n - 1 =\prod_{1\leq k\leq n} \left(x- e^{2 \pi \cdot \mathrm i k / n} \right)= \prod_{d \mid n} \prod_{1 \leq k \leq n\atop \operatorname{gcd}(k, n) = d} \left(x- e^{2 \pi \cdot \mathrm i k / n} \right) =\prod_{d \mid n} \Phi_{n/d}(x) = \prod_{d\mid n} \Phi_d(x)$

## Examples

If n is a prime number then

$~\Phi_n(x) = 1+x+x^2+\cdots+x^{n-1}=\sum_{i=0}^{n-1} x^i.$

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

$~\Phi_{2p}(x) = 1-x+x^2-\cdots+x^{p-1}=\sum_{i=0}^{p-1} (-x)^i.$

For n up to 30, the cyclotomic polynomials are:[1]

$~\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$
\begin{align} \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 \end{align}
$~\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$
\begin{align} \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 \end{align}
$~\Phi_{30}(x) = x^8 + x^7 - x^5 - x^4 - x^3 + x + 1$

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 and this polynomial is the first one that has a coefficient other than 1, 0, or -1:

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

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

The fact that $\Phi_n$ is an irreducible polynomial of degree $\varphi (n)$ in the ring $\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

$\prod_{d\mid n}\Phi_d(x) = x^n - 1,$

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 $\Phi_n(x)$ as an explicit rational fraction:

$\Phi_n(x)=\prod_{d\mid n}(x^d-1)^{\mu(n/d)},$

where $\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]

$~\Phi_n(x)=\prod\limits_{k=1}^n{(x^{\operatorname{gcd}(k,n)}-1)^{\cos (\frac{2\pi k}{n})}}$

The cyclotomic polynomial $\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:

$\Phi_n(x)=\frac{x^{n}-1}{\prod_{\stackrel{d|n}{{}_{d

(Recall that $\Phi_{1}(x)=x-1$.)

This formula allows to compute $\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 Sage, numtheory[cyclotomic](n,x); in Maple, and Cyclotomic[n,x] in Mathematica.

### Easy cases for the computation

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

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

$\Phi_{2n}(x) = \Phi_n(-x).$

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

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

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

$\Phi_n(x) = \Phi_{pr}(x^{p^{m-1}}).$

These formulas may be applied repeatedly to get a simple expression for any cyclotomic polynomial $\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]

$\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:

$\Phi_{2^h}(x) = x^{2^{h-1}}+1$
$\Phi_{p^k}(x) = \sum_{i=0}^{p-1}x^{ip^{k-1}}$
$\Phi_{2^hp^k}(x) = \sum_{i=0}^{p-1}(-1)^ix^{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 $\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]

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

The first cyclotomic polynomial for a product of 3 different odd prime factors is $\Phi_{105}(x);$ it has a coefficient −2 (see its expression above). The converse isn't true: $\Phi_{231}(x)$ = $\Phi_{3\times 7\times 11}(x)$ only has coefficients in {1, −1, 0}.

If n is a product of more odd different prime factors, the coefficients may increase to very high values. E.g., $\Phi_{15015}(x)$ = $\Phi_{3\times 5\times 7\times 11\times 13}(x)$ has coefficients running from −22 to 22, $\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]

$4\Phi_n(z) = A_n^2(z) - (-1)^{\frac{n-1}{2}}nz^2B_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

\begin{align} 4\Phi_5(z) &=4(z^4+z^3+z^2+z+1)\\ &= (2z^2+z+2)^2 - 5z^2 \end{align}
\begin{align} 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 \end{align}
\begin{align} 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}

### Lucas's formula

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

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

$\Phi_n((-1)^{\frac{n-1}{2}}z) = C_n^2(z) - nzD_n^2(z).$

If n is even, square-free and greater than 2 (this forces n to be ≡ 2 (mod 4)),

$\Phi_{n/2}(-z^2) = 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:

\begin{align} \Phi_3(-z) &=z^2-z+1 \\ &= (z+1)^2 - 3z \end{align}
\begin{align} \Phi_5(z) &=z^4+z^3+z^2+z+1 \\ &= (z^2+3z+1)^2 - 5z(z+1)^2 \end{align}
\begin{align} \Phi_3(-z^2) &=z^4-z^2+1 \\ &= (z^2+3z+1)^2 - 6z(z+1)^2 \end{align}

## Cyclotomic polynomials over Zp

For any prime number p which does not divide n, the cyclotomic polynomial $\Phi_n$ is irreducible over Zp if and only if p is a primitive root modulo n. That is, the p does not divide n, and its multiplicative order modulo n is $\varphi(n)$ (which is also the degree of $\Phi_n$).

## Prime Cyclotomic numbers

The prime numbers of the form $\Phi_n(b)$ (with n, b integers, n > 2, b > 1) are listed in , or all primes in .

The list is about the smallest integer b > 1 which $\Phi_n(b)$ is a prime (see ), it is conjectured that such b exists for all positive integer n (See Bunyakovsky conjecture). (For that to allow b = 1, see . In fact, b = 1 if and only if n is a prime or a prime power, so you can see this sequence for all positive integer n which is neither a prime nor a prime power. For n is a prime, see ).

The list is about all n ≤ 300 (The b-file of A117544 lists all n ≤ 1000, but it lists 1 if and only if n is a prime or prime power)

 n +1 +2 +3 +4 +5 +6 +7 +8 +9 +10 +11 +12 +13 +14 +15 +16 +17 +18 +19 +20 0+ 3 2 2 2 2 2 2 2 2 2 5 2 2 2 2 2 2 6 2 4 20+ 3 2 10 2 22 2 2 4 6 2 2 2 2 2 14 3 61 2 10 2 40+ 14 2 15 25 11 2 5 5 2 6 30 11 24 7 7 2 5 7 19 3 60+ 2 2 3 30 2 9 46 85 2 3 3 3 11 16 59 7 2 2 22 2 80+ 21 61 41 7 2 2 8 5 2 2 11 4 2 6 44 4 12 2 63 20 100+ 22 13 3 4 7 10 2 3 12 5 12 40 86 14 268 5 24 6 148 2 120+ 43 2 12 6 127 2 2 102 2 3 7 3 2 5 33 56 13 8 11 4 140+ 5 46 3 6 2 18 13 4 5 2 29 9 14 3 62 4 56 2 189 20 160+ 3 93 30 12 2 49 44 18 24 2 22 14 60 2 63 17 47 16 304 35 180+ 5 9 156 2 43 24 41 96 8 40 74 2 118 70 2 10 33 5 156 26 200+ 41 2 294 16 11 5 127 2 103 25 46 41 206 6 167 88 39 12 105 15 220+ 15 14 183 7 77 92 72 15 606 13 66 9 602 2 17 3 46 52 223 28 240+ 115 19 209 61 67 11 15 5 27 25 37 23 69 2 3 120 52 17 69 28 260+ 2 48 104 9 14 20 26 25 41 20 6 55 41 89 17 3 338 30 3 2 280+ 217 34 13 69 112 14 3 5 315 65 15 196 136 22 44 2 56 16 219 4

For all positive integers n ≤ 1000, the largest three bs are 2706, 2061, and 2042, when n is 545, 601, and 943, and there are 17 values of n ≤ 1000 such that b > 1000.

In fact, if p is a prime, then $\Phi_p(b)$ is $\frac{b^p-1}{b-1}$ and a repunit number in base b, (111111...111111)b, so the following is a list of the smallest b > 1 which $\Phi_p(b)$ is a prime. (see )

The list is about the first 100 primes p. (The b-file of A066180 lists the first 200 primes p, up to 1223)

 p 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 min b 2 2 2 2 5 2 2 2 10 6 2 61 14 15 5 24 19 2 46 3 p 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 min b 11 22 41 2 12 22 3 2 12 86 2 7 13 11 5 29 56 30 44 60 p 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 min b 304 5 74 118 33 156 46 183 72 606 602 223 115 37 52 104 41 6 338 217 p 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 min b 13 136 220 162 35 10 218 19 26 39 12 22 67 120 195 48 54 463 38 41 p 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 min b 17 808 404 46 76 793 38 28 215 37 236 59 15 514 260 498 6 2 95 3

## Applications

Using $\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.

## Notes

1. ^ (sequence A013595 in OEIS)
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. 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, 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.