Root of unity modulo n

• 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 $\backslash sum\_\{j=0\}^\{k-1\}\; x^j\; \backslash equiv\; 0\; \backslash pmod\{n\}$, because

:: $(x-1)\backslash cdot\backslash sum\_\{j=0\}^\{k-1\}\; x^j\; \backslash equiv\; x^k-1\; \backslash equiv\; 0\; \backslash pmod\{n\}.$

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\backslash ge2$
• $f(n,\backslash lambda(n))\; =\; \backslash varphi(n)$ where λ denotes the Carmichael function and $\backslash varphi$ denotes Euler's totient function
• $n\; \backslash mapsto\; f(n,k)$ is a multiplicative function
• $k\backslash mid\backslash ell\; \backslash implies\; f(n,k)\backslash mid\; f(n,\backslash ell)$ where the bar denotes divisibility
• $f(n,\backslash operatorname\{lcm\}(a,b))\; =\; \backslash operatorname\{lcm\}(f(n,a),f(n,b))$ where $\backslash operatorname\{lcm\}$ denotes the least common multiple
• For prime $p$, $\backslash forall\; i\backslash in\backslash mathbb\{N\}\backslash \; \backslash exists\; j\backslash in\backslash mathbb\{N\}\backslash \; 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.

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.

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

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:

• Consequently the function $k\; \backslash mapsto\; g(n,k)$ has $d(\backslash 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\; \backslash ge\; 3$, since -1 is always a square root of 1.
• $g(2^n,2^k)\; =\; 2^k$ for $k\; \backslash in\; [2,n-1)$
• $g(n,2)\; =\; 1$ for $n\; \backslash ge\; 3$ and $n$ in {{OEIS|A033948}}
• $\backslash sum\_\{k\backslash in\backslash mathbb\{N\}\}\; g(n,k)\; =\; f(n,\backslash lambda(n))\; =\; \backslash varphi(n)$ with $\backslash varphi$ being Euler's totient function
• The connection between $f$ and $g$ can be written in an elegant way using a Dirichlet convolution:

:: $f\; =\; \backslash mathbf\{1\}\; *\; g$, i.e. $f(n,k)\; =\; \backslash sum\_\{d\backslash 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.

By fast exponentiation, one can check that $x^k\; \backslash equiv\; 1\; \backslash 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 $x^\{\backslash ell\}\; \backslash equiv\; 1\; \backslash 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, x is a primitive kth root of unity modulo n if and only if $x^k\; \backslash equiv\; 1\; \backslash pmod\{n\}$ and

$$x^\{k/p\}\; \backslash not\backslash equiv\; 1\; \backslash pmod\{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\}\; \backslash not\backslash equiv\; 1\; \backslash pmod\{17\}.$$

Among the primitive kth roots of unity, the primitive $\backslash lambda(n)$th roots are most frequent.

It is thus recommended to try some integers for being a primitive $\backslash lambda(n)$th root, what will succeed quickly.

For a primitive $\backslash lambda(n)$th root x, the number $x^\{\backslash lambda(n)/k\}$ is a primitive $k$th root of unity.

If k does not divide $\backslash 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 $x^\backslash ell$ is a $k$th root of unity, but not necessarily a primitive one. The power $x^\backslash ell$ is a primitive $k$th root of unity if and only if $k$ and $\backslash ell$ are coprime. The proof is as follows: If $x^\backslash ell$ is not primitive, then there exists a divisor $m$ of $k$ with $(x^\backslash ell)^m\; \backslash equiv\; 1\; \backslash pmod\; n$, and since $k$ and $\backslash ell$ are coprime, there exists integers $a,b$ such that $ak+b\backslash ell=1$. This yields

$x^m\backslash equiv\; (x^m)^\{ak+b\backslash ell\}\backslash equiv\; (x^k)^\{ma\}\; ((x^\{\backslash ell\})^m)^b\; \backslash equiv\; 1\; \backslash 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 $\backslash 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 $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,\; \backslash 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 $\backslash lambda(p)\; =\; p-1$. Thus if $mk+1$ is prime, then $\backslash 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 $n$ such that there are primitive $k\_1\backslash text\{th\},\; k\_2\backslash text\{th\},\backslash ldots,k\_m\backslash 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\backslash text\{th\},\; \backslash ldots,\; k\_m\backslash text\{th\}$ roots of unity modulo $n$ if and only if there is a primitive $\backslash operatorname\{lcm\}(k\_1,\; \backslash ldots,\; k\_m)$th root of unity modulo n.

; Proof

Backward direction:

If there is a primitive $\backslash operatorname\{lcm\}(k\_1,\; \backslash ldots,\; k\_m)$th root of unity modulo $n$ called $x$, then $x^\{\backslash operatorname\{lcm\}(k\_1,\; \backslash ldots,\; k\_m)/k\_l\}$ is a $k\_l$th root of unity modulo $n$.

Forward direction:

If there are primitive $k\_1\backslash text\{th\},\; \backslash ldots,\; k\_m\backslash text\{th\}$ roots of unity modulo $n$, then all exponents $k\_1,\; \backslash dots,\; k\_m$ are divisors of $\backslash lambda(n)$. This implies $\backslash operatorname\{lcm\}(k\_1,\; \backslash dots,\; k\_m)\; \backslash mid\; \backslash lambda(n)$ and this in turn means there is a primitive $\backslash operatorname\{lcm\}(k\_1,\; \backslash ldots,\; k\_m)$th root of unity modulo $n$.

{{reflist}}

Category:Modular arithmetic