# Root of unity

In mathematics, a **root of unity**, occasionally called a de Moivre number, is any complex number that gives 1 when raised to some integer power Template:Mvar. Roots of unity are used in many branches of mathematics, and are especially important in number theory, the theory of group characters, and the discrete Fourier transform.

In field theory and ring theory the notion of root of unity also applies to any ring with a multiplicative identity element. Any algebraically closed field has exactly Template:Mvar Template:Mvarth roots of unity, if Template:Mvar is not divisible by the characteristic of the field.

## General definition

An **Template:Mvarth root of unity**, where Template:Mvar is a positive integer (i.e. *n* = 1, 2, 3, …), is a number Template:Mvar satisfying the equation^{[1]}^{[2]}

Traditionally, Template:Mvar is assumed to be a complex number, and subsequent sections of this article will comply with this usage. Generally, *z* ∈ *R* can be considered for any field Template:Mvar, or even for a unital ring. In this general formulation, an Template:Mvarth root of unity is just an element of the group of units of order Template:Mvar. Interesting cases are finite fields and modular arithmetics, for which the article root of unity modulo n contains some information.

An Template:Mvarth root of unity is **Template:Visible anchor** if it is not a Template:Mvarth root of unity for some smaller Template:Mvar:

## Elementary facts

Every Template:Mvarth root of unity Template:Mvar is a primitive Template:Mvarth root of unity for some Template:Mvar where 1 ≤ *a* ≤ *n*: if *z*^{1} = 1 then Template:Mvar is a primitive first root of unity, otherwise if *z*^{2} = 1 then Template:Mvar is a primitive second (square) root of unity, otherwise, ..., and by assumption there must be a "1" at or before the Template:Mvarth term in the sequence.

If Template:Mvar is an Template:Mvarth root of unity and *a* ≡ *b* (mod *n*) then *z*^{a} = *z*^{b}. By the definition of congruence, *a* = *b* + *kn* for some integer Template:Mvar. But then,

Therefore, given a power *z*^{a} of Template:Mvar, it can be assumed that 1 ≤ *a* ≤ *n*. This is often convenient.

Any integer power of an Template:Mvarth root of unity is also an Template:Mvarth root of unity:

Here Template:Mvar may be negative. In particular, the reciprocal of an Template:Mvarth root of unity is its complex conjugate, and is also an Template:Mvarth root of unity:

Let Template:Mvar be a primitive Template:Mvarth root of unity. Then the powers Template:Mvar, *z*^{2}, … , *z*^{n −1}, *z*^{n} = *z*^{0} = 1 are all distinct. Assume the contrary, that *z*^{a} = *z*^{b} where 1 ≤ *a* < *b* ≤ *n*. Then *z*^{b − a} = 1. But 0 < *b* − *a* < *n*, which contradicts Template:Mvar being primitive.

Since an Template:Mvarth degree polynomial equation can only have Template:Mvar distinct roots, this implies that the powers of a primitive root Template:Mvar, *z*^{2}, … , *z*^{n − 1}, *z*^{n} = *z*^{0} = 1 are in fact all of the Template:Mvarth roots of unity.

From the preceding facts it follows that if Template:Mvar is a primitive Template:Mvarth root of unity:

If Template:Mvar is not primitive there is only one implication:

An example showing that the converse implication is false is given by:

Let Template:Mvar be a primitive Template:Mvarth root of unity and let Template:Mvar be a positive integer. From the above discussion, *z*^{k} is a primitive root of unity for some Template:Mvar. Now if *z*^{ka} = 1, *ka* must be a multiple of Template:Mvar. The smallest number that is divisible by both Template:Mvar and Template:Mvar is their least common multiple, denoted by lcm(*n*, *k*). It is related to their greatest common divisor, gcd(*n*, *k*), by the formula:

i.e.

Therefore, *z*^{k} is a primitive Template:Mvarth root of unity where

