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
17	8	3,-3	3	3,5,6,7,10,11,12,14

Relation with other properties

Smallests

• Smallest primitive root is the smallest positive number that is a primitive root modulo a given number.
• Smallest magnitude primitive root is the primitive root with the smallest absolute value.

Other related properties

• Quadratic nonresidue is a number relatively prime to the modulus that is not a square modulo the modulus. Any primitive root must be a quadratic nonresidue except in the case where the modulus is $2$. This is because the multiplicative group has even order and hence its generator cannot be a square.

Facts

Known facts

For most primes, finding a primitive root is hard work. However, for those primes $p$ where $p-1$ has a very small list of prime factors, it is relatively easy to find a primitive root. Some cases are below:

Statement	Applicable prime type	Description in terms of factorization of $p-1$
Quadratic nonresidue that is not minus one is primitive root for safe prime	safe prime	$p-1$ is twice of a prime. The prime $(p-1)/2$ is called a Sophie Germain prime.
Safe prime has plus or minus two as a primitive root	safe prime	$p-1$ is twice of a prime. The prime $(p-1)/2$ is called a Sophie Germain prime.
Quadratic nonresidue equals primitive root for Fermat prime	Fermat prime	power of 2. In fact, it is a power of a power of 2

Conjectures and conditionally known facts

Artin's conjecture on primitive roots states that any integer that is not a perfect square and that is not equal to -1 occurs as a primitive root for infinitely many primes. The conjecture is open, but partial results are known:

Name of conjecture/fact	Statement	Conditional to ...
Hooley's theorem	Artin's conjecture holds for all $a$	(special cases of) generalized Riemann hypothesis
Gupta-Ram Murty theorem	Artin's conjecture holds for infinitely many $a$	Unconditional
Heath-Brown theorem on Artin's conjecture	Artin's conjecture holds for all but two exceptional values of $a$. However, no explicit information about the explicit values of $a$	Unconditional