# Cyclotomic polynomials

circular polynomials

The polynomials $\Phi _ {1} , \Phi _ {2}, \dots$ that satisfy the relation

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

where the product is taken over all positive divisors $d$ of the number $n$, including $n$ itself. Over the field of complex numbers one has

$$\Phi _ {n} ( x) = \ \prod _ \zeta ( x - \zeta ),$$

where $\zeta$ ranges over the primitive $n$-th roots of unity (cf. Primitive root). The degree of $\Phi _ {n} ( x)$ is the number of integers $k$ among $1, \dots, n$ that are relatively prime with $n$. The polynomials $\Phi _ {n} ( x)$ can be computed recursively by dividing the polynomial $x ^ {n} - 1$ by the product of all $\Phi _ {d} ( x)$, $d < n$, $d \mid n$. The coefficients lie in the prime field $\mathbf Q$; in case of characteristic zero, they are integers. Thus,

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

If, moreover, $n= p$ is prime, then

$$\Phi _ {p} ( x) = \frac{x ^ {p} - 1 }{x - 1 } = x ^ {p - 1 } + \dots + x + 1 .$$

The polynomial $\Phi _ {n} ( x)$ can be explicitly expressed using the Möbius function $\mu$:

$$\Phi _ {n} ( x) = \prod _ {d \mid n } ( x ^ {d} - 1 ) ^ {\mu ( n / d ) } .$$

For example,

$$\Phi _ {12} ( x) =$$

$$= \ ( x ^ {12} - 1) ( x ^ {6} - 1) ^ {-1} ( x ^ {4} - 1) ^ {-1} ( x ^ {3} - 1) ^ {0} ( x ^ {2} - 1) ( x - 1) ^ {0 } =$$

$$= \ \frac{x ^ {6} + 1 }{x ^ {2} + 1 } = x ^ {4} - x ^ {2} + 1 .$$

All the polynomials $\Phi _ {n} ( x)$ are irreducible over the field of rational numbers, but they may be reducible over finite prime fields. Thus, the relation

$$\Phi _ {12} ( x) = x ^ {4} - x ^ {2} + 1 = ( x ^ {2} + 5x + 1 ) ( x ^ {2} - 5x + 1 )$$

is valid over the field of residues modulo 11.

The equation $\Phi _ {n} ( x) = 0$, which gives all primitive $n$-th roots of unity, is known as the equation of division of the circle. The solution of this equation in trigonometric form is

$$r _ {k} = \cos \frac{2 k \pi }{n} + i \sin \frac{2 k \pi }{n} = \ e ^ {2 k \pi i /n } ,$$

where the fraction $k / n$ is irreducible, i.e. $k$ and $n$ are relatively prime. The solution of the equation of division of the circle by radicals is closely connected with the problem of constructing a regular $n$-gon, or with the equivalent problem of subdividing the circle into $n$ equal parts; the latter problem can be solved using a straightedge and a pair of compasses if and only if the equation $\Phi _ {n} ( x) = 0$ is solvable in quadratic radicals. It was shown by C.F. Gauss in 1801 that this condition is satisfied if and only if

$$n = 2 ^ {m} p _ {1} \cdots p _ {s} ,$$

where $m$ is a non-negative integer and $p _ {1}, \dots, p _ {s}$ are pairwise different prime numbers of the form $2 ^ {2 ^ {k} } + 1$, where $k$ is a non-negative integer.

#### References

 [1] B.L. van der Waerden, "Algebra" , 1–2 , Springer (1967–1971) (Translated from German) [2] A.K. Sushkevich, "Foundations of higher algebra" , Moscow-Leningrad (1941) (In Russian)

The degree of $\Phi _ {n} ( x)$ is equal to $\phi ( n)$, the value (at $n$) of the Euler $\phi$-function (cf. Euler function).
Prime numbers of the form $2 ^ {2 ^ {k} } + 1$ with $k$ a non-negative integer are called Fermat primes, these numbers are related to a problem of Fermat: When is the number $F _ {k} = 2 ^ {2 ^ {k} } + 1$, with $k$ as before, prime? The only small Fermat primes are $F _ {0}$, $F _ {1}$, $F _ {2}$, $F _ {3}$, $F _ {4}$ (cf. [a1], pp. 183-185).