Primitive root modulo $n$

In number theory, a number $g$ is a primitive root modulo $n$ if every number $a$ coprime to $n$ is congruent to a power of $g$ modulo $n$ . In symbols, $g$ is a primitive root modulo $n$ if for every integer $a$ coprime to $n$ , there is some integer $k$ for which $g k \equiv a (mod n)$ .

Primitive roots only exist for some integers $n$ . Specifically, a primitive root exists modulo $n$ if and only if $n$ is 1, 2, 4, $p k$ or $2 p k$ for some odd prime number $p$ and some $k > 0$ . This was first proved by Carl Friedrich Gauss. Gauss defined primitive roots in Article 57 of his Disquisitiones Arithmeticae (1801), where he credited Leonhard Euler with coining the term. In Article 56 he stated that Johann Heinrich Lambert and Euler knew of them, but he was the first to rigorously demonstrate that primitive roots exist for a prime number $n$ . In fact, the Disquisitiones contains two proofs: The one in Article 54 is a nonconstructive existence proof, while the proof in Article 55 is constructive.

An equivalent characterization is that $g$ is a primitive root modulo $n$ if and only if $g$ is a generator of the multiplicative group of integers modulo $n$ . Thus, primitive roots exist if and only if this group is a cyclic group.

If $g$ is a primitive root modulo $n$ and $g k \equiv a (mod n)$ , then the value $k$ is called the index or discrete logarithm of $a$ to the base $g$ modulo $n$ .