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 n. 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.

If the characteristic of the field is zero, the roots are complex numbers that are also algebraic integers.

An nth root of unity, where n is a positive integer, is a number z satisfying the equation[1][2]

[6] In the above formula in terms of exponential and trigonometric functions, the primitive nth roots of unity are those for which k and n are coprime integers.

Subsequent sections of this article will comply with complex roots of unity.

is the greatest common divisor of n and k. This results from the fact that ka is the smallest multiple of k that is also a multiple of n. In other words, ka is the least common multiple of k and n. Thus Thus, if k and n are coprime, zk is also a primitive nth root of unity, and therefore there are φ(n) distinct primitive nth roots of unity (where φ is Euler's totient function).

If k is an integer, ωk is a primitive nth root of unity if and only if k and n are coprime.

The rules of exponentiation imply that the composition of two such automorphisms is obtained by multiplying the exponents.

This shows that this Galois group is abelian, and implies thus that the primitive roots of unity may be expressed in terms of radicals.

De Moivre's formula, which is valid for all real x and integers n, is Setting x = ⁠2π/n⁠ gives a primitive nth root of unity – one gets but for k = 1, 2, …, n − 1.

This formula shows that in the complex plane the nth roots of unity are at the vertices of a regular n-sided polygon inscribed in the unit circle, with one vertex at 1 (see the plots for n = 3 and n = 5 on the right).

Euler's formula which is valid for all real x, can be used to put the formula for the nth roots of unity into the form It follows from the discussion in the previous section that this is a primitive nth-root if and only if the fraction ⁠k/n⁠ is in lowest terms; that is, that k and n are coprime.

An irrational number that can be expressed as the real part of the root of unity; that is, as

The degree of Φn is given by Euler's totient function, which counts (among other things) the number of primitive nth roots of unity.

Galois theory can be used to show that the cyclotomic polynomials may be conveniently solved in terms of radicals.

Gauss proved that a primitive nth 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 n-gon.

This means that any n-periodic sequence of complex numbers can be expressed as a linear combination of powers of a primitive nth root of unity: for some complex numbers X1, … , Xn and every integer j.

Choosing for the primitive nth root of unity allows xj to be expressed as a linear combination of cos and sin: This is a discrete Fourier transform.

In the section Elementary properties, it was shown that if R(n) is the set of all nth 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.

This is the special case cn(1) of Ramanujan's sum cn(s),[10] defined as the sum of the sth powers of the primitive nth roots of unity: From the summation formula follows an orthogonality relationship: for j = 1, … , n and j′ = 1, … , n where δ is the Kronecker delta and z is any primitive nth root of unity.

Computing the inverse transformation using Gaussian elimination requires O(n3) operations.

The fast Fourier transform algorithms reduces the number of operations further to O(n log n).

The zeros of the polynomial are precisely the nth roots of unity, each with multiplicity 1.

[9] The case of prime n, which is easier than the general assertion, follows by applying Eisenstein's criterion to the polynomial and expanding via the binomial theorem.

Every nth root of unity is a primitive dth root of unity for exactly one positive divisor d of n. This implies that[9] This formula represents the factorization of the polynomial zn − 1 into irreducible factors: Applying Möbius inversion to the formula gives where μ is the Möbius function.

It is not a surprise it takes this long to get an example, because the behavior of the coefficients depends not so much on n as on how many odd prime factors appear in n. More precisely, it can be shown that if n has 1 or 2 odd prime factors (for example, n = 150) then the nth cyclotomic polynomial only has coefficients 0, 1 or −1.

A theorem of Schur says that there are cyclotomic polynomials with coefficients arbitrarily large in absolute value.

The roots of unity appear as entries of the eigenvectors of any circulant matrix; that is, matrices that are invariant under cyclic shifts, a fact that also follows from group representation theory as a variant of Bloch's theorem.

[15][page needed] In particular, if a circulant Hermitian matrix is considered (for example, a discretized one-dimensional Laplacian with periodic boundaries[16]), the orthogonality property immediately follows from the usual orthogonality of eigenvectors of Hermitian matrices.

It follows that every nth root of unity may be expressed in term of k-roots, with various k not exceeding φ(n).