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$.

Title	primitive root
Canonical name	PrimitiveRoot
Date of creation	2013-03-22 16:04:33
Last modified on	2013-03-22 16:04:33
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	12
Author	CWoo (3771)
Entry type	Definition
Classification	msc 11-00
Synonym	primitive root modulo n
Synonym	primitive element
Related topic	MultiplicativeOrderOfAnIntegerModuloM
Related topic	PrimeResidueClass
Related topic	UsingPrimitiveRootsAndIndexToSolveCongruences