# 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) $x^{k}\equiv 1{\pmod {n}}$ . If k is the smallest such exponent for x, then x is called a primitive k-th root of unity modulo n. 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 $\mathbb {Z} /n\mathbb {Z}$ 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 $\varphi (n)$ .

## Roots of unity

### Properties

$(x-1)\cdot \sum _{j=0}^{k-1}x^{j}\equiv x^{k}-1\equiv 0{\pmod {n}}.$ ### 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 $f(n,k)$ . It satisfies a number of properties:

## Primitive roots of unity

### 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 $g(n,k)$ . It satisfies the following properties:

$f={\mathbf {1}}*g$ , i.e. $f(n,k)=\sum _{d\mid k}g(n,d)$ You 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 k-th root of unity modulo n

By fast exponentiation you can check that $x^{k}\equiv 1{\pmod {n}}$ . 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 $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{\text{ prime dividing}}\ k,\quad x^{k/p}\not \equiv 1{\pmod {n}}.$ ### Finding a primitive k-th root of unity modulo n

Among the primitive k-th roots of unity, the primitive $\lambda (n)$ -th roots are most frequent. It is thus recommended to try some integers for being a primitive $\lambda (n)$ -th root, what will succeed quickly. For a primitive $\lambda (n)$ -th root x, the number $x^{\lambda (n)/k}$ is a primitive $k$ -th root of unity. If k does not divide $\lambda (n)$ , then there will be no k-th roots of unity, at all.

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

That is, by exponentiating x one can obtain $\varphi (k)$ 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 $k$ -dimensional integer vector. In order to perform the inverse transform, you also need to divide by $k$ , that is, k shall also be a unit modulo $n$ .

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 $k+1,2k+1,3k+1,\dots$ . 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 $\lambda (p)=p-1$ . Thus if $mk+1$ is prime then $\lambda (mk+1)=mk$ 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

For given $n$ there are primitive $k_{1}$ -th, ..., $k_{m}$ -th roots of unity modulo $n$ if and only if there is a primitive $\mathrm {lcm} (k_{1},...,k_{m})$ -th root of unity modulo n.
Proof