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. 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. 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).}
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}} . 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}}.}
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)} . 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.
… excerpt ends here. Continue reading the full article.
