Root of unity modulo n

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) [math]\displaystyle{ x^k \equiv 1 \pmod{n} }[/math]. If k is the smallest such exponent for x, then x is called a primitive kth root of unity modulo n. 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 [math]\displaystyle{ \lambda(n)=\varphi(n), }[/math] where [math]\displaystyle{ \lambda }[/math] and [math]\displaystyle{ \varphi }[/math] 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 [math]\displaystyle{ \lambda(n), }[/math] and, conversely, there are primitive kth roots of unity modulo n if and only if k is a divisor of [math]\displaystyle{ \lambda(n). }[/math]

Roots of unity

Properties

• If x is a kth root of unity modulo n, then x is a unit (invertible) whose inverse is [math]\displaystyle{ x^{k-1} }[/math]. 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 [math]\displaystyle{ x-1 }[/math] is not a zero divisor, then [math]\displaystyle{ \sum_{j=0}^{k-1} x^j \equiv 0 \pmod{n} }[/math], because

[math]\displaystyle{ (x-1)\cdot\sum_{j=0}^{k-1} x^j \equiv x^k-1 \equiv 0 \pmod{n}. }[/math]

Number of kth roots

For the lack of a widely accepted symbol, we denote the number of kth roots of unity modulo n by [math]\displaystyle{ f(n,k) }[/math]. It satisfies a number of properties:

• [math]\displaystyle{ f(n,1) = 1 }[/math] for [math]\displaystyle{ n\ge2 }[/math]
• [math]\displaystyle{ f(n,\lambda(n)) = \varphi(n) }[/math] where λ denotes the Carmichael function and [math]\displaystyle{ \varphi }[/math] denotes Euler's totient function
• [math]\displaystyle{ n \mapsto f(n,k) }[/math] is a multiplicative function
• [math]\displaystyle{ k\mid\ell \implies f(n,k)\mid f(n,\ell) }[/math] where the bar denotes divisibility
• [math]\displaystyle{ f(n,\operatorname{lcm}(a,b)) = \operatorname{lcm}(f(n,a),f(n,b)) }[/math] where [math]\displaystyle{ \operatorname{lcm} }[/math] denotes the least common multiple
• For prime [math]\displaystyle{ p }[/math], [math]\displaystyle{ \forall i\in\mathbb{N}\ \exists j\in\mathbb{N}\ f(n,p^i) = p^j }[/math]. The precise mapping from [math]\displaystyle{ i }[/math] to [math]\displaystyle{ j }[/math] is not known. If it were known, then together with the previous law it would yield a way to evaluate [math]\displaystyle{ f }[/math] quickly.

Examples

Let [math]\displaystyle{ n = 7 }[/math] and [math]\displaystyle{ k = 3 }[/math]. In this case, there are three cube roots of unity (1, 2, and 4). When [math]\displaystyle{ n = 11 }[/math] 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.

Primitive roots of unity

Properties

• The maximum possible radix exponent for primitive roots modulo [math]\displaystyle{ n }[/math] is [math]\displaystyle{ \lambda(n) }[/math], where λ denotes the Carmichael function.
• A radix exponent for a primitive root of unity is a divisor of [math]\displaystyle{ \lambda(n) }[/math].
• Every divisor [math]\displaystyle{ k }[/math] of [math]\displaystyle{ \lambda(n) }[/math] yields a primitive [math]\displaystyle{ k }[/math]th root of unity. One can obtain such a root by choosing a [math]\displaystyle{ \lambda(n) }[/math]th primitive root of unity (that must exist by definition of λ), named [math]\displaystyle{ x }[/math] and compute the power [math]\displaystyle{ x^{\lambda(n)/k} }[/math].
• 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 [math]\displaystyle{ \gcd(k,\ell) }[/math]. Since k is minimal, it must be [math]\displaystyle{ k = \gcd(k,\ell) }[/math] and [math]\displaystyle{ \gcd(k,\ell) }[/math] 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 [math]\displaystyle{ g(n,k) }[/math]. It satisfies the following properties:

• [math]\displaystyle{ g(n,k) = \begin{cases} \gt 0 &\text{if } k\mid\lambda(n), \\ 0 & \text{otherwise}. \end{cases} }[/math]
• Consequently the function [math]\displaystyle{ k \mapsto g(n,k) }[/math] has [math]\displaystyle{ d(\lambda(n)) }[/math] values different from zero, where [math]\displaystyle{ d }[/math] computes the number of divisors.
• [math]\displaystyle{ g(n,1) = 1 }[/math]
• [math]\displaystyle{ g(4,2) = 1 }[/math]
• [math]\displaystyle{ g(2^n,2) = 3 }[/math] for [math]\displaystyle{ n \ge 3 }[/math], since -1 is always a square root of 1.
• [math]\displaystyle{ g(2^n,2^k) = 2^k }[/math] for [math]\displaystyle{ k \in [2,n-1) }[/math]
• [math]\displaystyle{ g(n,2) = 1 }[/math] for [math]\displaystyle{ n \ge 3 }[/math] and [math]\displaystyle{ n }[/math] in (sequence A033948 in the OEIS)
• [math]\displaystyle{ \sum_{k\in\mathbb{N}} g(n,k) = f(n,\lambda(n)) = \varphi(n) }[/math] with [math]\displaystyle{ \varphi }[/math] being Euler's totient function
• The connection between [math]\displaystyle{ f }[/math] and [math]\displaystyle{ g }[/math] can be written in an elegant way using a Dirichlet convolution:

