Root of unity modulo n

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

A [[primitive root modulo n|primitive root modulo Template:Mvar]], is a generator of the group of units of the ring of integers modulo Template:Mvar. There exist primitive roots modulo Template:Mvar if and only if $\lambda (n)=\phi (n),$ where $\lambda$ and $\phi$ are respectively the Carmichael function and Euler's totient function.

A root of unity modulo Template:Mvar is a primitive Template:Mvarth root of unity modulo Template:Mvar for some divisor Template:Mvar of $\lambda (n),$ and, conversely, there are primitive Template:Mvarth roots of unity modulo Template:Mvar if and only if Template:Mvar is a divisor of $\lambda (n).$

Roots of unity

Properties

• If x is a kth root of unity modulo n, 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) 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 $x-1$ is not a zero divisor, then $\sum _{j=0}^{k-1}{x}^j\equiv 0(\mathrm{mod}n)$, because

$(x-1)\cdot \sum _{j=0}^{k-1}{x}^j\equiv x^k-1\equiv 0(\mathrm{mod}n).$

Number of kth roots

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

• $f(n,1)=1$ for $n\ge 2$
• $f(n,\lambda (n))=\phi (n)$ where λ denotes the Carmichael function and $\phi$ denotes Euler's totient function
• $n\mapsto f(n,k)$ is a multiplicative function
• $k\mid \ell ⟹f(n,k)\mid f(n,\ell )$ 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$, $\mathrm{\forall }i\in \mathbb{N}\mathrm{\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.

Examples

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

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. One can obtain such a root 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 kth 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 $\gcd (k,\ell )$. Since k is minimal, it must be $k=\gcd (k,\ell )$ and $\gcd (k,\ell )$ is a divisor of ℓ.

Number of primitive kth roots

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

• $g(n,k)=\{\begin{array}{cc}>0& \text{if }k\mid \lambda (n),\\ 0& \text{otherwise}.\end{array}$
• 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 Template:OEIS
• $\sum _{k\in \mathbb{N}}g(n,k)=f(n,\lambda (n))=\phi (n)$ with $\phi$ being Euler's totient function
• The connection between $f$ and $g$ can be written in an elegant way using a Dirichlet convolution:

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

One 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 kth root of unity modulo n

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

That is, x is a primitive kth root of unity modulo n if and only if $x^k\equiv 1(\mathrm{mod}n)$ and $$x^{k/p}\equiv ̸1(\mathrm{mod}n)$$ for every prime divisor p of n.

For example, if $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 $$x^{16/2}\equiv ̸1(\mathrm{mod}17).$$

Finding a primitive kth root of unity modulo n

Among the primitive kth 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 kth roots of unity, at all.

Finding multiple primitive kth roots modulo n

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

$x^m\equiv (x^m{)}^{ak+b\ell }\equiv (x^k{)}^{ma}((x^{\ell }{)}^m{)}^b\equiv 1(\mathrm{mod}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 $\phi (k)$ different primitive kth 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 kth root of unity modulo n

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 $k$-dimensional integer vector. In order to perform the inverse transform, divide by $k$; that is, k is also a unit modulo $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 $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 there are primitive kth roots of unity. But the test for primes is too strong, and there may be other appropriate moduli.

Finding an n with multiple primitive roots of unity modulo n

To find a modulus $n$ such that there are primitive $k_1\text{th},k_2\text{th},\dots ,k_m\text{th}$ roots of unity modulo $n$, the following theorem reduces the problem to a simpler one:

For given $n$ there are primitive $k_1\text{th},\dots ,k_m\text{th}$ roots of unity modulo $n$ if and only if there is a primitive $\mathrm{lcm}(k_1,\dots ,k_m)$th root of unity modulo n.

Proof

Backward direction: If there is a primitive $\mathrm{lcm}(k_1,\dots ,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\text{th},\dots ,k_m\text{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,\dots ,k_m)$th root of unity modulo $n$.