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 solution x to the equation (or congruence) $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, where the primitive root must generate all units of the residue class ring $\mathbb {Z} /n\mathbb {Z}$ by exponentiation. That is, there are always roots and primitive roots of unity modulo n for n ≥ 2, but for some n there is no primitive root modulo n. Being a root of unity or a primitive root of unity modulo n always depends on the exponent k and the modulus n, whereas being a primitive root modulo n only depends on the modulus n — the exponent is automatically $\varphi (n)$ .

Roots of unity

Properties

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

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

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

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. You can obtain one 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 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 ${\mathrm {gcd}}(k,\ell )$ . Since k is minimal, it must be $k={\mathrm {gcd}}(k,\ell )$ and ${\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 $g(n,k)$ . It satisfies the following properties:

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

f={\mathbf {1}}*g

, i.e.

f(n,k)=\sum _{{d\mid k}}g(n,d)

You 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 k-th root of unity modulo n

By fast exponentiation you can check that $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 $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:

\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 $\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 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 $x^{l}$ is a $k$ -th root of unity, but not necessarily a primitive one. The power $x^{l}$ is a primitive $k$ -th root of unity if and only if $k$ and $l$ are coprime. The proof is as follows: If $x^{l}$ is not primitive, then there exists a divisor $m$ of $k$ with $(x^{l})^{m}\equiv 1{\pmod {n}}$ , and since $k$ and $l$ are coprime, there exists an inverse $l^{{-1}}$ of $l$ modulo $k$ . This yields $1\equiv ((x^{l})^{m})^{{l^{{-l}}}}\equiv x^{m}{\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 $\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 $k$ -dimensional integer vector. In order to perform the inverse transform, you also need to divide by $k$ , that is, k shall also be a unit modulo $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 $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 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 $n$ such that there are primitive $k_{1}$ -th, $k_{2}$ -th, ..., $k_{m}$ -th roots of unity modulo $n$ , the following theorem reduces the problem to a simpler one:

For given

n

there are primitive

k_{1}

-th, ...,

k_{m}

-th roots of unity modulo

n

if and only if there is a primitive

{\mathrm {lcm}}(k_{1},...,k_{m})

-th root of unity modulo n.

Proof

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

References

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

This article is issued from Wikipedia - version of the 1/19/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Root of unity modulo n

Roots of unity

Properties

Number of k-th roots

Primitive roots of unity

Properties

Number of primitive k-th roots

Testing whether x is a primitive k-th root of unity modulo n

Finding a primitive k-th root of unity modulo n

Finding multiple primitive k-th roots modulo n

Finding an n with a primitive k-th root of unity modulo n

Finding an n with multiple primitive roots of unity modulo n

See also

References