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) ${\displaystyle x^{k}\equiv 1{\pmod {n}}}$. 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 n are exactly the integers that are coprime with n. In fact, these integers are roots of unity modulo n by Euler's theorem, and the other integers cannot be roots of unity modulo n, because they are zero divisors modulo n.

A primitive root modulo n, is a generator of the group of units of the ring of integers modulo n. There exist primitive roots modulo n if and only if ${\displaystyle \lambda (n)=\varphi (n),}$ where ${\displaystyle \lambda }$ and ${\displaystyle \varphi }$ are respectively the Carmichael function and Euler's totient function.^{[clarification needed]}

A root of unity modulo n is a primitive kth root of unity modulo n for some divisor k of ${\displaystyle \lambda (n),}$ and, conversely, there are primitive kth roots of unity modulo n if and only if k is a divisor of ${\displaystyle \lambda (n).}$

For the lack of a widely accepted symbol, we denote the number of kth roots of unity modulo n by ${\displaystyle f(n,k)}$. It satisfies a number of properties:

Let ${\displaystyle n=7}$ and ${\displaystyle k=3}$. In this case, there are three cube roots of unity (1, 2, and 4). When ${\displaystyle n=11}$ 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.

For the lack of a widely accepted symbol, we denote the number of primitive kth roots of unity modulo n by ${\displaystyle g(n,k)}$. It satisfies the following properties:

By fast exponentiation, one can check that ${\displaystyle x^{k}\equiv 1{\pmod {n}}}$. 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 ${\displaystyle 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.