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) . 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

Roots of unity

edit

Properties

edit
  • 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
 

Number of kth roots

edit

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  
  •   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.

Examples

edit

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.

Primitive roots of unity

edit

Properties

edit
  • 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

edit

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:

  •  
  • Consequently the function   has   values different from zero, where   computes the number of divisors.
  •  
  •  
  •   for  , since -1 is always a square root of 1.
  •   for  
  •   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.  
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

edit

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:

 

Finding a primitive kth root of unity modulo n

edit

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

edit

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

edit

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

edit

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  .

References

edit
  1. ^ Finch, Stephen; Martin, Greg; Sebah, Pascal (2010). "Roots of unity and nullity modulo n" (PDF). Proceedings of the American Mathematical Society. 138 (8): 2729–2743. doi:10.1090/s0002-9939-10-10341-4. Retrieved 2011-02-20.