Root of unity modulo n

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}}}${\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.^[1] 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),}${\displaystyle \lambda (n)=\varphi (n),} where ${\displaystyle \lambda }${\displaystyle \lambda } and ${\displaystyle \varphi }${\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),}${\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).}${\displaystyle \lambda (n).}

• If x is a kth root of unity modulo n, then x is a unit (invertible) whose inverse is ${\displaystyle x^{k-1}}${\displaystyle x^{k-1}}. That is, x and n are coprime.
• If x is a unit, then it is a (primitive) kth root of unity modulo n, where k is the multiplicative order of x modulo n.
• If x is a kth root of unity and ${\displaystyle x-1}${\displaystyle x-1} is not a zero divisor, then ${\displaystyle \sum _{j=0}^{k-1}x^{j}\equiv 0{\pmod {n}}}${\displaystyle \sum _{j=0}^{k-1}x^{j}\equiv 0{\pmod {n}}}, because

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

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

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

• The maximum possible radix exponent for primitive roots modulo ${\displaystyle n}${\displaystyle n} is ${\displaystyle \lambda (n)}${\displaystyle \lambda (n)}, where λ denotes the Carmichael function.
• A radix exponent for a primitive root of unity is a divisor of ${\displaystyle \lambda (n)}${\displaystyle \lambda (n)}.
• Every divisor ${\displaystyle k}${\displaystyle k} of ${\displaystyle \lambda (n)}${\displaystyle \lambda (n)} yields a primitive ${\displaystyle k}${\displaystyle k}th root of unity. One can obtain such a root by choosing a ${\displaystyle \lambda (n)}${\displaystyle \lambda (n)}th primitive root of unity (that must exist by definition of λ), named ${\displaystyle x}${\displaystyle x} and compute the power ${\displaystyle x^{\lambda (n)/k}}${\displaystyle x^{\lambda (n)/k}}.
• If x is a primitive kth root of unity and also a (not necessarily primitive) lth root of unity, then k is a divisor of l. This is true, because Bézout's identity yields an integer linear combination of k and l equal to ${\displaystyle \gcd(k,\ell )}${\displaystyle \gcd(k,\ell )}. Since k is minimal, it must be ${\displaystyle k=\gcd(k,\ell )}${\displaystyle k=\gcd(k,\ell )} and ${\displaystyle \gcd(k,\ell )}${\displaystyle \gcd(k,\ell )} is a divisor of l.

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

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

${\displaystyle f=\mathbf {1} *g}${\displaystyle f=\mathbf {1} *g}, i.e. ${\displaystyle f(n,k)=\sum _{d\mid k}g(n,d)}${\displaystyle f(n,k)=\sum _{d\mid k}g(n,d)}

One can compute values of ${\displaystyle g}${\displaystyle g} recursively from ${\displaystyle f}${\displaystyle f} using this formula, which is equivalent to the Möbius inversion formula.