Thus, if Template:Mvar and Template:Mvar are coprime, *z ^{k}* is also a primitive Template:Mvarth root of unity, and therefore there are φ(

*n*) (where φ is Euler's totient function) distinct primitive Template:Mvarth roots of unity. (This implies that if Template:Mvar is a prime number, all the roots except +1 are primitive).

In other words, if R(*n*) is the set of all Template:Mvarth roots of unity and P(*n*) is the set of primitive ones, R(*n*) is a disjoint union of the P(*n*):

where the notation means that Template:Mvar goes through all the divisors of Template:Mvar, including 1 and Template:Mvar.

Since the cardinality of R(*n*) is Template:Mvar, and that of P(*n*) is φ(*n*), this demonstrates the classical formula

## Examples

De Moivre's formula, which is valid for all real Template:Mvar and integers Template:Mvar, is

Setting *x* = 2π/*n* gives a primitive Template:Mvarth root of unity:

but for *k* = 1, 2, ⋯ , *n* − 1,

This formula shows that on the complex plane the Template:Mvarth roots of unity are at the vertices of a [[regular polygon|regular Template:Mvar-sided polygon]] inscribed in the unit circle, with one vertex at 1. (See the plots for *n* = 3 and *n* = 5 on the right.) This geometric fact accounts for the term "cyclotomic" in such phrases as cyclotomic field and cyclotomic polynomial; it is from the Greek roots "cyclo" (circle) plus "tomos" (cut, divide).

which is valid for all real Template:Mvar, can be used to put the formula for the Template:Mvarth roots of unity into the form

It follows from the discussion in the previous section that this is a primitive Template:Mvarth-root if and only if the fraction *k*/*n* is in lowest terms, i.e. that Template:Mvar and Template:Mvar are coprime.

The roots of unity are, by definition, the roots of a polynomial equation and are thus algebraic numbers. In fact, Galois theory can be used to show that they may be expressed as expressions involving integers and the operations of addition, subtraction, multiplication, division, and the extraction of roots. (There are more details later in this article at Cyclotomic fields.)

The equation *z*^{1} = 1 obviously has only one solution, +1, which is therefore the only primitive first root of unity. It is a nonprimitive 2nd, 3rd, 4th, ... root of unity.

The equation *z*^{2} = 1 has two solutions, +1 and −1. +1 is the primitive first root of unity, leaving −1 as the only primitive second (square) root of unity. It is a nonprimitive 4th, 6th, 8th, ...root of unity.

The only real roots of unity are ±1; all the others are non-real complex numbers, as can be seen from de Moivre's formula or the figures.

The third (cube) roots satisfy the equation *z*^{3} − 1 = 0; the non-principal root +1 may be factored out, giving (*z* − 1)(*z*^{2} + *z* + 1) = 0. Therefore, the primitive cube roots of unity are the roots of a quadratic equation. (See Cyclotomic polynomial, below.)

The two primitive fourth roots of unity are the two square roots of the primitive square root of unity, −1

The four primitive fifth roots of unity are

The two primitive sixth roots of unity are the negatives (and also the square roots) of the two primitive cube roots:

Gauss observed that if a primitive Template:Mvarth root of unity can be expressed using only square roots, then it is possible to construct the regular Template:Mvar-gon using only ruler and compass, and that if the root of unity requires third or fourth or higher radicals the regular polygon cannot be constructed. The 7th roots of unity are the first that require cube roots. Note that the real part and imaginary part are both real numbers, but complex numbers are buried in the expressions. They cannot be removed. See casus irreducibilis for details.

One of the primitive seventh roots of unity is{{ safesubst:#invoke:Unsubst||date=__DATE__ |$B=
{{#invoke:Category handler|main}}{{#invoke:Category handler|main}}^{[citation needed]}
}}

where Template:Mvar and *ω*^{2} are the primitive cube roots of unity exp(2π*i*/3) and exp(4π*i*/3).

The four primitive eighth roots of unity are ± the square roots of the primitive fourth roots, ±*i*. One of them is:

See heptadecagon for the real part of a 17th root of unity.

## Periodicity

If Template:Mvar is a primitive Template:Mvarth root of unity, then the sequence of powers

- … ,
*z*^{−1},*z*^{0},*z*^{1}, …

is Template:Mvar-periodic (because *z*^{ j + n} = *z*^{ j}⋅*z*^{ n} = *z*^{ j}⋅1 = *z*^{ j} for all values of Template:Mvar), and the Template:Mvar sequences of powers

*s*: … ,_{k}*z*^{ k⋅(−1)},*z*^{ k⋅0},*z*^{ k⋅1}, …

for *k* = 1, … , *n* are all Template:Mvar-periodic (because *z*^{ k⋅(j + n)} = *z*^{ k⋅j}). Furthermore, the set {*s*_{1}, … , *s _{n}*} of these sequences is a basis of the linear space of all Template:Mvar-periodic sequences. This means that

*any*Template:Mvar-periodic sequence of complex numbers

- … ,
*x*_{−1},*x*_{0},*x*_{1}, …

can be expressed as a linear combination of powers of a primitive Template:Mvarth root of unity:

for some complex numbers *X*_{1}, … , *X*_{n} and every integer Template:Mvar.

This is a form of Fourier analysis. If Template:Mvar is a (discrete) time variable, then Template:Mvar is a frequency and *X*_{k} is a complex amplitude.

Choosing for the primitive Template:Mvarth root of unity

*z*=*e*^{2πi/n}= cos(2π/*n*) +*i*⋅sin(2π/*n*)

allows *x*_{j} to be expressed as a linear combination of cos and sin:

*x*_{j}= ∑_{k}*A*_{k}⋅cos(2π⋅*j*⋅*k*/*n*) + ∑_{k}*B*_{k}⋅sin(2π⋅*j*⋅*k*/*n*).

This is a discrete Fourier transform.

## Summation

Let SR(*n*) be the sum of all the Template:Mvarth roots of unity, primitive or not. Then

For *n* = 1 there is nothing to prove. For *n* > 1, it is "intuitively obvious" from the symmetry of the roots in the complex plane. For a rigorous proof, let Template:Mvar be a primitive Template:Mvarth root of unity. Then the set of all roots is given by *z*^{k}, *k* = 0, 1, … , *n* − 1, and their sum is given by the formula for a geometric series:

Let SP(*n*) be the sum of all the primitive Template:Mvarth roots of unity. Then

where μ(*n*) is the Möbius function.

In the section Elementary facts, it was shown that if R(*n*) is the set of all Template:Mvarth roots of unity and P(*n*) is the set of primitive ones, R(*n*) is a disjoint union of the P(*n*):

This implies

Applying the Möbius inversion formula gives

In this formula, if *d* < *n*, then SR(*n*/*d*) = 0, and for *d* = *n*: SR(*n*/*d*) = 1. Therefore, SP(*n*) = *μ*(*n*).

This is the special case *c*_{n}(1) of Ramanujan's sum *c*_{n}(*s*), defined as the sum of the Template:Mvarth powers of the primitive Template:Mvarth roots of unity:

## Orthogonality

From the summation formula follows an orthogonality relationship: for *j* = 1, … , *n* and *j′* = 1, … , *n*

where Template:Mvar is the Kronecker delta and Template:Mvar is any primitive Template:Mvarth root of unity.

The *n* × *n* matrix Template:Mvar whose (*j*, *k*)th entry is

defines a discrete Fourier transform. Computing the inverse transformation using gaussian elimination requires *O*(*n*^{3}) operations. However, it follows from the orthogonality that Template:Mvar is unitary. That is,

and thus the inverse of Template:Mvar is simply the complex conjugate. (This fact was first noted by Gauss when solving the problem of trigonometric interpolation). The straightforward application of Template:Mvar or its inverse to a given vector requires *O*(*n*^{2}) operations. The fast Fourier transform algorithms reduces the number of operations further to *O*(*n* log *n*).

## Cyclotomic polynomials

{{#invoke:main|main}}

The zeroes of the polynomial

are precisely the Template:Mvarth roots of unity, each with multiplicity 1. The Template:Mvarth **cyclotomic polynomial** is defined by the fact that its zeros are precisely the *primitive* Template:Mvarth roots of unity, each with multiplicity 1.

where *z*_{1}, *z*_{2}, *z*_{3}, … ,*z*_{φ(n)} are the primitive Template:Mvarth roots of unity, and φ(*n*) is Euler's totient function. The polynomial Φ_{n}(*z*) has integer coefficients and is an irreducible polynomial over the rational numbers (i.e., it cannot be written as the product of two positive-degree polynomials with rational coefficients). The case of prime Template:Mvar, which is easier than the general assertion, follows by applying Eisenstein's criterion to the polynomial

and expanding via the binomial theorem.

Every Template:Mvarth root of unity is a primitive Template:Mvarth root of unity for exactly one positive divisor Template:Mvar of Template:Mvar. This implies that

This formula represents the factorization of the polynomial *z*^{n} − 1 into irreducible factors.

*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)

Applying Möbius inversion to the formula gives

where *μ* is the Möbius function.

So the first few cyclotomic polynomials are

- Φ
_{1}(*z*) =*z*− 1 - Φ
_{2}(*z*) = (*z*^{2}− 1)⋅(*z*− 1)^{−1}=*z*+ 1 - Φ
_{3}(*z*) = (*z*^{3}− 1)⋅(*z*− 1)^{−1}=*z*^{2}+*z*+ 1 - Φ
_{4}(*z*) = (*z*^{4}− 1)⋅(*z*^{2}− 1)^{−1}=*z*^{2}+ 1 - Φ
_{5}(*z*) = (*z*^{5}− 1)⋅(*z*− 1)^{−1}=*z*^{4}+*z*^{3}+*z*^{2}+*z*+ 1 - Φ
_{6}(*z*) = (*z*^{6}− 1)⋅(*z*^{3}− 1)^{−1}⋅(*z*^{2}− 1)^{−1}⋅(*z*− 1) =*z*^{2}−*z*+ 1 - Φ
_{7}(*z*) = (*z*^{7}− 1)⋅(*z*− 1)^{−1}=*z*^{6}+*z*^{5}+*z*^{4}+*z*^{3}+*z*^{2}+*z*+ 1.

If Template:Mvar is a prime number, then all the Template:Mvarth roots of unity except 1 are primitive Template:Mvarth roots, and we have

Substituting any positive integer ≥ 2 for Template:Mvar, this sum becomes a [[radix|base Template:Mvar]] 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 Φ_{105}. It is not a surprise it takes this long to get an example, because the behavior of the coefficients depends not so much on Template:Mvar as on how many odd prime factors appear in Template:Mvar. More precisely, it can be shown that if Template:Mvar has 1 or 2 odd prime factors (e.g., *n* = 150) then the Template:Mvarth cyclotomic polynomial only has coefficients 0, 1 or −1. Thus the first conceivable Template:Mvar for which there could be a coefficient besides 0, 1, or −1 is a product of the three smallest odd primes, and that is 3⋅5⋅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 *n* = *p*_{1}⋅*p*_{2}⋅ ⋯ ⋅*p*_{t}, where *p*_{1} < *p*_{2} < ⋯ < *p*_{t} are odd primes, *p*_{1} + *p*_{2} > *p*_{t}, and *t* is odd, then 1 − *t* occurs as a coefficient in the Template:Mvarth cyclotomic polynomial.^{[3]}

Many restrictions are known about the values that cyclotomic polynomials can assume at integer values. For example, if Template:Mvar is prime and *d* ∣ Φ_{p}(*d*), then either *d* ≡ 1 (mod *p*), or *d* ≡ 0 (mod *p*).

Cyclotomic polynomials are solvable in radicals, as roots of unity are themselves radicals. Moreover, there exist more informative radical expressions for Template:Mvarth roots of unity with the additional property^{[4]} that every value of the expression obtained by choosing values of the radicals (for example, signs of square roots) is a primitive Template:Mvarth root of unity. This was already shown by Gauss in 1797.^{[5]} Efficient algorithms exist for calculating such expressions.^{[6]}

## Cyclic groups

The Template:Mvarth roots of unity form under multiplication a cyclic group of order Template:Mvar, and in fact these groups comprise all of the finite subgroups of the multiplicative group of the complex number field. A generator for this cyclic group is a primitive Template:Mvarth root of unity.

The Template:Mvarth roots of unity form an irreducible representation of any cyclic group of order Template:Mvar. The orthogonality relationship also follows from group-theoretic principles as described in character group.

The roots of unity appear as entries of the eigenvectors of any circulant matrix, i.e. matrices that are invariant under cyclic shifts, a fact that also follows from group representation theory as a variant of Bloch's theorem.^{[7]} In particular, if a circulant Hermitian matrix is considered (for example, a discretized one-dimensional Laplacian with periodic boundaries^{[8]}), the orthogonality property immediately follows from the usual orthogonality of eigenvectors of Hermitian matrices.

## Cyclotomic fields

{{#invoke:main|main}}
By adjoining a primitive Template:Mvarth root of unity to **Q**, one obtains the Template:Mvarth cyclotomic field **Q**(exp(2π*i*/*n*)). This field contains all Template:Mvarth roots of unity and is the splitting field of the Template:Mvarth cyclotomic polynomial over **Q**. The field extension **Q**(exp(2π*i*/*n*))/**Q** has degree φ(*n*) and its Galois group is naturally isomorphic to the multiplicative group of units of the ring **Z**/*n***Z**.

As the Galois group of **Q**(exp(2π*i*/*n*))/**Q** is abelian, this is an abelian extension. Every subfield of a cyclotomic field is an abelian extension of the rationals. It follows that every *n*th root of unity may be expressed in term of *k*-roots, with various *k* not exceeding *φ(n)*. In these cases Galois theory can be written out explicitly in terms of Gaussian periods: this theory from the *Disquisitiones Arithmeticae* of Gauss was published many years before Galois.^{[9]}

Conversely, *every* abelian extension of the rationals is such a subfield of a cyclotomic field – this is the content of a theorem of Kronecker, usually called the *Kronecker–Weber theorem* on the grounds that Weber completed the proof.

## Relation to integer rings

For *n* = 2, both roots of unity 1 and −1 belong to **Z**. For certain Template:Mvar corresponding roots of unity are quadratic integers:

- For
*n*= 3, 6 they are Eisenstein integers (*D*= −3). - For
*n*= 4 they are Gaussian integers (*D*= −1): see imaginary unit.

For *n* = 5, 10, neither of non-real roots of unity (which satisfy a quartic equation) is a quadratic integer, but the sum *z* + *Template:Overline* = 2 Re*z* of each root with its complex conjugate (also a 5th root of unity) is an element of the ring [[quadratic integer|**Z**[{{ safesubst:#invoke:Unsubst||$B=1 + Template:Sqrt/2}}]]] (*D* = 5). For two pairs of non-real 5th roots of unity these sums are inverse golden ratio and minus golden ratio.

For *n* = 8, for any root: *z* + *Template:Overline* equals to either ±2, 0, or ±[[square root of 2|Template:Sqrt]] (*D* = 2).

## See also

- Argand system
- Circle group, the unit complex numbers
- Group scheme of roots of unity
- Primitive root modulo
*n* - Dirichlet character
- Ramanujan's sum

## Notes

{{ safesubst:#invoke:Unsubst||$N=Refimprove |date=__DATE__ |$B= {{#invoke:Message box|ambox}} }}

- ↑ {{#invoke:citation/CS1|citation |CitationClass=book }}
- ↑ {{#invoke:citation/CS1|citation |CitationClass=book }}
- ↑ Emma Lehmer,
*On the magnitude of the coefficients of the cyclotomic polynomial*, Bulletin of the American Mathematical Society 42 (1936), no. 6, pp. 389–392. - ↑ {{#invoke:Citation/CS1|citation |CitationClass=journal }}
- ↑ {{#invoke:citation/CS1|citation |CitationClass=book }}
- ↑ Template:Cite web
- ↑ T. Inui, Y. Tanabe, and Y. Onodera,
*Group Theory and Its Applications in Physics*(Springer, 1996). - ↑ Gilbert Strang, "The discrete cosine transform,"
*SIAM Review***41**(1), 135–147 (1999). - ↑ The
*Disquisitiones*was published in 1801, Galois was born in 1811, died in 1832, but wasn't published until 1846.

## References

- Template:Lang Algebra
- Template:Cite web
- Template:Cite web
- Template:Neukirch ANT
- {{#invoke:citation/CS1|citation

|CitationClass=book }}

- {{#invoke:citation/CS1|citation

|CitationClass=book }}

- {{#invoke:citation/CS1|citation

|CitationClass=book }}

## Further reading

- {{#invoke:citation/CS1|citation

|CitationClass=book }}

Template:Algebraic numbers {{ safesubst:#invoke:Unsubst||$N=Use dmy dates |date=__DATE__ |$B= }}