In number theory, a kth root of unity modulo n for positive integers k, n ≥ 2, is a root of unity in the ring of integers modulo n; that is, a solution x to the equation (or congruence)
If k is the smallest such exponent for x, then x is called a primitive kth root of unity modulo n.[1] See modular arithmetic for notation and terminology.
The roots of unity modulo n are exactly the integers that are coprime with n. In fact, these integers are roots of unity modulo n by Euler's theorem, and the other integers cannot be roots of unity modulo n, because they are zero divisors modulo n. A primitive root modulo n, is a generator of the group of units of the ring of integers modulo n. There exist primitive roots modulo n if and only if
A root of unity modulo n is a primitive kth root of unity modulo n for some divisor k of
and, conversely, there are primitive kth roots of unity modulo n if and only if k is a divisor of
For the lack of a widely accepted symbol, we denote the number of kth roots of unity modulo n by
It satisfies a number of properties: Let
In this case, there are three cube roots of unity (1, 2, and 4).
however, there is only one cube root of unity, the unit 1 itself.
This behavior is quite different from the field of complex numbers where every nonzero number has k kth roots.
For the lack of a widely accepted symbol, we denote the number of primitive kth roots of unity modulo n by
It satisfies the following properties: By fast exponentiation, one can check that
If this is true, x is a kth root of unity modulo n but not necessarily primitive.
If it is not a primitive root, then there would be some divisor ℓ of k, with
In order to exclude this possibility, one has only to check for a few ℓ's equal k divided by a prime.
That is, x is a primitive kth root of unity modulo n if and only if
every positive integer less than 17 is a 16th root of unity modulo 17, and the integers that are primitive 16th roots of unity modulo 17 are exactly those such that
Once a primitive kth root of unity x is obtained, every power
th root of unity, but not necessarily a primitive one.
is not primitive, then there exists a divisor
are coprime, there exists integers
th root of unity because there is the smaller exponent
In what integer residue class rings does a primitive kth root of unity exist?
It can be used to compute a discrete Fourier transform (more precisely a number theoretic transform) of a
In order to perform the inverse transform, divide by
A simple way to find such an n is to check for primitive kth roots with respect to the moduli in the arithmetic progression
According to Dirichlet's theorem on arithmetic progressions there are infinitely many primes in the progression, and for a prime
, and thus there are primitive kth roots of unity.
But the test for primes is too strong, and there may be other appropriate moduli.
, the following theorem reduces the problem to a simpler one: Backward direction: If there is a primitive