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 $\varphi (\varphi (n))$ where $\varphi$ is the Euler phi-function. This is because the order of the multiplicative group is $\varphi (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)	$\varphi (p-1)$
$p^{k}$, $p$ odd, $k\geq 2$	$p^{k-2}(p-1)\varphi (p-1)$
$2p$, $p$ odd	$\varphi (p-1)$
$2p^{k}$, $p$ odd, $k\geq 2$	$p^{k-2}(p-1)\varphi (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
17	8	3,-3	3	3,5,6,7,10,11,12,14

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