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 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 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, which is a generator of the group of units of the ring of integers modulo n. The primitive roots modulo n are the primitive ${\displaystyle \varphi (n)}$-roots of unity modulo n, where ${\displaystyle \varphi }$ is Euler's totient function.

Roots of unity

Properties

• If x is a k-th root of unity modulo n, then x is a unit (invertible) whose inverse is ${\displaystyle 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 ${\displaystyle x-1}$ is not a zero divisor, then ${\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}}.}$

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 ${\displaystyle f(n,k)}$. It satisfies a number of properties:

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

Primitive roots of unity

Properties

• The maximum possible radix exponent for primitive roots modulo ${\displaystyle n}$ is ${\displaystyle \lambda (n)}$, where λ denotes the Carmichael function.
• A radix exponent for a primitive root of unity is a divisor of ${\displaystyle \lambda (n)}$.
• Every divisor ${\displaystyle k}$ of ${\displaystyle \lambda (n)}$ yields a primitive ${\displaystyle k}$-th root of unity. You can obtain one by choosing a ${\displaystyle \lambda (n)}$-th primitive root of unity (that must exist by definition of λ), named ${\displaystyle x}$ and compute the power ${\displaystyle 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 ${\displaystyle \mathrm {gcd} (k,\ell )}$. Since k is minimal, it must be ${\displaystyle k=\mathrm {gcd} (k,\ell )}$ and ${\displaystyle \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 ${\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}}}$
• Consequently the function ${\displaystyle k\mapsto g(n,k)}$ has ${\displaystyle d(\lambda (n))}$ values different from zero, where ${\displaystyle d}$ computes the number of divisors.
• ${\displaystyle g(n,1)=1}$
• ${\displaystyle g(4,2)=1}$
• ${\displaystyle g(2^{n},2)=3}$ for ${\displaystyle n\geq 3}$, since -1 is always a square root of 1.
• ${\displaystyle g(2^{n},2^{k})=2^{k}}$ for ${\displaystyle k\in [2,n-1)}$
• ${\displaystyle g(n,2)=1}$ for ${\displaystyle n\geq 3}$ and ${\displaystyle n}$ in (sequence A033948 in the OEIS)
• ${\displaystyle \sum _{k\in \mathbb {N} }g(n,k)=f(n,\lambda (n))=\varphi (n)}$ with ${\displaystyle \varphi }$ being Euler's totient function
• The connection between ${\displaystyle f}$ and ${\displaystyle g}$ can be written in an elegant way using a Dirichlet convolution:

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

You can compute values of ${\displaystyle g}$ recursively from ${\displaystyle 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 ${\displaystyle 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 ${\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. That is, what needs to be checked is:

${\displaystyle \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 ${\displaystyle \lambda (n)}$-th roots are most frequent. It is thus recommended to try some integers for being a primitive ${\displaystyle \lambda (n)}$-th root, what will succeed quickly. For a primitive ${\displaystyle \lambda (n)}$-th root x, the number ${\displaystyle x^{\lambda (n)/k}}$ is a primitive ${\displaystyle k}$-th root of unity. If k does not divide ${\displaystyle \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 ${\displaystyle x^{l}}$ is a ${\displaystyle k}$-th root of unity, but not necessarily a primitive one. The power ${\displaystyle x^{l}}$ is a primitive ${\displaystyle k}$-th root of unity if and only if ${\displaystyle k}$ and ${\displaystyle l}$ are coprime. The proof is as follows: If ${\displaystyle x^{l}}$ is not primitive, then there exists a divisor ${\displaystyle m}$ of ${\displaystyle k}$ with ${\displaystyle (x^{l})^{m}\equiv 1{\pmod {n}}}$, and since ${\displaystyle k}$ and ${\displaystyle l}$ are coprime, there exists an inverse ${\displaystyle l^{-1}}$ of ${\displaystyle l}$ modulo ${\displaystyle k}$. This yields ${\displaystyle 1\equiv ((x^{l})^{m})^{l^{-l}}\equiv x^{m}{\pmod {n}}}$, which means that ${\displaystyle x}$ is not a primitive ${\displaystyle k}$-th root of unity because there is the smaller exponent ${\displaystyle m}$.

That is, by exponentiating x one can obtain ${\displaystyle \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 ${\displaystyle k}$-dimensional integer vector. In order to perform the inverse transform, you also need to divide by ${\displaystyle k}$, that is, k shall also be a unit modulo ${\displaystyle 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 ${\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}$ it holds ${\displaystyle \lambda (p)=p-1}$. Thus if ${\displaystyle mk+1}$ is prime then ${\displaystyle \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 ${\displaystyle n}$ such that there are primitive ${\displaystyle k_{1}}$-th, ${\displaystyle k_{2}}$-th, ..., ${\displaystyle k_{m}}$-th roots of unity modulo ${\displaystyle n}$, the following theorem reduces the problem to a simpler one:

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

Proof

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

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

References

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