Primitive root

From Number
Revision as of 21:17, 15 January 2012 by Vipul (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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

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