Root of unity modulo n
![]() | This article may require cleanup to meet Wikipedia's quality standards. The specific problem is: Lack of context, lack of explicit examples, lack of explanation of the main differences with Root of unity and Finite field § Roots of unity. (October 2018) |
In mathematics, namely ring theory, a k-th 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 k-th root of unity modulo n.[1] See modular arithmetic for notation and terminology.
Do not confuse this with a primitive root modulo n, which is a generator of the group of units of the ring of integers modulo n. The primitive roots modulo n are the primitive -roots of unity modulo n, where is Euler's totient function.
Roots of unity
Properties
- If x is a k-th root of unity modulo n, then x is a unit (invertible) whose inverse is . That is, x and n are coprime.
- If x is a unit, then it is a (primitive) k-th root of unity modulo n, where k is the multiplicative order of x modulo n.
- If x is a k-th root of unity and is not a zero divisor, then , because
Number of k-th roots
For the lack of a widely accepted symbol, we denote the number of k-th roots of unity modulo n by . It satisfies a number of properties:
- for
- where λ denotes the Carmichael function and denotes Euler's totient function
- is a multiplicative function
- where the bar denotes divisibility
- where denotes the least common multiple
- For prime , . The precise mapping from to is not known. If it were known, then together with the previous law it would yield a way to evaluate quickly.
Primitive roots of unity
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. You can obtain one by choosing a -th primitive root of unity (that must exist by definition of λ), named and compute the power .
- If x is a primitive k-th 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 k-th roots
For the lack of a widely accepted symbol, we denote the number of primitive k-th 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.
- You can compute values of recursively from using this formula, which is equivalent to the Möbius inversion formula.
Testing whether x is a primitive k-th root of unity modulo n
By fast exponentiation you can check that . If this is true, x is a k-th 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, what needs to be checked is:
Finding a primitive k-th root of unity modulo n
Among the primitive k-th roots of unity, the primitive -th roots are most frequent. It is thus recommended to try some integers for being a primitive -th root, what will succeed quickly. For a primitive -th root x, the number is a primitive -th root of unity. If k does not divide , then there will be no k-th roots of unity, at all.
Finding multiple primitive k-th roots modulo n
Once you have a primitive k-th root of unity x, 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 an inverse of modulo . 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 k-th 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 k-th root of unity modulo n
You may want to know, in what integer residue class rings you have a primitive k-th root of unity. You need it for instance if you want to compute a Discrete Fourier Transform (more precisely a Number theoretic transform) of a -dimensional integer vector. In order to perform the inverse transform, you also need to divide by , that is, k shall also be a unit modulo
A simple way to find such an n is to check for primitive k-th 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 you have primitive k-th roots of unity. But the test for primes is too strong, you may find other appropriate moduli.
Finding an n with multiple primitive roots of unity modulo n
If you want to have a modulus such that there are primitive -th, -th, ..., -th roots of unity modulo , the following theorem reduces the problem to a simpler one:
- For given there are primitive -th, ..., -th 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 -th, ..., -th 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 .
References
- ^ Finch, Stephen; Martin, Greg; Sebah, And Pascal (2010). "Roots of unity and nullity modulo n" (PDF). Proceedings of the American Mathematical Society. 138 (8): 2729–2743. doi:10.1090/s0002-9939-10-10341-4. Retrieved 2011-02-20.