# .

In algebra, the nth cyclotomic polynomial, for any positive integer n, is the monic polynomial:

$$\Phi_n(X) = \prod_\omega (X-\omega)\,$$

where the product is over all nth primitive roots of unity ω in an algebraically closed field, i.e. all its elements ω of order n.

Properties

Let us set $$\Phi_{1}(X)=X-1.$$
Fundamental tools

The degree of \Phi_n, or in other words the number of factors in its definition above, is φ(n), where φ is Euler's totient function.

The coefficients of $$\Phi_n$$ are integers, in other words, $$\Phi_n(X)\in\mathbb{Z}[X]$$. This can be seen elementarily by expressing the coefficients of the polynomials as elementary symmetric polynomials of the primitive roots, and to proceed inductively by using the relation:

$$\sum_{k = 1}^n e ^{\frac{2ik\pi}{n}} = 0.$$

The fundamental relation involving cyclotomic polynomials is

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

which amounts to the fact that each polynomial involved with n-th root of unity is product, for some divisor d of n, a primitive d-th root of unity. This depends on formula :
\ $$sum_{d\mid n}\varphi(d)=n,$$

where φ is Euler's totient function.

The Möbius inversion formula yields the equivalent formulation:

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

where μ is the Möbius function.

From this fact, or alternatively, directly from the fact that the roots of a cyclotomic polynomial are the primitive roots of unity, we can calculate \Phi_{n}(X) by dividing X^n-1 by the cyclotomic polynomials of the proper divisors of n:

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

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

The polynomial \Phi_n(X) is irreducible in the ring $$\mathbb{Z}[X]$$. This result, due to Gauss, is not trivial.[1] The case of prime n is easier to prove than the general case, thanks to Eisenstein's criterion.
Cyclotomic polynomials and arithmetic of integers

If n is a prime power, say pm where p is prime, then

$$\Phi_n(X) = \sum_{0\le k\le p-1}X^{kp^{m-1}}.$$

In particular ( for m = 1)

$$\Phi_p(X) = 1+X+X^2+\cdots+X^{p-1}.$$

Any cyclotomic polynomial $$\Phi_n(X)$$ has a simple expression in terms of $$\Phi_q(X)$$ where q is the radical of n:

$$\Phi_n(X) = \Phi_q(X^{n/q})$$

If n > 1 is odd, then $$\Phi_{2n}(X) = \Phi_n(-X).$$
Integers appearing as coefficients

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}.[2]

The first cyclotomic polynomial with 3 different odd prime factors is $$\Phi_{105}(X)$$and it has a coefficient −2 (see its expression below). The converse isn't true: $$\Phi_{651}(X) = \Phi_{3\times 7\times 31}(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.
Examples of cyclotomic polynomials

$$~\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_{12}(X) = X^4 - X^2 + 1$$

$$~\Phi_{15}(X) = X^8 - X^7 + X^5 - X^4 + X^3 - X + 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}

Applications

Using the fact that $$\Phi_n$$ is irreducible, one can prove the infinitude of primes congruent to 1 modulo n,[3] which is a special case of Dirichlet's theorem on arithmetic progressions.

Cyclotomic field

References

^ Lang, Serge (2002), Algebra, Graduate Texts in Mathematics, 211 (Revised third ed.), New York: Springer-Verlag, ISBN 978-0-387-95385-4, MR1878556
^ Isaacs, Martin (2009). Algebra: A Graduate Course. AMS Bookstore. p. 310. ISBN 978-0-8218-4799-2.
^ S. Shirali. Number Theory. Orient Blackswan, 2004. p. 67. ISBN 81-7371-454-1