# Root of unity modulo *n*

In mathematics, namely ring theory, a ** k-th root of unity modulo n** for positive integers

*k*,

*n*≥ 2, is a solution

*x*to the equation (or

*congruence*) . If

*k*is the smallest such exponent for

*x*, then

*x*is called a

**primitive**.

*k*-th root of unity modulo*n*^{[1]}See modular arithmetic for notation and terminology.

Do not confuse this with a primitive element modulo *n*, where the primitive element must generate all units of the residue class ring by exponentiation.
That is, there are always roots and primitive roots of unity modulo *n* for *n* ≥ 2, but for some *n* there is no primitive element modulo *n*. Being a root or a primitive root modulo *n* always depends on the exponent *k* and the modulus *n*, whereas being a primitive element modulo *n* only depends on the modulus *n* — the exponent is automatically .

## Roots of unity

### Properties

- If
*x*is a*k*-th root of unity, 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)*k*-th root of unity modulo*n*, where*k*is the multiplicative order of*x*modulo*n*. - If
*x*is a*k*-th root of unity and is not a zero divisor, then , because

### Number of *k*-th roots

For the lack of a widely accepted symbol, we denote the number of *k*-th 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 would be known, then together with the previous law it would yield a way to evaluate quickly.

## 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. You can obtain one by choosing a -th primitive root of unity (that must exist by definition of λ), named and compute the power .
- If
*x*is a primitive*k*-th 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 *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.
- for , since -1 is always a square root of 1.
- for
- for and in (sequence A033948 in OEIS)
- with being Euler's totient function
- The connection between and can be written in an elegant way using a Dirichlet convolution:

- You can compute values of recursively from 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 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 *k* divided 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.

### Finding multiple primitive *k*-th roots modulo *n*

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 (more precisely a Number theoretic 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:

- For given there are primitive -th, ..., -th 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 -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 .

## See also

## References

- ↑ {{#invoke:Citation/CS1|citation |CitationClass=journal }}