Primitive root modulo n

In <a href="/facts/Modular_arithmetic/0wtRa5dU">modular arithmetic</a>, a number g is a primitive root modulo n if every number a <a href="/facts/Coprime/bnCxCXxs">coprime</a> to n is <a href="/facts/Congruence_relation/TV3njpqF">congruent</a> to a power of g modulo n. That is, g is a primitive root modulo n if for every integer a coprime to n, there is some integer k for which gk ≡ a (mod n). Such a value k is called the index or <a href="/facts/Discrete_logarithm/k8TXh5bL">discrete logarithm</a> of a to the base g modulo n. So g is a primitive root modulo n if and only if g is a <a href="/facts/Generating_set_of_a_group/B9q5lnFY">generator</a> of the <a href="/facts/Multiplicative_group_of_integers_modulo_n/IACS6cgH">multiplicative group of integers modulo n</a>.
<a href="/facts/Carl_Friedrich_Gauss/f4eSMBD7">Gauss</a> defined primitive roots in Article 57 of the <a href="/facts/Disquisitiones_Arithmeticae/VQ38ReTh">Disquisitiones Arithmeticae</a> (1801), where he credited <a href="/facts/Euler/z2fsbjgj">Euler</a> with coining the term. In Article 56 he stated that <a href="/facts/Johann_Heinrich_Lambert/CG3IHVB9">Lambert</a> and Euler knew of them, but he was the first to rigorously demonstrate that primitive roots exist for a <a href="/facts/Prime_number/L20FLkgn">prime</a> n. In fact, the Disquisitiones contains two proofs: The one in Article 54 is a nonconstructive <a href="/facts/Existence_theorem/Au8x1FSt">existence proof</a>, while the proof in Article 55 is <a href="/facts/Constructive_proof/0QhhRjhW">constructive</a>.
A primitive root exists if and only if n is 1, 2, 4, pk or 2pk, where p is an odd prime and k > 0. For all other values of n the multiplicative group of integers modulo n is not <a href="/facts/Cyclic_group/JL5zfFuL">cyclic</a>.
This was first proved by <a href="/facts/Carl_Friedrich_Gauss/f4eSMBD7">Gauss</a>.

Primitive root modulo n open-in-new

Primitive root modulo n