Editing Root of unity (section)

==Cyclotomic polynomials==<!-- This section is linked from [[Cyclotomic polynomial]] -->
{{Main|Cyclotomic polynomial}}

The [[zero of a function|zeros]] of the polynomial
:<math>p(z) = z^n - 1</math>
are precisely the {{mvar|n}}th roots of unity, each with [[multiplicity of a root|multiplicity]] 1. The {{mvar|n}}th ''[[cyclotomic polynomial]]'' is defined by the fact that its zeros are precisely the ''primitive'' {{mvar|n}}th roots of unity, each with multiplicity 1.
: <math>\Phi_n(z) = \prod_{k=1}^{\varphi(n)}(z-z_k)</math>
where {{math|''z''<sub>1</sub>, ''z''<sub>2</sub>, ''z''<sub>3</sub>, …, ''z''<sub>φ(''n'')</sub>}} are the primitive {{mvar|n}}th roots of unity, and {{math|φ(''n'')}} is [[Euler's totient function]]. The polynomial {{math|Φ<sub>''n''</sub>(''z'')}} has integer coefficients and is an [[irreducible polynomial]] over the rational numbers (that is, it cannot be written as the product of two positive-degree polynomials with rational coefficients).<ref name="riesel" /> The case of prime {{mvar|n}}, which is easier than the general assertion, follows by applying [[Eisenstein's criterion]] to the polynomial

:<math>\frac{(z+1)^n - 1}{(z+1) - 1},</math>

and expanding via the [[binomial theorem]].

Every {{mvar|n}}th root of unity is a primitive {{mvar|d}}th root of unity for exactly one positive [[divisor]] {{mvar|d}} of {{mvar|n}}. This implies that<ref name="riesel" />

:<math>z^n - 1 = \prod_{d \,|\, n} \Phi_d(z).</math>

This formula represents the [[factorization of polynomials|factorization]] of the polynomial {{math|''z''<sup>''n''</sup> − 1}} into irreducible factors:

:<math>\begin{align}
z^1 -1 &= z-1 \\
z^2 -1 &= (z-1)(z+1) \\
z^3 -1 &= (z-1) (z^2 + z + 1) \\
z^4 -1 &= (z-1)(z+1) (z^2+1) \\
z^5 -1 &= (z-1) (z^4 + z^3 +z^2 + z + 1) \\
z^6 -1 &= (z-1)(z+1) (z^2 + z + 1) (z^2 - z + 1)\\
z^7 -1 &= (z-1) (z^6+ z^5 + z^4 + z^3 + z^2 + z + 1) \\
z^8 -1 &= (z-1)(z+1) (z^2+1) (z^4+1)  \\
\end{align}</math>

Applying [[Möbius inversion]] to the formula gives

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

where {{math|''μ''}} is the [[Möbius function]]. So the first few cyclotomic polynomials are

:{{math|1=Φ<sub>1</sub>(''z'') = ''z'' − 1}}
:{{math|1=Φ<sub>2</sub>(''z'') = (''z''<sup>2</sup> − 1)⋅(''z'' − 1)<sup>−1</sup> = ''z'' + 1}}
:{{math|1=Φ<sub>3</sub>(''z'') = (''z''<sup>3</sup> − 1)⋅(''z'' − 1)<sup>−1</sup> = ''z''<sup>2</sup> + ''z'' + 1}}
:{{math|1=Φ<sub>4</sub>(''z'') = (''z''<sup>4</sup> − 1)⋅(''z''<sup>2</sup> − 1)<sup>−1</sup> = ''z''<sup>2</sup> + 1}}
:{{math|1=Φ<sub>5</sub>(''z'') = (''z''<sup>5</sup> − 1)⋅(''z'' − 1)<sup>−1</sup> = ''z''<sup>4</sup> + ''z''<sup>3</sup> + ''z''<sup>2</sup> + ''z'' + 1}}
:{{math|1=Φ<sub>6</sub>(''z'') = (''z''<sup>6</sup> − 1)⋅(''z''<sup>3</sup> − 1)<sup>−1</sup>⋅(''z''<sup>2</sup> − 1)<sup>−1</sup>⋅(''z'' − 1)  = ''z''<sup>2</sup> − ''z'' + 1}}
:{{math|1=Φ<sub>7</sub>(''z'') = (''z''<sup>7</sup> − 1)⋅(''z'' − 1)<sup>−1</sup>  = ''z''<sup>6</sup> + ''z''<sup>5</sup> + ''z''<sup>4</sup> + ''z''<sup>3</sup> + ''z''<sup>2</sup>  +''z'' + 1}}
:{{math|1=Φ<sub>8</sub>(''z'') = (''z''<sup>8</sup> − 1)⋅(''z''<sup>4</sup> − 1)<sup>−1</sup> = ''z''<sup>4</sup> + 1}}

