# 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},\,\ldots,\,r^{n-2}$ form a reduced residue system modulo $n$.

For example, 2 is a primitive root modulo 5, since $1,\;2,\;2^{2}=4,\;2^{3}=8\equiv 3\pmod{5}$ 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}$.

## References

Wikipedia, “Primitive root modulo n”

Title primitive root PrimitiveRoot 2013-03-22 16:04:33 2013-03-22 16:04:33 CWoo (3771) CWoo (3771) 12 CWoo (3771) Definition msc 11-00 primitive root modulo n primitive element MultiplicativeOrderOfAnIntegerModuloM PrimeResidueClass UsingPrimitiveRootsAndIndexToSolveCongruences