Root of unity modulo n explained

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)

x ^{k} \equiv 1 \pmod{n} . 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 are exactly the integers that are coprime with . In fact, these integers are roots of unity modulo by Euler's theorem, and the other integers cannot be roots of unity modulo, because they are zero divisors modulo .

A primitive root modulo , is a generator of the group of units of the ring of integers modulo . There exist primitive roots modulo if and only if

λ (n) = \varphi(n), where λ and \varphi are respectively the Carmichael function and Euler's totient function.

A root of unity modulo is a primitive th root of unity modulo for some divisor of

λ (n), and, conversely, there are primitive th roots of unity modulo if and only if is a divisor of λ (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 ^{k -1} _{j =0} x ^{j} \equiv 0 \pmod{n} , because(x -1 ) ⋅ \sum ^{k -1} _{j =0} x ^{j} \equiv x ^{k-1} \equiv 0 \pmod{n}.

Number of kth 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\ge 2 f(n, λ (n)) = \varphi(n) where λ denotes the Carmichael function and \varphi denotes Euler's totient functionn \mapsto f(n,k) is a multiplicative functionk\mid\ell \implies f(n,k)\mid f(n,\ell) where the bar denotes divisibilityf(n,\operatorname{lcm}(a,b)) = \operatorname{lcm}(f(n,a),f(n,b)) where \operatorname{lcm} denotes the least common multiplep , \forall i\in N \exists j\in 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 λ (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. One can obtain such a root 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 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 ℓ.

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

g(n,k) .It satisfies the following properties:g(n,k) = \begin{cases} > 0 & if k\mid λ (n), \ 0 & otherwise . \end{cases}

• Consequently the function

k \mapsto 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 \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\inN} g(n,k) = f(n, λ (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 = 1 * g , i.e. f(n,k) = \sum _{d\mid} 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 kth 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, what needs to be checked is:\forall p primedividing k, x ^{k/p} \not\equiv 1 \pmod{n}.

Finding a primitive kth root of unity modulo n

Among the primitive kth 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 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

x ^{\ell} is a k th root of unity, but not necessarily a primitive one. The power x ^{\ell} is a primitive k th 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 k th 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 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

k -dimensional integer vector. In order to perform the inverse transform, divide by k ; that is, k is also a unit modulo n. 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 mk +1 is prime, then λ (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 _{1th,} k _{2th,\ldots,k} _{mth} roots of unity modulo n , the following theorem reduces the problem to a simpler one:

For given

n there are primitive k _{1th,} \ldots, k _{mth} 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 _{l} th root of unity modulo n .

Forward direction:If there are primitive

k _{1th,} \ldots, k _{mth} roots of unity modulo n , then all exponents k _{1,} ... , k _{m} are divisors of λ (n) . This implies \operatorname{lcm}(k _{1,} ... , k _{m)} \mid λ (n) and this in turn means there is a primitive \operatorname{lcm}(k _{1,} \ldots, k _{m)} th root of unity modulo n .

Notes and References

1. Finch . Stephen . Martin . Greg . Sebah . Pascal . Roots of unity and nullity modulo n . . 138 . 8 . 2729–2743 . 2011-02-20 . 10.1090/s0002-9939-10-10341-4. 2010 . free .