Primitive root

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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

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