primitive root

Given any positive integer $n$, the group of units $U(\mathbb{Z}/n\mathbb{Z})$ of the ring $\mathbb{Z}/n\mathbb{Z}$ is a cyclic group iff $n$ is 4, $p^m$ or $2p^m$ for any odd positive prime $p$ and any non-negative integer $m$.  A primitive root is a generator of this group of units when it is cyclic.

Equivalently, one can define the integer $r$ to be a primitive root modulo $n$, if the numbers $r^0,r^1,\mathrm{\dots },r^{n-2}$ form a reduced residue system modulo $n$.

For example, 2 is a primitive root modulo 5, since$1,\mathrm{\hspace{0.33em}2},{\mathrm{\hspace{0.33em}2}}^2=4,{\mathrm{\hspace{0.33em}2}}^3=8\equiv 3(mod5)$are all with 5 coprime positive integers less than 5.

The generalized Riemann hypothesis implies that every prime number $p$ has a primitive root below $70{(\ln p)}^2$.