In mathematics, namely ring theory, a k-th root of unity modulo n for positive integers k, n ≥ 2, is a solution x to the equation (or congruence)
x
k
≡
1
(
mod
n
)
. If k is the smallest such exponent for x, then x is called a primitive k-th root of unity modulo n. See modular arithmetic for notation and terminology.
Do not confuse this with a Primitive root modulo n, where the primitive root must generate all units of the residue class ring
Z
/
n
Z
by exponentiation. That is, there are always roots and primitive roots of unity modulo n for n ≥ 2, but for some n there is no primitive root modulo n. Being a root of unity or a primitive root of unity modulo n always depends on the exponent k and the modulus n, whereas being a primitive root modulo n only depends on the modulus n — the exponent is automatically
φ
(
n
)
.
If x is a k-th root of unity, then x is a unit (invertible) whose inverse is
x
k
−
1
. 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
x
−
1
is not a zero divisor, then
∑
j
=
0
k
−
1
x
j
≡
0
(
mod
n
)
, because
For the lack of a widely accepted symbol, we denote the number of k-th roots of unity modulo n by
f
(
n
,
k
)
. It satisfies a number of properties:
f
(
n
,
1
)
=
1
for
n
≥
2
f
(
n
,
λ
(
n
)
)
=
φ
(
n
)
where λ denotes the Carmichael function and
φ
denotes Euler's totient function
n
↦
f
(
n
,
k
)
is a multiplicative function
k
∣
l
⟹
f
(
n
,
k
)
∣
f
(
n
,
l
)
where the bar denotes divisibility
f
(
n
,
l
c
m
(
a
,
b
)
)
=
l
c
m
(
f
(
n
,
a
)
,
f
(
n
,
b
)
)
where
l
c
m
denotes the least common multiple
For prime
p
,
∀
i
∈
N
∃
j
∈
N
f
(
n
,
p
i
)
=
p
j
. The precise mapping from
i
to
j
is not known. If it were known, then together with the previous law it would yield a way to evaluate
f
quickly.
The maximum possible radix exponent for primitive roots modulo
n
is
λ
(
n
)
, where λ denotes the Carmichael function.
A radix exponent for a primitive root of unity is a divisor of
λ
(
n
)
.
Every divisor
k
of
λ
(
n
)
yields a primitive
k
-th root of unity. You can obtain one by choosing a
λ
(
n
)
-th primitive root of unity (that must exist by definition of λ), named
x
and compute the power
x
λ
(
n
)
/
k
.
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
g
c
d
(
k
,
ℓ
)
. Since k is minimal, it must be
k
=
g
c
d
(
k
,
ℓ
)
and
g
c
d
(
k
,
ℓ
)
is a divisor of ℓ.
For the lack of a widely accepted symbol, we denote the number of primitive k-th roots of unity modulo n by
g
(
n
,
k
)
. It satisfies the following properties:
g
(
n
,
k
)
=
{
>
0
if
k
∣
λ
(
n
)
,
0
otherwise
.
Consequently the function
k
↦
g
(
n
,
k
)
has
d
(
λ
(
n
)
)
values different from zero, where
d
computes the number of divisors.
g
(
n
,
1
)
=
1
g
(
4
,
2
)
=
1
g
(
2
n
,
2
)
=
3
for
n
≥
3
, since -1 is always a square root of 1.
g
(
2
n
,
2
k
)
=
2
k
for
k
∈
[
2
,
n
−
1
)
g
(
n
,
2
)
=
1
for
n
≥
3
and
n
in (sequence A033948 in the OEIS)
∑
k
∈
N
g
(
n
,
k
)
=
f
(
n
,
λ
(
n
)
)
=
φ
(
n
)
with
φ
being Euler's totient function
The connection between
f
and
g
can be written in an elegant way using a Dirichlet convolution:
You can compute values of
g
recursively from
f
using this formula, which is equivalent to the Möbius inversion formula.
By fast exponentiation you can check that
x
k
≡
1
(
mod
n
)
. 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
x
ℓ
≡
1
(
mod
n
)
. 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:
∀
p
prime dividing
k
,
x
k
/
p
≢
1
(
mod
n
)
.
Among the primitive k-th roots of unity, the primitive
λ
(
n
)
-th roots are most frequent. It is thus recommended to try some integers for being a primitive
λ
(
n
)
-th root, what will succeed quickly. For a primitive
λ
(
n
)
-th root x, the number
x
λ
(
n
)
/
k
is a primitive
k
-th root of unity. If k does not divide
λ
(
n
)
, then there will be no k-th roots of unity, at all.
Once you have a primitive k-th root of unity x, every power
x
l
is a
k
-th root of unity, but not necessarily a primitive one. The power
x
l
is a primitive
k
-th root of unity if and only if
k
and
l
are coprime. The proof is as follows: If
x
l
is not primitive, then there exists a divisor
m
of
k
with
(
x
l
)
m
≡
1
(
mod
n
)
, and since
k
and
l
are coprime, there exists an inverse
l
−
1
of
l
modulo
k
. This yields
1
≡
(
(
x
l
)
m
)
l
−
l
≡
x
m
(
mod
n
)
, which means that
x
is not a primitive
k
-th root of unity because there is the smaller exponent
m
.
That is, by exponentiating x one can obtain
φ
(
k
)
different primitive k-th roots of unity, but these may not be all such roots. However, finding all of them is not so easy.
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
k
-dimensional integer vector. In order to perform the inverse transform, you also need to divide by
k
, that is, k shall also be a unit modulo
n
.
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
k
+
1
,
2
k
+
1
,
3
k
+
1
,
…
. 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
p
it holds
λ
(
p
)
=
p
−
1
. Thus if
m
k
+
1
is prime then
λ
(
m
k
+
1
)
=
m
k
and thus you have primitive k-th roots of unity. But the test for primes is too strong, you may find other appropriate moduli.
If you want to have a modulus
n
such that there are primitive
k
1
-th,
k
2
-th, ...,
k
m
-th roots of unity modulo
n
, the following theorem reduces the problem to a simpler one:
For given
n
there are primitive
k
1
-th, ...,
k
m
-th roots of unity modulo
n
if and only if there is a primitive
l
c
m
(
k
1
,
.
.
.
,
k
m
)
-th root of unity modulo
n.
Proof
Backward direction: If there is a primitive
l
c
m
(
k
1
,
.
.
.
,
k
m
)
-th root of unity modulo
n
called
x
, then
x
l
c
m
(
k
1
,
…
,
k
m
)
/
k
l
is a
k
l
-th root of unity modulo
n
.
Forward direction: If there are primitive
k
1
-th, ...,
k
m
-th roots of unity modulo
n
, then all exponents
k
1
,
…
,
k
m
are divisors of
λ
(
n
)
. This implies
l
c
m
(
k
1
,
…
,
k
m
)
∣
λ
(
n
)
and this in turn means there is a primitive
l
c
m
(
k
1
,
.
.
.
,
k
m
)
-th root of unity modulo
n
.
