Primitive root
Contents
Definition
Suppose 
is a natural number such that the multiplicative group modulo , i.e., the group 
, is a cyclic group. (This happens if and only if is of one of these four forms: 
, where 
is a prime number and 
. Then, a primitive root modulo is a residue class modulo 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 , if the multiplicative group is cyclic, is 
where 
is the Euler totient function. This is because the order of the multiplicative group is 
, and the number of generators of a cyclic group equals the Euler phi-function of its order.
For a proof of the characterization of natural numbers for which the multiplicative group is cyclic, see Classification of natural numbers for which the multiplicative group is cyclic.
Particular cases
Number of primitive roots
Here are the particular cases:
| Value of |
Number of primitive roots |
|---|---|
| 2 | 1 |
| 4 | 1 |
| (odd prime) |
|
 , odd,  |
|
 , odd |
|
 , odd, |
|
Values of primitive roots
For an odd prime , any number that is a primitive root modulo 
continues to be a primitive root modulo higher powers of . We thus list primitive roots only for numbers of the form and .
| Value of |
Number of primitive roots | Smallest absolute value primitive root ( to  ) |
Smallest positive primitive root | All primitive roots from  to
|
|---|---|---|---|---|
| 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.
- 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
. 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 where 
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
|
|---|---|---|
| Quadratic nonresidue that is not minus one is primitive root for safe prime | safe prime | is twice of a prime. The prime  is called a Sophie Germain prime.
|
| Safe prime has plus or minus two as a primitive root | safe prime | is twice of a prime. The prime 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 |
| Fermat prime greater than three implies three is primitive root | Fermat prime | power of 2. In fact, it is a power of a power of 2, and from the given condition, it is also 1 mod 4. |
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  |
(special cases of) generalized Riemann hypothesis |
| Gupta-Ram Murty theorem | Artin's conjecture holds for infinitely many |
Unconditional |
| Heath-Brown theorem on Artin's conjecture | Artin's conjecture holds for all but two exceptional values of . However, no explicit information about the explicit values of |
Unconditional |
