Root of unity modulo n

This article may require cleanup to meet Wikipedia's quality standards. The specific problem is: Lack of context, lack of explicit examples, lack of explanation of the main differences with Root of unity and Finite field § Roots of unity. Please help improve this article if you can. (February 2023) (Learn how and when to remove this message)

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}}} . 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),} where λ {\displaystyle \lambda } and φ {\displaystyle \varphi } are respectively the Carmichael function and Euler's totient function.^{[clarification needed]}

A root of unity modulo n is a primitive kth root of unity modulo n for some divisor k of λ ( 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).}

• 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}} . 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} 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}}} , 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}}.}

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)} . It satisfies a number of properties:

• f ( n , 1 ) = 1 {\displaystyle f(n,1)=1} for n ≥ 2 {\displaystyle n\geq 2}
• f ( n , λ ( n ) ) = φ ( n ) {\displaystyle f(n,\lambda (n))=\varphi (n)} where λ denotes the Carmichael function and φ {\displaystyle \varphi } denotes Euler's totient function
• n ↦ 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 )} 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))} where lcm {\displaystyle \operatorname {lcm} } denotes the least common multiple
• For prime 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}} . The precise mapping from i {\displaystyle i} to 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} quickly.

Let n = 7 {\displaystyle n=7} and 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} 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 {\displaystyle n} is λ ( 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)} .
• Every divisor k {\displaystyle k} of λ ( n ) {\displaystyle \lambda (n)} yields a primitive k {\displaystyle k} th root of unity. One can obtain such a root by choosing a λ ( n ) {\displaystyle \lambda (n)} th primitive root of unity (that must exist by definition of λ), named x {\displaystyle x} and compute the power x λ ( 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 )} . Since k is minimal, it must be k = gcd ( k , ℓ ) {\displaystyle k=\gcd(k,\ell )} and gcd ( k , ℓ ) {\displaystyle \gcd(k,\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 ) {\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}}}
• Consequently the function k ↦ g ( n , k ) {\displaystyle k\mapsto g(n,k)} has d ( λ ( n ) ) {\displaystyle d(\lambda (n))} values different from zero, where d {\displaystyle d} computes the number of divisors.
• g ( n , 1 ) = 1 {\displaystyle g(n,1)=1}
• g ( 4 , 2 ) = 1 {\displaystyle g(4,2)=1}
• g ( 2 n , 2 ) = 3 {\displaystyle g(2^{n},2)=3} for n ≥ 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}} for k ∈ [ 2 , n − 1 ) {\displaystyle k\in [2,n-1)}
• g ( n , 2 ) = 1 {\displaystyle g(n,2)=1} for n ≥ 3 {\displaystyle n\geq 3} and 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)} with φ {\displaystyle \varphi } being Euler's totient function
• The connection between f {\displaystyle f} and g {\displaystyle g} can be written in an elegant way using a Dirichlet convolution:

f = 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)}

One can compute values of g {\displaystyle g} recursively from f {\displaystyle f} using this formula, which is equivalent to the Möbius inversion formula.

By fast exponentiation, one can check that x k ≡ 1 ( mod 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}}} . 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}}} and x k / p ≢ 1 ( mod 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,} 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}}.}

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

which means that x {\displaystyle x} is not a primitive k {\displaystyle k} th root of unity because there is the smaller exponent m {\displaystyle m} .

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

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

To find a modulus 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}}} roots of unity modulo n {\displaystyle n} , the following theorem reduces the problem to a simpler one:

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