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