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.^[1] See modular arithmetic for notation and terminology.

Do not confuse this with a Primitive root modulo n, where the primitive root 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 root modulo n. Being a root of unity or a primitive root of unity modulo n always depends on the exponent k and the modulus n, whereas being a primitive root modulo n only depends on the modulus n — the exponent is automatically $\varphi(n)$.

Roots of unity

Properties

• If x is a k-th root of unity, then x is a unit (invertible) whose inverse is $x^{k-1}$. 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 $x-1$ is not a zero divisor, then $\sum_{j=0}^{k-1} x^j \equiv 0 \pmod{n}$, because

$(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:

• $f(n,1) = 1$ for $n\ge2$
• $f(n,\lambda(n)) = \varphi(n)$ where λ denotes the Carmichael function and $\varphi$ denotes Euler's totient function
• $n \mapsto f(n,k)$ is a multiplicative function
• $k\mid l \implies f(n,k)\mid f(n,l)$ where the bar denotes divisibility
• $f(n,\mathrm{lcm}(a,b)) = \mathrm{lcm}(f(n,a),f(n,b))$ where $\mathrm{lcm}$ denotes the least common multiple
• For prime $p$, $\forall i\in\mathbb{N}\ \exists j\in\mathbb{N}\ f(n,p^i) = p^j$. The precise mapping from $i$ to $j$ is not known. If it were known, then together with the previous law it would yield a way to evaluate $f$ quickly.

Primitive roots of unity

Properties

• The maximum possible radix exponent for primitive roots modulo $n$ is $\lambda(n)$, where λ denotes the Carmichael function.
• A radix exponent for a primitive root of unity is a divisor of $\lambda(n)$.
• Every divisor $k$ of $\lambda(n)$ yields a primitive $k$-th root of unity. You can obtain one by choosing a $\lambda(n)$-th primitive root of unity (that must exist by definition of λ), named $x$ and compute the power $x^{\lambda(n)/k}$.
• 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 $\mathrm{gcd}(k,\ell)$. Since k is minimal, it must be $k = \mathrm{gcd}(k,\ell)$ and $\mathrm{gcd}(k,\ell)$ 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 $g(n,k)$. It satisfies the following properties:

• $g(n,k) = \begin{cases} >0 &\text{if } k\mid\lambda(n), \\ 0 & \text{otherwise}. \end{cases}$
• Consequently the function $k \mapsto g(n,k)$ has $d(\lambda(n))$ values different from zero, where $d$ computes the number of divisors.
• $g(n,1) = 1$
• $g(4,2) = 1$
• $g(2^n,2) = 3$ for $n \ge 3$, since -1 is always a square root of 1.
• $g(2^n,2^k) = 2^k$ for $k \in [2,n-1)$
• $g(n,2) = 1$ for $n \ge 3$ and $n$ in (sequence A033948 in OEIS)
• $\sum_{k\in\mathbb{N}} g(n,k) = f(n,\lambda(n)) = \varphi(n)$ with $\varphi$ being Euler's totient function
• The connection between $f$ and $g$ can be written in an elegant way using a Dirichlet convolution:

$f = \bold{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

Once you have a primitive k-th root of unity x, every power $x^l$ is a $k$-th root of unity, but not necessarily a primitive one. The power $x^l$ is a primitive $k$-th root of unity if and only if $k$ and $l$ are coprime. The proof is as follows: If $x^l$ is not primitive, then there exists a divisor $m$ of $k$ with $(x^l)^m \equiv 1 \pmod{n}$, and since $k$ and $l$ are coprime, there exists an inverse $l^{-1}$ of $l$ modulo $k$. This yields $1 \equiv ((x^l)^m)^{l^{-l}} \equiv x^m \pmod{n}$, which means that $x$ is not a primitive $k$-th root of unity because there is the smaller exponent $m$.

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

If you want to have a modulus $n$ such that there are primitive $k_1$-th, $k_2$-th, ..., $k_m$-th roots of unity modulo $n$, the following theorem reduces the problem to a simpler one:

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

Backward direction: If there is a primitive $\mathrm{lcm}(k_1, ..., k_m)$-th root of unity modulo $n$ called $x$, then $x^{\mathrm{lcm}(k_1, \dots, k_m)/k_l}$ is a $k_l$-th root of unity modulo $n$.

Forward direction: If there are primitive $k_1$-th, ..., $k_m$-th roots of unity modulo $n$, then all exponents $k_1, \dots, k_m$ are divisors of $\lambda(n)$. This implies $\mathrm{lcm}(k_1, \dots, k_m) \mid \lambda(n)$ and this in turn means there is a primitive $\mathrm{lcm}(k_1, ..., k_m)$-th root of unity modulo $n$.

See also

• Root of unity
• Primitive root modulo n

References

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