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. 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  where  and  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  and, conversely, there are primitive th roots of unity modulo  if and only if  is a divisor of

Roots of unity

Properties 
 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 
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 
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

Properties 
 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 
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 
  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 
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 
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 
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 an inverse  of  modulo . 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 
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 
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 

Modular arithmetic