![]() | 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. (February 2023) |
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
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 and . In this case, there are three cube roots of unity (1, 2, and 4). When 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, what needs to be checked is:
Among the primitive kth 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 kth roots of unity, at all.
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.
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.
To find a modulus such that there are primitive roots of unity modulo , the following theorem reduces the problem to a simpler one:
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 .
![]() | 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. (February 2023) |
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
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 and . In this case, there are three cube roots of unity (1, 2, and 4). When 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, what needs to be checked is:
Among the primitive kth 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 kth roots of unity, at all.
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.
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.
To find a modulus such that there are primitive roots of unity modulo , the following theorem reduces the problem to a simpler one:
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 .