By fast exponentiation, one can check that ${\displaystyle x^{k}\equiv 1{\pmod {n}}}${\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 l of k, with ${\displaystyle x^{\ell }\equiv 1{\pmod {n}}}${\displaystyle x^{\ell }\equiv 1{\pmod {n}}}. In order to exclude this possibility, one has only to check for a few l's equal k divided by a prime.

That is, x is a primitive kth root of unity modulo n if and only if ${\textstyle x^{k}\equiv 1{\pmod {n}}}${\textstyle x^{k}\equiv 1{\pmod {n}}} and $${\displaystyle x^{k/p}\not \equiv 1{\pmod {n}}}$${\displaystyle x^{k/p}\not \equiv 1{\pmod {n}}} for every prime divisor p of n.

For example, if ${\displaystyle n=17,}${\displaystyle n=17,} every positive integer less than 17 is a 16th root of unity modulo 17, and the integers that are primitive 16th roots of unity modulo 17 are exactly those such that $${\displaystyle x^{16/2}\not \equiv 1{\pmod {17}}.}$${\displaystyle x^{16/2}\not \equiv 1{\pmod {17}}.}

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

Once a primitive kth root of unity x is obtained, every power ${\displaystyle x^{\ell }}${\displaystyle x^{\ell }} is a ${\displaystyle k}${\displaystyle k}th root of unity, but not necessarily a primitive one. The power ${\displaystyle x^{\ell }}${\displaystyle x^{\ell }} is a primitive ${\displaystyle k}${\displaystyle k}th root of unity if and only if ${\displaystyle k}${\displaystyle k} and ${\displaystyle \ell }${\displaystyle \ell } are coprime. The proof is as follows: If ${\displaystyle x^{\ell }}${\displaystyle x^{\ell }} is not primitive, then there exists a divisor ${\displaystyle m}${\displaystyle m} of ${\displaystyle k}${\displaystyle k} with ${\displaystyle (x^{\ell })^{m}\equiv 1{\pmod {n}}}${\displaystyle (x^{\ell })^{m}\equiv 1{\pmod {n}}}, and since ${\displaystyle k}${\displaystyle k} and ${\displaystyle \ell }${\displaystyle \ell } are coprime, there exists integers ${\displaystyle a,b}${\displaystyle a,b} such that ${\displaystyle ak+b\ell =1}${\displaystyle ak+b\ell =1}. This yields

${\displaystyle x^{m}\equiv (x^{m})^{ak+b\ell }\equiv (x^{k})^{ma}((x^{\ell })^{m})^{b}\equiv 1{\pmod {n}}}${\displaystyle x^{m}\equiv (x^{m})^{ak+b\ell }\equiv (x^{k})^{ma}((x^{\ell })^{m})^{b}\equiv 1{\pmod {n}}},

which means that ${\displaystyle x}${\displaystyle x} is not a primitive ${\displaystyle k}${\displaystyle k}th root of unity because there is the smaller exponent ${\displaystyle m}${\displaystyle m}.

That is, by exponentiating x one can obtain ${\displaystyle \varphi (k)}${\displaystyle \varphi (k)} different primitive kth roots of unity, but these may not be all such roots. However, finding all of them is not so easy.

In what integer residue class rings does a primitive kth root of unity exist? It can be used to compute a discrete Fourier transform (more precisely a number theoretic transform) of a ${\displaystyle k}${\displaystyle k}-dimensional integer vector. In order to perform the inverse transform, divide by ${\displaystyle k}${\displaystyle k}; that is, k is also a unit modulo ${\displaystyle n.}${\displaystyle n.}

A simple way to find such an n is to check for primitive kth roots with respect to the moduli in the arithmetic progression ${\displaystyle k+1,2k+1,3k+1,\dots }${\displaystyle 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 ${\displaystyle p}${\displaystyle p}, it holds ${\displaystyle \lambda (p)=p-1}${\displaystyle \lambda (p)=p-1}. Thus if ${\displaystyle mk+1}${\displaystyle mk+1} is prime, then ${\displaystyle \lambda (mk+1)=mk}${\displaystyle \lambda (mk+1)=mk}, and thus there are primitive kth roots of unity. But the test for primes is too strong, and there may be other appropriate moduli.

To find a modulus ${\displaystyle n}${\displaystyle n} such that there are primitive ${\displaystyle k_{1}{\text{th}},k_{2}{\text{th}},\ldots ,k_{m}{\text{th}}}${\displaystyle k_{1}{\text{th}},k_{2}{\text{th}},\ldots ,k_{m}{\text{th}}} roots of unity modulo ${\displaystyle n}${\displaystyle n}, the following theorem reduces the problem to a simpler one:

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

Proof

Backward direction: If there is a primitive ${\displaystyle \operatorname {lcm} (k_{1},\ldots ,k_{m})}${\displaystyle \operatorname {lcm} (k_{1},\ldots ,k_{m})}th root of unity modulo ${\displaystyle n}${\displaystyle n} called ${\displaystyle x}${\displaystyle x}, then ${\displaystyle x^{\operatorname {lcm} (k_{1},\ldots ,k_{m})/k_{l}}}${\displaystyle x^{\operatorname {lcm} (k_{1},\ldots ,k_{m})/k_{l}}} is a ${\displaystyle k_{l}}${\displaystyle k_{l}}th root of unity modulo ${\displaystyle n}${\displaystyle n}.

Forward direction: If there are primitive ${\displaystyle k_{1}{\text{th}},\ldots ,k_{m}{\text{th}}}${\displaystyle k_{1}{\text{th}},\ldots ,k_{m}{\text{th}}} roots of unity modulo ${\displaystyle n}${\displaystyle n}, then all exponents ${\displaystyle k_{1},\dots ,k_{m}}${\displaystyle k_{1},\dots ,k_{m}} are divisors of ${\displaystyle \lambda (n)}${\displaystyle \lambda (n)}. This implies ${\displaystyle \operatorname {lcm} (k_{1},\dots ,k_{m})\mid \lambda (n)}${\displaystyle \operatorname {lcm} (k_{1},\dots ,k_{m})\mid \lambda (n)} and this in turn means there is a primitive ${\displaystyle \operatorname {lcm} (k_{1},\ldots ,k_{m})}${\displaystyle \operatorname {lcm} (k_{1},\ldots ,k_{m})}th root of unity modulo ${\displaystyle n}${\displaystyle n}.

• Modular arithmetic

• Articles needing cleanup from February 2023
• All pages needing cleanup
• Cleanup tagged articles with a reason field from February 2023
• Wikipedia pages needing cleanup from February 2023
• Wikipedia articles needing clarification from April 2025