In modular arithmetic, 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. That is, g is a primitive root modulo n if for every integer a coprime to n, there is some integer k for which g^k ≡ a (mod n). Such a value k is called the index or discrete logarithm of a to the base g modulo n. So g is a primitive root modulo n if and only if g is a generator of the multiplicative group of integers modulo n.

Gauss defined primitive roots in Article 57 of the Disquisitiones Arithmeticae (1801), where he credited Euler with coining the term. In Article 56 he stated that Lambert and Euler knew of them, but he was the first to rigorously demonstrate that primitive roots exist for a prime 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.

A primitive root exists if and only if n is 1, 2, 4, p^k or 2p^k, where p is an odd prime and k > 0. For all other values of n the multiplicative group of integers modulo n is not cyclic. This was first proved by Gauss.

The number 3 is a primitive root modulo 7 because $${\displaystyle {\begin{array}{rcrcrcrcrcr}3^{1}&=&3^{0}\times 3&\equiv &1\times 3&=&3&\equiv &3{\pmod {7}}\\3^{2}&=&3^{1}\times 3&\equiv &3\times 3&=&9&\equiv &2{\pmod {7}}\\3^{3}&=&3^{2}\times 3&\equiv &2\times 3&=&6&\equiv &6{\pmod {7}}\\3^{4}&=&3^{3}\times 3&\equiv &6\times 3&=&18&\equiv &4{\pmod {7}}\\3^{5}&=&3^{4}\times 3&\equiv &4\times 3&=&12&\equiv &5{\pmod {7}}\\3^{6}&=&3^{5}\times 3&\equiv &5\times 3&=&15&\equiv &1{\pmod {7}}\end{array}}}$$

Here we see that the period of 3^k modulo 7 is 6. The remainders in the period, which are 3, 2, 6, 4, 5, 1, form a rearrangement of all nonzero remainders modulo 7, implying that 3 is indeed a primitive root modulo 7. This derives from the fact that a sequence (g^k modulo n) always repeats after some value of k, since modulo n produces a finite number of values. If g is a primitive root modulo n and n is prime, then the period of repetition is n − 1. Permutations created in this way (and their circular shifts) have been shown to be Costas arrays.

If n is a positive integer, the integers from 1 to n − 1 that are coprime to n (or equivalently, the congruence classes coprime to n) form a group, with multiplication modulo n as the operation; it is denoted by ${\displaystyle \mathbb {Z} }$^×
_n, and is called the group of units modulo n, or the group of primitive classes modulo n. As explained in the article multiplicative group of integers modulo n, this multiplicative group (${\displaystyle \mathbb {Z} }$^×
_n) is cyclic if and only if n is equal to 2, 4, p^k, or 2p^k where p^k is a power of an odd prime number. When (and only when) this group ${\displaystyle \mathbb {Z} }$^×
_n is cyclic, a generator of this cyclic group is called a primitive root modulo n (or in fuller language primitive root of unity modulo n, emphasizing its role as a fundamental solution of the roots of unity polynomial equations X^m
− 1 in the ring ${\displaystyle \mathbb {Z} }$_n), or simply a primitive element of ${\displaystyle \mathbb {Z} }$^×
_n.

When ${\displaystyle \mathbb {Z} }$^×
_n is non-cyclic, such primitive elements mod n do not exist. Instead, each prime component of n has its own sub-primitive roots (see 15 in the examples below).

For any n (whether or not ${\displaystyle \mathbb {Z} }$^×
_n is cyclic), the order of ${\displaystyle \mathbb {Z} }$^×
_n is given by Euler's totient function φ(n) (sequence A000010 in the OEIS). And then, Euler's theorem says that a^φ(n) ≡ 1 (mod n) for every a coprime to n; the lowest power of a that is congruent to 1 modulo n is called the multiplicative order of a modulo n. In particular, for a to be a primitive root modulo n, a^φ(n) has to be the smallest power of a that is congruent to 1 modulo n.