A primitive root of a prime 
is an integer 
such that 
(mod 
) has multiplicative order 
(Ribenboim 1996, p. 22). More
generally, for an integer 
, 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 
incongruent primitive roots (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). An integer 
has a primitive root iff
it is of the form 2, 4, 
, or 
, where 
is an odd prime and 
is a positive integer
(Burton 1989, p. 204). The first few such 
are 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 17, 18, 19, 22, ...
(OEIS A033948, with the initial 1 omitted).
For 
,
3, ..., the numbers of primitive roots modulo 
are 1, 1, 1, 2, 1, 2, 0, 2, 2, 4, 0, 4, ... (OEIS A046144).
These two OEIS sequences include a primitive root modulo
1, whereas the convention here restricts primitive roots to moduli 
.
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 a 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 among the integers 1, 2, ..., 
,
or 0 when none exist, 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.
| 2 | 1 | 38 | 3 | 94 | 5 | 158 | 3 |
| 3 | 2 | 41 | 6 | 97 | 5 | 162 | 5 |
| 4 | 3 | 43 | 3 | 98 | 3 | 163 | 2 |
| 5 | 2 | 46 | 5 | 101 | 2 | 166 | 5 |
| 6 | 5 | 47 | 5 | 103 | 5 | 167 | 5 |
| 7 | 3 | 49 | 3 | 106 | 3 | 169 | 2 |
| 9 | 2 | 50 | 3 | 107 | 2 | 173 | 2 |
| 10 | 3 | 53 | 2 | 109 | 6 | 178 | 3 |
| 11 | 2 | 54 | 5 | 113 | 3 | 179 | 2 |
| 13 | 2 | 58 | 3 | 118 | 11 | 181 | 2 |
| 14 | 3 | 59 | 2 | 121 | 2 | 191 | 19 |
| 17 | 3 | 61 | 2 | 122 | 7 | 193 | 5 |
| 18 | 5 | 62 | 3 | 125 | 2 | 194 | 5 |
| 19 | 2 | 67 | 2 | 127 | 3 | 197 | 2 |
| 22 | 7 | 71 | 7 | 131 | 2 | 199 | 3 |
| 23 | 5 | 73 | 5 | 134 | 7 | 202 | 3 |
| 25 | 2 | 74 | 5 | 137 | 3 | 206 | 5 |
| 26 | 7 | 79 | 3 | 139 | 2 | 211 | 2 |
| 27 | 2 | 81 | 2 | 142 | 7 | 214 | 5 |
| 29 | 2 | 82 | 7 | 146 | 5 | 218 | 11 |
| 31 | 3 | 83 | 2 | 149 | 2 | 223 | 3 |
| 34 | 3 | 86 | 3 | 151 | 6 | 226 | 3 |
| 37 | 2 | 89 | 3 | 157 | 5 | 227 | 2 |
Let 
be any odd prime, let 
be a positive integer,
and let
 |
(1)
|
Then
 |
(2)
|
(Ribenboim 1996, pp. 22-23). For numbers 
with primitive roots, all 
satisfying 
are representable as
 |
(3)
|
where 
is a primitive root of 
,
, 1, ..., 
is known as the index, and 
is an integer. Let 
denote the least primitive root of a prime 
. Kearnes (1984) showed that for any
positive integer 
, there exist infinitely many primes 
such that
 |
(4)
|
Burgess (1962) proved that for every 
there is a positive
constant 
such that
 |
(5)
|
for 
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.
-Series."
Proc. London Math. Soc. 12, 193-206, 1962.Burton, D. M.
"The Order of an Integer Modulo 
," "Primitive Roots for Primes," and "Composite
Numbers Having Primitive Roots." §8.1-8.3 in