Root of unity modulo n

In <a href="/facts/Number_theory/zhoa7zrc">number theory</a>, a kth root of unity modulo n for positive <a href="/facts/Integer/PUwwrawx">integers</a> k, n ≥ 2, is a <a href="/facts/Root_of_unity/EqH0ho1Y">root of unity</a> in the ring of <a href="/facts/Integers_modulo_n/0wtRa5dU">integers modulo n</a>; that is, a solution x to the <a href="/facts/Equation/pxFzLAVR">equation</a> (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 <a href="/facts/Modular_arithmetic/0wtRa5dU">modular arithmetic</a> for notation and terminology.
The roots of unity modulo n are exactly the integers that are <a href="/facts/Coprime/bnCxCXxs">coprime</a> with n. In fact, these integers are roots of unity modulo n by <a href="/facts/Euler%2527s_theorem/2q2DTwK3">Euler's theorem</a>, and the other integers cannot be roots of unity modulo n, because they are <a href="/facts/Zero_divisor/5GraAU8o">zero divisors</a> modulo n.
A <a href="/facts/Primitive_root_modulo_n/QS4DbIB0">primitive root modulo n</a>, is a generator of the group of <a href="/facts/Unit_(ring_theory)/GJSBu8Y7">units</a> 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 <a href="/facts/Carmichael_function/D0l0I6od">Carmichael function</a> and <a href="/facts/Euler%2527s_totient_function/mIQwXYzj">Euler's totient function</a>.
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).}

Root of unity modulo n open-in-new

Root of unity modulo n