Editing Cyclotomic polynomial (section)

===Fundamental tools===

The cyclotomic polynomials are monic polynomials with integer coefficients that are [[irreducible polynomial|irreducible]] over the field of the rational numbers. Except for ''n'' equal to 1 or 2, they are [[Palindromic polynomial|palindrome]]s of even degree.

The degree of <math>\Phi_n</math>, or in other words the number of ''n''th primitive roots of unity, is <math>\varphi (n)</math>, where <math>\varphi</math> is [[Euler's totient function]].

The fact that <math>\Phi_n</math> is an irreducible polynomial of degree <math>\varphi (n)</math> in the [[ring (mathematics)|ring]] <math>\Z[x]</math> is a nontrivial result due to [[Carl Friedrich Gauss|Gauss]].<ref>{{Lang Algebra}}</ref> 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#Cyclotomic polynomials|Eisenstein's criterion]].

A fundamental relation involving cyclotomic polynomials is 

:<math>\begin{align} 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).\end{align}</math>

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#Multiplicative notation|Möbius inversion formula]] allows <math>\Phi_n(x)</math> to be expressed as an explicit rational fraction:

:<math>\Phi_n(x)=\prod_{d\mid n}(x^d-1)^{\mu \left (\frac{n}{d} \right )}, </math>

where <math>\mu</math> is the [[Möbius function]].

This provides a [[Recursive definition|recursive formula]] for the cyclotomic polynomial <math>\Phi_{n}(x)</math>, which may be computed by [[Polynomial long division|dividing]] <math>x^n-1</math> by the cyclotomic polynomials <math>\Phi_d(x)</math> for the proper divisors ''d'' dividing ''n'', starting from <math>\Phi_{1}(x)=x-1</math>:

:<math>\Phi_n(x)=\frac{x^{n}-1}{\prod_{\stackrel{d|n}{{}_{d<n}}}\Phi_{d}(x)}.</math>

This gives an algorithm for computing any <math>\Phi_n(x)</math>, provided [[integer factorization]] and [[Euclidean division of polynomials|division of polynomials]] are available. Many [[computer algebra systems]], such as [[SageMath]], [[Maple (software)|Maple]], [[Mathematica]], and [[PARI/GP]], have a built-in function to compute the cyclotomic polynomials.