If {{mvar|p}} is a [[prime number]], then all the {{mvar|p}}th roots of unity except 1 are primitive {{mvar|p}}th roots. Therefore,<ref name="morandi" />
<math display="block">\Phi_p(z) = \frac{z^p - 1}{z - 1} = \sum_{k = 0}^{p - 1} z^k.</math>
Substituting any positive integer ≥&thinsp;2 for {{mvar|z}}, this sum becomes a [[radix|base {{mvar|z}}]] [[repunit]]. Thus a necessary (but not sufficient) condition for a repunit to be prime is that its length be prime.

Note that, contrary to first appearances, ''not'' all coefficients of all cyclotomic polynomials are 0, 1, or −1.  The first exception is {{math|Φ<sub>{{num|105}}</sub>}}. It is not a surprise it takes this long to get an example, because the behavior of the coefficients depends not so much on {{mvar|n}} as on how many [[parity (mathematics)|odd]] prime factors appear in {{mvar|n}}.  More precisely, it can be shown that if {{mvar|n}} has 1 or 2 odd prime factors (for example, {{math|1=''n''&nbsp;=&thinsp;150}}) then the {{mvar|n}}th cyclotomic polynomial only has coefficients 0, 1 or −1.  Thus the first conceivable {{mvar|n}} for which there could be a coefficient besides 0, 1, or −1 is a product of the three smallest odd primes, and that is {{math|1=3&thinsp;⋅&thinsp;5&thinsp;⋅&thinsp;7 = 105}}.  This by itself doesn't prove the 105th polynomial has another coefficient, but does show it is the first one which even has a chance of working (and then a computation of the coefficients shows it does).  A theorem of Schur says that there are cyclotomic polynomials with coefficients arbitrarily large in [[absolute value]]. In particular, if <math>n = p_1 p_2 \cdots p_t,</math> where <math>p_1 < p_2 < \cdots < p_t</math> are odd primes, <math>p_1 +p_2>p_t,</math> and ''t'' is odd, then {{math|1 − ''t''}} occurs as a coefficient in the {{mvar|n}}th cyclotomic polynomial.<ref name="lehmer">{{cite journal
|last = Lehmer|first = Emma|author-link = Emma Lehmer
|title = On the magnitude of the coefficients of the cyclotomic polynomial
|journal = Bulletin of the American Mathematical Society
|year = 1936
|volume = 42
|issue = 6
|pages = 389–392| doi=10.1090/S0002-9904-1936-06309-3 |doi-access = free
}}</ref>

Many restrictions are known about the values that cyclotomic polynomials can assume at integer values. For example, if {{mvar|p}} is prime, then {{math|''d''&thinsp;∣&thinsp;Φ<sub>''p''</sub>(''d'')}} if and only if {{math|''d'' ≡ 1 (mod ''p'')}}.

Cyclotomic polynomials are solvable in [[radical expression|radicals]], as roots of unity are themselves radicals. Moreover, there exist more informative radical expressions for {{mvar|n}}th roots of unity with the additional property<ref name="landau">{{Cite journal
|last1 = Landau |first1 = Susan|authorlink1 = Susan Landau
|last2 = Miller |first2 = Gary L.|authorlink2 = Gary Miller (computer scientist)
|title = Solvability by radicals is in polynomial time
|journal = Journal of Computer and System Sciences
|volume = 30
|issue = 2
|pages = 179–208
|year = 1985
|doi = 10.1016/0022-0000(85)90013-3
|doi-access = }}</ref> that every value of the expression obtained by choosing values of the radicals (for example, signs of square roots) is a primitive {{mvar|n}}th root of unity. This was already shown by [[Carl Friedrich Gauss|Gauss]] in 1797.<ref>{{Cite book|last=Gauss|first=Carl F.|author-link=Carl Friedrich Gauss|title=Disquisitiones Arithmeticae|pages=§§359–360|publisher=Yale University Press|year=1965|isbn=0-300-09473-6}}</ref> Efficient [[algorithm]]s exist for calculating such expressions.<ref>{{cite web|last1=Weber|first1=Andreas|last2=Keckeisen|first2=Michael|title=Solving Cyclotomic Polynomials by Radical Expressions|url=http://cg.cs.uni-bonn.de/personal-pages/weber/publications/pdf/WeberA/WeberKeckeisen99a.pdf|access-date=22 June 2007}}</ref>