Every divisor of yields a primitive -th root of unity. You can obtain one by choosing a -th primitive root of unity, named and compute the power.
If x is a primitive k-th root of unity and also a ℓ-th root of unity, then k is a divisor of ℓ. This is true, because Bézout's identity yields an integerlinear combination of k and ℓ equal to. Since k is minimal, it must be and is a divisor of ℓ.
Number of primitive ''k''-th roots
For the lack of a widely accepted symbol, we denote the number of primitive k-th 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.
The connection between and can be written in an elegant way using a Dirichlet convolution:
Testing whether ''x'' is a primitive ''k''-th root of unity modulo ''n''
By fast exponentiation you can check that. If this is true, x is a k-th 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 kdivided by a prime. That is, what needs to be checked is:
Finding a primitive ''k''-th root of unity modulo ''n''
Among the primitive k-th 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 k-th roots of unity, at all.
Once you have a primitive k-th root of unity x, 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 k-th 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''
You may want to know, in what integer residue class rings you have a primitive k-th root of unity. You need it for instance if you want to compute a Discrete Fourier Transform of a -dimensional integer vector. In order to perform the inverse transform, you also need to divide by, that is, k shall also be a unit modulo A simple way to find such an n is to check for primitive k-th 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 you have primitive k-th roots of unity. But the test for primes is too strong, you may find other appropriate moduli.
Finding an ''n'' with multiple primitive roots of unity modulo ''n''
If you want to have a modulus such that there are primitive -th, -th,..., -th roots of unity modulo, the following theorem reduces the problem to a simpler one: ; 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 -th,..., -th 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.
