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 where and are respectively the Carmichael function and Euler's totient function.
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
Properties
- The maximum possible radix exponent for primitive roots modulo is , where λ denotes the Carmichael function.
- A radix exponent for a primitive root of unity is a divisor of .
- Every divisor of yields a primitive th root of unity. One can obtain such a root by choosing a th primitive root of unity (that must exist by definition of λ), named and compute the power .
- If x is a primitive kth root of unity and also a (not necessarily primitive) ℓth root of unity, then k is a divisor of ℓ. This is true, because Bézout's identity yields an integer linear combination of k and ℓ equal to . Since k is minimal, it must be and is a divisor of ℓ.
Number of primitive 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:
- Consequently the function has values different from zero, where computes the number of divisors.
- for , since -1 is always a square root of 1.
- for
- for and in (sequence A033948 in the OEIS)
- with being Euler's totient function
- The connection between and can be written in an elegant way using a Dirichlet convolution:
- , i.e.
- One can compute values of recursively from using this formula, which is equivalent to the Möbius inversion formula.
Finding multiple primitive kth roots modulo n
Once a primitive kth root of unity x is obtained, every power is a th root of unity, but not necessarily a primitive one. The power is a primitive th root of unity if and only if and are coprime. The proof is as follows: If is not primitive, then there exists a divisor of with , and since and are coprime, there exists integers such that . This yields
,
which means that is not a primitive th root of unity because there is the smaller exponent .
That is, by exponentiating x one can obtain different primitive kth roots of unity, but these may not be all such roots. However, finding all of them is not so easy.
Finding an n with a primitive kth root of unity modulo n
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 -dimensional integer vector. In order to perform the inverse transform, divide by ; that is, k is also a unit modulo
A simple way to find such an n is to check for primitive kth roots with respect to the moduli in the arithmetic progression All of these moduli are coprime to k and thus k is a unit. According to Dirichlet's theorem on arithmetic progressions there are infinitely many primes in the progression, and for a prime , it holds . Thus if is prime, then , and thus there are primitive kth roots of unity. But the test for primes is too strong, and there may be other appropriate moduli.
Finding an n with multiple primitive roots of unity modulo n
To find a modulus such that there are primitive roots of unity modulo , the following theorem reduces the problem to a simpler one:
- For given there are primitive roots of unity modulo if and only if there is a primitive th root of unity modulo n.
- Proof
Backward direction:
If there is a primitive th root of unity modulo called , then is a th root of unity modulo .
Forward direction:
If there are primitive roots of unity modulo , then all exponents are divisors of . This implies and this in turn means there is a primitive th root of unity modulo .