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
- If x is a kth 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) kth root of unity modulo n, where k is the
multiplicative order of x modulo n.
- If x is a kth root of unity and
is not a
zero divisor, then
, because
![{\displaystyle (x-1)\cdot \sum _{j=0}^{k-1}x^{j}\equiv x^{k}-1\equiv 0{\pmod {n}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/09fec4a837228094294bfce4a93611ebc338b556)
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:
for ![{\displaystyle n\geq 2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e6bf67f9d06ca3af619657f8d20ee1322da77174)
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.
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.
- 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:
![{\displaystyle g(n,k)={\begin{cases}>0&{\text{if }}k\mid \lambda (n),\\0&{\text{otherwise}}.\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/465b6a00f34a28f3552b9e19d892bd61c0f4751b)
- Consequently the function
has
values different from zero, where
computes the
number of divisors.
![{\displaystyle g(n,1)=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/24a949499c40be271f682606281f93731ea4866f)
![{\displaystyle g(4,2)=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/48913f51881a8983edd07490e9f068e1c4217b72)
for
, since -1 is always a
square root of 1.
for ![{\displaystyle k\in [2,n-1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/394752460455aa966bc9ca06478663613afb7efe)
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. ![{\displaystyle f(n,k)=\sum _{d\mid k}g(n,d)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/90ffb559367c6015f2899ae35ba8cf83cd887f68)
- One can compute values of
recursively from
using this formula, which is equivalent to the
Möbius inversion formula.
Testing whether x is a primitive kth root of unity modulo n
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:
![{\displaystyle \forall p{\text{ prime dividing}}\ k,\quad x^{k/p}\not \equiv 1{\pmod {n}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a9fbe44af33f5536e9ae4c595ab88985fcd6367b)
Finding a primitive kth root of unity modulo n
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.
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
.