[math]\displaystyle{ f = \mathbf{1} * g }[/math], i.e. [math]\displaystyle{ f(n,k) = \sum_{d\mid k} g(n,d) }[/math]

One can compute values of [math]\displaystyle{ g }[/math] recursively from [math]\displaystyle{ f }[/math] 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 [math]\displaystyle{ x^k \equiv 1 \pmod{n} }[/math]. 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 [math]\displaystyle{ x^{\ell} \equiv 1 \pmod{n} }[/math]. 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:

[math]\displaystyle{ \forall p \text{ prime dividing}\ k,\quad x^{k/p} \not\equiv 1 \pmod{n}. }[/math]

Finding a primitive kth root of unity modulo n

Among the primitive kth roots of unity, the primitive [math]\displaystyle{ \lambda(n) }[/math]th roots are most frequent. It is thus recommended to try some integers for being a primitive [math]\displaystyle{ \lambda(n) }[/math]th root, what will succeed quickly. For a primitive [math]\displaystyle{ \lambda(n) }[/math]th root x, the number [math]\displaystyle{ x^{\lambda(n)/k} }[/math] is a primitive [math]\displaystyle{ k }[/math]th root of unity. If k does not divide [math]\displaystyle{ \lambda(n) }[/math], 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 [math]\displaystyle{ x^\ell }[/math] is a [math]\displaystyle{ k }[/math]th root of unity, but not necessarily a primitive one. The power [math]\displaystyle{ x^\ell }[/math] is a primitive [math]\displaystyle{ k }[/math]th root of unity if and only if [math]\displaystyle{ k }[/math] and [math]\displaystyle{ \ell }[/math] are coprime. The proof is as follows: If [math]\displaystyle{ x^\ell }[/math] is not primitive, then there exists a divisor [math]\displaystyle{ m }[/math] of [math]\displaystyle{ k }[/math] with [math]\displaystyle{ (x^\ell)^m \equiv 1 \pmod n }[/math], and since [math]\displaystyle{ k }[/math] and [math]\displaystyle{ \ell }[/math] are coprime, there exists an inverse [math]\displaystyle{ \ell^{-1} }[/math] of [math]\displaystyle{ \ell }[/math] modulo [math]\displaystyle{ k }[/math]. This yields [math]\displaystyle{ 1 \equiv ((x^\ell)^m)^{\ell^{-\ell}} \equiv x^m \pmod n }[/math], which means that [math]\displaystyle{ x }[/math] is not a primitive [math]\displaystyle{ k }[/math]th root of unity because there is the smaller exponent [math]\displaystyle{ m }[/math].

That is, by exponentiating x one can obtain [math]\displaystyle{ \varphi(k) }[/math] 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 [math]\displaystyle{ k }[/math]-dimensional integer vector. In order to perform the inverse transform, divide by [math]\displaystyle{ k }[/math]; that is, k is also a unit modulo [math]\displaystyle{ n. }[/math]

A simple way to find such an n is to check for primitive kth roots with respect to the moduli in the arithmetic progression [math]\displaystyle{ k+1, 2k+1, 3k+1, \dots }[/math] 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 [math]\displaystyle{ p }[/math], it holds [math]\displaystyle{ \lambda(p) = p-1 }[/math]. Thus if [math]\displaystyle{ mk+1 }[/math] is prime, then [math]\displaystyle{ \lambda(mk+1) = mk }[/math], 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 [math]\displaystyle{ n }[/math] such that there are primitive [math]\displaystyle{ k_1\text{th}, k_2\text{th},\ldots,k_m\text{th} }[/math] roots of unity modulo [math]\displaystyle{ n }[/math], the following theorem reduces the problem to a simpler one:

For given [math]\displaystyle{ n }[/math] there are primitive [math]\displaystyle{ k_1\text{th}, \ldots, k_m\text{th} }[/math] roots of unity modulo [math]\displaystyle{ n }[/math] if and only if there is a primitive [math]\displaystyle{ \operatorname{lcm}(k_1, \ldots, k_m) }[/math]th root of unity modulo n.

Proof

Backward direction: If there is a primitive [math]\displaystyle{ \operatorname{lcm}(k_1, \ldots, k_m) }[/math]th root of unity modulo [math]\displaystyle{ n }[/math] called [math]\displaystyle{ x }[/math], then [math]\displaystyle{ x^{\operatorname{lcm}(k_1, \ldots, k_m)/k_l} }[/math] is a [math]\displaystyle{ k_l }[/math]th root of unity modulo [math]\displaystyle{ n }[/math].

Forward direction: If there are primitive [math]\displaystyle{ k_1\text{th}, \ldots, k_m\text{th} }[/math] roots of unity modulo [math]\displaystyle{ n }[/math], then all exponents [math]\displaystyle{ k_1, \dots, k_m }[/math] are divisors of [math]\displaystyle{ \lambda(n) }[/math]. This implies [math]\displaystyle{ \operatorname{lcm}(k_1, \dots, k_m) \mid \lambda(n) }[/math] and this in turn means there is a primitive [math]\displaystyle{ \operatorname{lcm}(k_1, \ldots, k_m) }[/math]th root of unity modulo [math]\displaystyle{ n }[/math].