Root of unity modulo n

Roots of unity

Properties

• If x is a kth root of unity modulo n, 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) 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 x-1 is not a zero divisor, then \sum_{j=0}^{k-1} x^j \equiv 0 \pmod{n}, because :: (x-1)\cdot\sum_{j=0}^{k-1} x^j \equiv x^k-1 \equiv 0 \pmod{n}.

Number of ''k''th roots

For the lack of a widely accepted symbol, we denote the number of kth roots of unity modulo n by f(n,k). It satisfies a number of properties:

• f(n,1) = 1 for n\ge2
• f(n,\lambda(n)) = \varphi(n) where λ denotes the Carmichael function and \varphi denotes Euler's totient function
• n \mapsto f(n,k) is a multiplicative function
• k\mid\ell \implies f(n,k)\mid f(n,\ell) where the bar denotes divisibility
• f(n,\operatorname{lcm}(a,b)) = \operatorname{lcm}(f(n,a),f(n,b)) where \operatorname{lcm} denotes the least common multiple
• For prime p, \forall i\in\mathbb{N}\ \exists j\in\mathbb{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.

Examples

Let n = 7 and k = 3 . In this case, there are three cube roots of unity (1, 2, and 4). When n = 11 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 n is \lambda(n), where λ denotes the Carmichael function.
• A radix exponent for a primitive root of unity is a divisor of \lambda(n).
• Every divisor k of \lambda(n) yields a primitive kth root of unity. One can obtain such a root by choosing a \lambda(n)th primitive root of unity (that must exist by definition of λ), named x and compute the power x^{\lambda(n)/k}.
• 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 \gcd(k,\ell). Since k is minimal, it must be k = \gcd(k,\ell) and \gcd(k,\ell) is a divisor of ℓ.
• If x is a primitive kth root of unity and for another exponent l it holds x^l \equiv 1 \pmod{n}, then k is a divisor of l. --

Number of primitive ''k''th roots

For the lack of a widely accepted symbol, we denote the number of primitive kth roots of unity modulo n by g(n,k). It satisfies the following properties:

• g(n,k) = \begin{cases} 0 &\text{if } k\mid\lambda(n), \ 0 & \text{otherwise}. \end{cases}
• Consequently the function k \mapsto g(n,k) has d(\lambda(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 \ge 3, since -1 is always a square root of 1.
• g(2^n,2^k) = 2^k for k \in 2,n-1)
• g(n,2) = 1 for n \ge 3 and n in
• \sum_{k\in\mathbb{N}} g(n,k) = f(n,\lambda(n)) = \varphi(n) with \varphi being [Euler's totient function
• The connection between f and g can be written in an elegant way using a Dirichlet convolution: :: f = \mathbf{1} * g, i.e. f(n,k) = \sum_{d\mid k} g(n,d) : One can compute values of g recursively from f 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, one can check that x^k \equiv 1 \pmod{n}. 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 x^{\ell} \equiv 1 \pmod{n}. In order to exclude this possibility, one has only to check for a few ℓ's equal k divided by a prime.

That is, x is a primitive kth root of unity modulo n if and only if x^k \equiv 1 \pmod{n} and x^{k/p} \not\equiv 1 \pmod{n} for every prime divisor p of n.

For example, if n=17, every positive integer less than 17 is a 16th root of unity modulo 17, and the integers that are primitive 16th roots of unity modulo 17 are exactly those such that x^{16/2} \not\equiv 1 \pmod{17}.

Finding a primitive ''k''th root of unity modulo ''n''

Among the primitive kth roots of unity, the primitive \lambda(n)th roots are most frequent. It is thus recommended to try some integers for being a primitive \lambda(n)th root, what will succeed quickly. For a primitive \lambda(n)th root x, the number x^{\lambda(n)/k} is a primitive kth root of unity. If k does not divide \lambda(n), then there will be no kth roots of unity, at all.

Finding multiple primitive ''k''th roots modulo ''n''

Once a primitive kth root of unity x is obtained, every power x^\ell is a kth root of unity, but not necessarily a primitive one. The power x^\ell is a primitive kth root of unity if and only if k and \ell are coprime. The proof is as follows: If x^\ell is not primitive, then there exists a divisor m of k with (x^\ell)^m \equiv 1 \pmod n, and since k and \ell are coprime, there exists integers a,b such that ak+b\ell=1. This yields

x^m\equiv (x^m)^{ak+b\ell}\equiv (x^k)^{ma} ((x^{\ell})^m)^b \equiv 1 \pmod n ,

which means that x is not a primitive kth root of unity because there is the smaller exponent m.

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

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

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

; Proof

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

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

References