Primitive root

Definition

Suppose $n$ is a natural number such that the multiplicative group modulo $n$, i.e., the group $(\mathbb{Z}/n\mathbb{Z}{)}^{*}$, is a cyclic group. (This happens if and only if $n$ is of one of these four forms: $2,4,p^k,2p^k$, where $p$ is a prime number and $k\in \mathbb{N}$. Then, a primitive root modulo $n$ is a residue class modulo $n$ that generates the cyclic group.

We often use the term primitive root for an integer representative of such a residue class.

The number of primitive roots modulo $n$, if the multiplicative group is cyclic, is $\phi (\phi (n))$ where $\phi$ is the Euler phi-function. This is because the order of the multiplicative group is $\phi (n)$, and the number of generators of a cyclic group equals the Euler phi-function of its order.

Particular cases

Number of primitive roots

Here are the particular cases:

Value of $n$	Number of primitive roots
2	1
4	1
$p$ (odd prime)	$\phi (p-1)$
$p^k$, $p$ odd, $k\ge 2$	$p^{k-2}(p-1)\phi (p-1)$
$2p$, $p$ odd	$\phi (p-1)$
$2p^k$, $p$ odd, $k\ge 2$	$p^{k-2}(p-1)\phi (p-1)$

Values of primitive roots

For an odd prime $p$, any number that is a primitive root modulo $p^2$ continues to be a primitive root modulo higher powers of $p$. We thus list primitive roots only for numbers of the form $p$ and $p^2$.

Value of $n$	Number of primitive roots	Smallest absolute value primitive root ($-n/2$ to $n/2$)	Smallest positive primitive root	All primitive roots from $1$ to $n$
2	1	1	1	1
3	1	-1	2	2
4	1	-1	3	3
5	2	2,-2	2	2,3
7	2	-2	3	3,5
9	2	2	2	2,5
11	4	2	2	2,6,7,8
13	4	2	2	2,6,7,11

Facts

• Quadratic nonresidue that is not minus one is primitive root for safe prime
• Safe prime has plus or minus two as a primitive root