Root of unity modulo n

☆ Save On Wikipedia ↗

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 ≡ 1 ( mod n ) {\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 λ ( n ) = φ ( n ) , {\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.

A root of unity modulo n is a primitive kth root of unity modulo n for some divisor k of λ ( n ) , {\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 λ ( n ) . {\displaystyle \lambda (n).} {\displaystyle \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 {\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 x − 1 {\displaystyle x-1} {\displaystyle x-1} is not a zero divisor, then ∑ j = 0 k − 1 x j ≡ 0 ( mod n ) {\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
( x − 1 ) ⋅ ∑ j = 0 k − 1 x j ≡ x k − 1 ≡ 0 ( mod n ) . {\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}}.}

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

  • f ( n , 1 ) = 1 {\displaystyle f(n,1)=1} {\displaystyle f(n,1)=1} for n ≥ 2 {\displaystyle n\geq 2} {\displaystyle n\geq 2}
  • f ( n , λ ( n ) ) = φ ( n ) {\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
  • n ↦ f ( n , k ) {\displaystyle n\mapsto f(n,k)} {\displaystyle n\mapsto f(n,k)} is a multiplicative function
  • k ∣ ℓ ⟹ f ( n , k ) ∣ f ( n , ℓ ) {\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
  • f ( n , lcm ⁡ ( a , b ) ) = lcm ⁡ ( f ( n , a ) , f ( n , b ) ) {\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 lcm {\displaystyle \operatorname {lcm} } {\displaystyle \operatorname {lcm} } denotes the least common multiple
  • For prime p {\displaystyle p} {\displaystyle p}, ∀ i ∈ N   ∃ j ∈ N   f ( n , p i ) = p j {\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 i {\displaystyle i} {\displaystyle i} to j {\displaystyle j} {\displaystyle j} is not known. If it were known, then together with the previous law it would yield a way to evaluate f {\displaystyle f} {\displaystyle f} quickly.

Examples

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

Primitive roots of unity

Properties

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

  • g ( n , k ) = { > 0 if  k ∣ λ ( n ) , 0 otherwise . {\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 k ↦ g ( n , k ) {\displaystyle k\mapsto g(n,k)} {\displaystyle k\mapsto g(n,k)} has d ( λ ( n ) ) {\displaystyle d(\lambda (n))} {\displaystyle d(\lambda (n))} values different from zero, where d {\displaystyle d} {\displaystyle d} computes the number of divisors.
  • g ( n , 1 ) = 1 {\displaystyle g(n,1)=1} {\displaystyle g(n,1)=1}
  • g ( 4 , 2 ) = 1 {\displaystyle g(4,2)=1} {\displaystyle g(4,2)=1}
  • g ( 2 n , 2 ) = 3 {\displaystyle g(2^{n},2)=3} {\displaystyle g(2^{n},2)=3} for n ≥ 3 {\displaystyle n\geq 3} {\displaystyle n\geq 3}, since -1 is always a square root of 1.
  • g ( 2 n , 2 k ) = 2 k {\displaystyle g(2^{n},2^{k})=2^{k}} {\displaystyle g(2^{n},2^{k})=2^{k}} for k ∈ [ 2 , n − 1 ) {\displaystyle k\in [2,n-1)} {\displaystyle k\in [2,n-1)}
  • g ( n , 2 ) = 1 {\displaystyle g(n,2)=1} {\displaystyle g(n,2)=1} for n ≥ 3 {\displaystyle n\geq 3} {\displaystyle n\geq 3} and n {\displaystyle n} {\displaystyle n} in (sequence A033948 in the OEIS)
  • ∑ k ∈ N g ( n , k ) = f ( n , λ ( n ) ) = φ ( n ) {\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 f {\displaystyle f} {\displaystyle f} and g {\displaystyle g} {\displaystyle g} can be written in an elegant way using a Dirichlet convolution:
f = 1 ∗ g {\displaystyle f=\mathbf {1} *g} {\displaystyle f=\mathbf {1} *g}, i.e. f ( n , k ) = ∑ d ∣ k g ( n , d ) {\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 g {\displaystyle g} {\displaystyle g} recursively from f {\displaystyle f} {\displaystyle 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 ≡ 1 ( mod n ) {\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 ℓ of k, with x ℓ ≡ 1 ( mod n ) {\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 ℓ'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 ≡ 1 ( mod n ) {\textstyle x^{k}\equiv 1{\pmod {n}}} {\textstyle x^{k}\equiv 1{\pmod {n}}} and x k / p ≢ 1 ( mod n ) {\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 n = 17 , {\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 x 16 / 2 ≢ 1 ( mod 17 ) . {\displaystyle x^{16/2}\not \equiv 1{\pmod {17}}.} {\displaystyle x^{16/2}\not \equiv 1{\pmod {17}}.}

Finding a primitive kth root of unity modulo n

Among the primitive kth roots of unity, the primitive λ ( n ) {\displaystyle \lambda (n)} {\displaystyle \lambda (n)}th roots are most frequent. It is thus recommended to try some integers for being a primitive λ ( n ) {\displaystyle \lambda (n)} {\displaystyle \lambda (n)}th root, what will succeed quickly. For a primitive λ ( n ) {\displaystyle \lambda (n)} {\displaystyle \lambda (n)}th root x, the number x λ ( n ) / k {\displaystyle x^{\lambda (n)/k}} {\displaystyle x^{\lambda (n)/k}} is a primitive k {\displaystyle k} {\displaystyle k}th root of unity. If k does not divide λ ( n ) {\displaystyle \lambda (n)} {\displaystyle \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 ℓ {\displaystyle x^{\ell }} {\displaystyle x^{\ell }} is a k {\displaystyle k} {\displaystyle k}th root of unity, but not necessarily a primitive one. The power x ℓ {\displaystyle x^{\ell }} {\displaystyle x^{\ell }} is a primitive k {\displaystyle k} {\displaystyle k}th root of unity if and only if k {\displaystyle k} {\displaystyle k} and ℓ {\displaystyle \ell } {\displaystyle \ell } are coprime. The proof is as follows: If x ℓ {\displaystyle x^{\ell }} {\displaystyle x^{\ell }} is not primitive, then there exists a divisor m {\displaystyle m} {\displaystyle m} of k {\displaystyle k} {\displaystyle k} with ( x ℓ ) m ≡ 1 ( mod n ) {\displaystyle (x^{\ell })^{m}\equiv 1{\pmod {n}}} {\displaystyle (x^{\ell })^{m}\equiv 1{\pmod {n}}}, and since k {\displaystyle k} {\displaystyle k} and ℓ {\displaystyle \ell } {\displaystyle \ell } are coprime, there exists integers a , b {\displaystyle a,b} {\displaystyle a,b} such that a k + b ℓ = 1 {\displaystyle ak+b\ell =1} {\displaystyle ak+b\ell =1}. This yields

x m ≡ ( x m ) a k + b ℓ ≡ ( x k ) m a ( ( x ℓ ) m ) b ≡ 1 ( mod n ) {\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 x {\displaystyle x} {\displaystyle x} is not a primitive k {\displaystyle k} {\displaystyle k}th root of unity because there is the smaller exponent m {\displaystyle m} {\displaystyle m}.

That is, by exponentiating x one can obtain φ ( k ) {\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.

Finding an n with a primitive kth root of unity modulo n

A motivating question is, 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 {\displaystyle k} {\displaystyle k}-dimensional integer vector. In order to perform the inverse transform, divide by k {\displaystyle k} {\displaystyle k}; that is, k is also a unit modulo n . {\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 k + 1 , 2 k + 1 , 3 k + 1 , … {\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 p {\displaystyle p} {\displaystyle p}, it holds λ ( p ) = p − 1 {\displaystyle \lambda (p)=p-1} {\displaystyle \lambda (p)=p-1}. Thus if m k + 1 {\displaystyle mk+1} {\displaystyle mk+1} is prime, then λ ( m k + 1 ) = m k {\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.

Finding an n with multiple primitive roots of unity modulo n

To find a modulus n {\displaystyle n} {\displaystyle n} such that there are primitive k 1 th , k 2 th , … , k m th {\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 n {\displaystyle n} {\displaystyle n}, the following theorem reduces the problem to a simpler one:

For given n {\displaystyle n} {\displaystyle n} there are primitive k 1 th , … , k m th {\displaystyle k_{1}{\text{th}},\ldots ,k_{m}{\text{th}}} {\displaystyle k_{1}{\text{th}},\ldots ,k_{m}{\text{th}}} roots of unity modulo n {\displaystyle n} {\displaystyle n} if and only if there is a primitive lcm ⁡ ( k 1 , … , k m ) {\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 lcm ⁡ ( k 1 , … , k m ) {\displaystyle \operatorname {lcm} (k_{1},\ldots ,k_{m})} {\displaystyle \operatorname {lcm} (k_{1},\ldots ,k_{m})}th root of unity modulo n {\displaystyle n} {\displaystyle n} called x {\displaystyle x} {\displaystyle x}, then x lcm ⁡ ( k 1 , … , k m ) / k l {\displaystyle x^{\operatorname {lcm} (k_{1},\ldots ,k_{m})/k_{l}}} {\displaystyle x^{\operatorname {lcm} (k_{1},\ldots ,k_{m})/k_{l}}} is a k l {\displaystyle k_{l}} {\displaystyle k_{l}}th root of unity modulo n {\displaystyle n} {\displaystyle n}.

Forward direction: If there are primitive k 1 th , … , k m th {\displaystyle k_{1}{\text{th}},\ldots ,k_{m}{\text{th}}} {\displaystyle k_{1}{\text{th}},\ldots ,k_{m}{\text{th}}} roots of unity modulo n {\displaystyle n} {\displaystyle n}, then all exponents k 1 , … , k m {\displaystyle k_{1},\dots ,k_{m}} {\displaystyle k_{1},\dots ,k_{m}} are divisors of λ ( n ) {\displaystyle \lambda (n)} {\displaystyle \lambda (n)}. This implies lcm ⁡ ( k 1 , … , k m ) ∣ λ ( n ) {\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 lcm ⁡ ( k 1 , … , k m ) {\displaystyle \operatorname {lcm} (k_{1},\ldots ,k_{m})} {\displaystyle \operatorname {lcm} (k_{1},\ldots ,k_{m})}th root of unity modulo n {\displaystyle n} {\displaystyle n}.

References

  1. Finch, Stephen; Martin, Greg; Sebah, 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.