Root of unity

In mathematics, a root of unity, occasionally called a de Moivre number, is any complex number that yields 1 when raised to some positive integer power . 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.
Roots of unity can be defined in any field. If the characteristic of the field is zero, the roots are complex numbers that are also algebraic integers. For fields with a positive characteristic, the roots belong to a finite field, and, conversely, every nonzero element of a finite field is a root of unity. Any algebraically closed field contains exactly th roots of unity, except when is a multiple of the (positive) characteristic of the field.
General definition.
An "th root of unity", where is a positive integer, is a number satisfying the equation
Unless otherwise specified, the roots of unity may be taken to be complex numbers (including the number 1, and the number –1 if is even, which are complex with a zero imaginary part), and in this case, the th roots of unity are
However, the defining equation of roots of unity is meaningful over any field (and even over any ring) , and this allows considering roots of unity in . Whichever is the field , the roots of unity in are either complex numbers, if the characteristic of is 0, or, otherwise, belong to a finite field. Conversely, every nonzero element in a finite field is a root of unity in that field. See Root of unity modulo "n" and Finite field for further details.
An th root of unity is said to be if it is not an th root of unity for some smaller , that is if
If "n" is a prime number, all th roots of unity, except 1, are primitive.
In the above formula in terms of exponential and trigonometric functions, the primitive th roots of unity are those for which and are coprime integers.
Subsequent sections of this article will comply with complex roots of unity. For the case of roots of unity in fields of nonzero characteristic, see . For the case of roots of unity in rings of modular integers, see Root of unity modulo n.
Elementary properties.
Every th root of unity is a primitive th root of unity for some , which is the smallest positive integer such that .
Any integer power of an th root of unity is also an th root of unity, as
This is also true for negative exponents. In particular, the reciprocal of an th root of unity is its complex conjugate, and is also an th root of unity:
If is an th root of unity and then . In fact, by the definition of congruence, for some integer , and
Therefore, given a power of , one has , where is the remainder of the Euclidean division of by .
Let be a primitive th root of unity. Then the powers , , ..., , are th root of unity and are all distinct. (If where , then , which would imply that would not be primitive.) This implies that , , ..., , are all of the th roots of unity, since an th-degree polynomial equation has at most distinct solutions.
From the preceding, it follows that, if is a primitive th root of unity, then formula_7 if and only if formula_8
If is not primitive then formula_9 implies formula_10 but the converse may be false, as shown by the following example. If , a non-primitive th root of unity is , and one has formula_11, although formula_12
Let be a primitive th root of unity. A power of is a primitive th root of unity for 
where formula_14 is the greatest common divisor of and . This results from the fact that is the smallest multiple of that is also a multiple of . In other words, is the least common multiple of and . Thus 
Thus, if and are coprime, is also a primitive th root of unity, and therefore there are (where is Euler's totient function) distinct primitive th roots of unity. (This implies that if is a prime number, all the roots except are primitive.)
In other words, if is the set of all th roots of unity and is the set of primitive ones, is a disjoint union of the :
where the notation means that goes through all the divisors of , including and .
Since the cardinality of is , and that of is , this demonstrates the classical formula
Group properties.
Group of all roots of unity.
The product and the multiplicative inverse of two roots of unity are also roots of unity. In fact, if and , then , and , where is the least common multiple of and .
Therefore, the roots of unity form an abelian group under multiplication. This group is the torsion subgroup of the circle group.
Group of th roots of unity.
The product and the multiplicative inverse of two th roots of unity are also th roots of unity. Therefore, the th roots of unity form a group under multiplication.
Given a primitive th root of unity , the other th roots are powers of . This means that the group of the th roots of unity is a cyclic group. It is worth remarking that the term of "cyclic group" originated from the fact that this group is a subgroup of the circle group.
Galois group of the primitive th roots of unity.
Let formula_18 be the field extension of the rational numbers generated over formula_19 by a primitive th root of unity . As every th root of unity is a power of , the field formula_18 contains all th roots of unity, and formula_18 is a Galois extension of formula_22
If is an integer, is a primitive th root of unity if and only if and are coprime. In this case, the map
induces an automorphism of formula_18, which maps every th root of unity to its th power. Every automorphism of formula_18 is obtained in this way, and these automorphisms form the Galois group of formula_18 over the field of the rationals.
The rules of exponentiation imply that the composition of two such automorphisms is obtained by multiplying the exponents. It follows that the map
defines a group isomorphism between the units of the ring of integers modulo and the Galois group of formula_28
This shows that this Galois group is abelian, and implies thus that the primitive roots of unity may be expressed in terms of radicals.
Trigonometric expression.
De Moivre's formula, which is valid for all real and integers , is
Setting gives a primitive th root of unity, one gets
but
for . In other words, 
is a primitive th root of unity.
This formula shows that on the complex plane the th roots of unity are at the vertices of a regular -sided polygon inscribed in the unit circle, with one vertex at 1. (See the plots for and 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).
Euler's formula
which is valid for all real , can be used to put the formula for the th roots of unity into the form
It follows from the discussion in the previous section that this is a primitive th-root if and only if the fraction is in lowest terms, i.e. that and are coprime.
Algebraic expression.
The th roots of unity are, by definition, the roots of the polynomial , and are thus algebraic numbers. As this polynomial is not irreducible (except for ), the primitive th roots of unity are roots of an irreducible polynomial of lower degree, called the cyclotomic polynomial, and often denoted . The degree of is given by Euler's totient function, which counts (among other things) the number of primitive th roots of unity. The roots of are exactly the primitive th roots of unity.
Galois theory can be used to show that cyclotomic polynomials may be conveniently solved in terms of radicals. (The trivial form formula_35 is not convenient, because it contains non-primitive roots, such as 1, which are not roots of the cyclotomic polynomial, and because it does not give the real and imaginary parts separately.) This means that, for each positive integer , there exists an expression built from integers by root extractions, additions, subtractions, multiplications, and divisions (nothing else), such that the primitive th roots of unity are exactly the set of values that can be obtained by choosing values for the root extractions ( possible values for a th root). (For more details see , below.)
Gauss proved that a primitive th root of unity can be expressed using only square roots, addition, subtraction, multiplication and division if and only if it is possible to construct with compass and straightedge the regular -gon. This is the case if and only if is either a power of two or the product of a power of two and Fermat primes that are all different.
If is a primitive th root of unity, the same is true for , and formula_36 is twice the real part of . In other words, is a reciprocal polynomial, the polynomial formula_37 that has as a root may be deduced from by the standard manipulation on reciprocal polynomials, and the primitive th roots of unity may be deduced from the roots of formula_37 by solving the quadratic equation formula_39 That is, the real part of the primitive root is formula_40 and its imaginary part is formula_41
The polynomial formula_37 is an irreducible polynomial whose roots are all real. Its degree is a power of two, if and only if is a product of a power of two by a product (possibly empty) of distinct Fermat primes, and the regular -gon is constructible with compass and straightedge. Otherwise, it is solvable in radicals, but one are in the casus irreducibilis, that is, every expression of the roots in terms of radicals involves "nonreal radicals".
Periodicity.
If is a primitive th root of unity, then the sequence of powers
is -periodic (because for all values of ), and the sequences of powers
for are all -periodic (because ). Furthermore, the set } of these sequences is a basis of the linear space of all -periodic sequences. This means that "any" -periodic sequence of complex numbers
can be expressed as a linear combination of powers of a primitive th root of unity:
for some complex numbers and every integer .
This is a form of Fourier analysis. If is a (discrete) time variable, then is a frequency and is a complex amplitude.
Choosing for the primitive th root of unity
allows to be expressed as a linear combination of and :
This is a discrete Fourier transform.
Summation.
Let be the sum of all the th roots of unity, primitive or not. Then
This is an immediate consequence of Vieta's formulas. In fact, the th roots of unity being the roots of the polynomial , their sum is the coefficient of degree , which is either 1 or 0 according whether or .
Alternatively, for there is nothing to prove. For there exists a root . Since the set of all the th roots of unity is a group, , so the sum satisfies , whence .
Let be the sum of all the primitive th roots of unity. Then
where is the Möbius function.
In the section Elementary properties, it was shown that if is the set of all th roots of unity and is the set of primitive ones, is a disjoint union of the :
This implies
Applying the Möbius inversion formula gives
In this formula, if , then , and for : . Therefore, .
This is the special case of Ramanujan's sum , defined as the sum of the th powers of the primitive th roots of unity:
Orthogonality.
From the summation formula follows an orthogonality relationship: for and 
where is the Kronecker delta and is any primitive th root of unity.
The matrix whose th entry is
defines a discrete Fourier transform. Computing the inverse transformation using gaussian elimination requires operations. However, it follows from the orthogonality that is unitary. That is,
and thus the inverse of is simply the complex conjugate. (This fact was first noted by Gauss when solving the problem of trigonometric interpolation). The straightforward application of or its inverse to a given vector requires operations. The fast Fourier transform algorithms reduces the number of operations further to .
Cyclotomic polynomials.
The zeroes of the polynomial
are precisely the th roots of unity, each with multiplicity 1. The th "cyclotomic polynomial" is defined by the fact that its zeros are precisely the "primitive" th roots of unity, each with multiplicity 1.
where are the primitive th roots of unity, and is Euler's totient function. The polynomial 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 , which is easier than the general assertion, follows by applying Eisenstein's criterion to the polynomial
and expanding via the binomial theorem.
Every th root of unity is a primitive th root of unity for exactly one positive divisor of . This implies that
This formula represents the factorization of the polynomial into irreducible factors.
Applying Möbius inversion to the formula gives
where is the Möbius function. So the first few cyclotomic polynomials are
If is a prime number, then all the th roots of unity except 1 are primitive th roots, and we have
Substituting any positive integer ≥ 2 for , this sum becomes a base 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 . It is not a surprise it takes this long to get an example, because the behavior of the coefficients depends not so much on as on how many odd prime factors appear in . More precisely, it can be shown that if has 1 or 2 odd prime factors (e.g., ) then the th cyclotomic polynomial only has coefficients 0, 1 or −1. Thus the first conceivable for which there could be a coefficient besides 0, 1, or −1 is a product of the three smallest odd primes, and that is . 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 formula_69 where formula_70 are odd primes, formula_71 and "t" is odd, then occurs as a coefficient in the th cyclotomic polynomial.
Many restrictions are known about the values that cyclotomic polynomials can assume at integer values. For example, if is prime, then if and only .
Cyclotomic polynomials are solvable in radicals, as roots of unity are themselves radicals. Moreover, there exist more informative radical expressions for th roots of unity with the additional property that every value of the expression obtained by choosing values of the radicals (for example, signs of square roots) is a primitive th root of unity. This was already shown by Gauss in 1797. Efficient algorithms exist for calculating such expressions.
Cyclic groups.
The th roots of unity form under multiplication a cyclic group of order , 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 th root of unity.
The th roots of unity form an irreducible representation of any cyclic group of order . 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. In particular, if a circulant Hermitian matrix is considered (for example, a discretized one-dimensional Laplacian with periodic boundaries), the orthogonality property immediately follows from the usual orthogonality of eigenvectors of Hermitian matrices.
Cyclotomic fields.
By adjoining a primitive th root of unity to formula_72 one obtains the th cyclotomic field formula_73This field contains all th roots of unity and is the splitting field of the th cyclotomic polynomial over formula_22 The field extension formula_75 has degree φ("n") and its Galois group is naturally isomorphic to the multiplicative group of units of the ring formula_76
As the Galois group of formula_75 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.
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 quadratic integers.
For , both roots of unity and are integers.
For three values of , the roots of unity are quadratic integers:
For four other values of , the primitive roots of unity are not quadratic integers, but the sum of any root of unity with its complex conjugate (also an th root of unity) is a quadratic integer.
For , none of the non-real roots of unity (which satisfy a quartic equation) is a quadratic integer, but the sum of each root with its complex conjugate (also a 5th root of unity) is an element of the ring Z[] (). For two pairs of non-real 5th roots of unity these sums are inverse golden ratio and minus golden ratio.
For , for any root of unity equals to either 0, ±2, or ± ().
For , for any root of unity, equals to either 0, ±1, ±2 or ± ().