Primitive Root

A primitive root of a prime is an integer such that (mod ) has multiplicative order (Ribenboim 1996, p. 22). More generally, if ( and are relatively prime) and is of multiplicative order modulo where is the totient function, then is a primitive root of (Burton 1989, p. 187). The first definition is a special case of the second since for a prime.

A primitive root of a number (but not necessarily the smallest primitive root for composite ) can be computed in the Wolfram Language using PrimitiveRoot[n].

If has a primitive root, then it has exactly of them (Burton 1989, p. 188), which means that if is a prime number, then there are exactly incongruent primitive roots of (Burton 1989). For , 2, ..., the first few values of are 1, 1, 1, 1, 2, 1, 2, 2, 2, 2, 4, 2, 4, 2, 4, 4, 8, ... (OEIS A010554). has a primitive root if it is of the form 2, 4, , or , where is an odd prime and (Burton 1989, p. 204). The first few for which primitive roots exist are 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 17, 18, 19, 22, ... (OEIS A033948), so the number of primitive root of order for , 2, ... are 0, 1, 1, 1, 2, 1, 2, 0, 2, 2, 4, 0, 4, ... (OEIS A046144).

The smallest primitive roots for the first few primes are 1, 2, 2, 3, 2, 2, 3, 2, 5, 2, 3, 2, 6, 3, 5, 2, 2, 2, ... (OEIS A001918). Here is table of the primitive roots for the first few for which a primitive root exists (OEIS A046147).

2	1
3	2
4	3
5	2, 3
6	5
7	3, 5
9	2, 5
10	3, 7
11	2, 6, 7, 8
13	2, 6, 7, 11

The largest primitive roots for , 2, ..., are 0, 1, 2, 3, 3, 5, 5, 0, 5, 7, 8, 0, 11, ... (OEIS A046146). The smallest primitive roots for the first few integers are given in the following table (OEIS A046145), which omits when does not exist.

Let be any odd prime , and let

(1)

Then

(2)

(Ribenboim 1996, pp. 22-23). For numbers with primitive roots, all satisfying are representable as

(3)

where , 1, ..., , is known as the index, and is an integer. Kearnes (1984) showed that for any positive integer , there exist infinitely many primes such that

(4)

Call the least primitive root . Burgess (1962) proved that

(5)

for and positive constants and sufficiently large (Ribenboim 1996, p. 24).

Matthews (1976) obtained a formula for the "two-dimensional" Artin's constants for the set of primes for which and are both primitive roots.

Wolfram Web Resources