nt.number theory - Reference of primitive root mod p

There are two things that you might want.

1) your example of 2 being a primitive root for $p=4q+1$ where $q$ is also prime comes from the more general criterion that if $p-1 = q_1^{e_1} dots q_r^{e_r}$ is a prime factorization then a non-zero reside $a$ is a primitive root if and only if

$a^{(p-1)/q_i} ne 1 bmod p$ for all $i$.

In the particular case you give $p-1 = 2^2 q$. So the criterion reduces to:

$2^{(p-1)/2} ne 1 bmod p$ and $2^2 ne 1 bmod p$. The second is certainly true if $p ne 3$. The first is true if and only if 2 is quadratic non-residue $bmod p$, which is true (by the law of quadratic reciprocity) if and only if $p equiv 3,5 bmod 8$. However, since if $q$ is odd, $p equiv 5 bmod 8$.

2) You might be interested in Artin's conjecture on primitive roots:

If $a$ is an integer $ne 0,pm 1$ or a square then there are an infinite set of primes $p$ for which $a$ is a primitive root. In fact this set is a positive proportion of all primes, where the constant of proportionality depends on $a$, see http://en.wikipedia.org/wiki/Artin%27s_conjecture_on_primitive_roots

Artin's original conjecture was amended due to computations by D.H. and Emma Lehmer (in a paper entitled "Heuristics Anyone"), and the amended conjecture was proved conditional on various extended Riemann Hypotheses by Hooley. Without the GRH it isn't known that there are even an infinite number of primes for which 2 is a primitive root (in particular it isn't known if there are an infinite number of primes $q$ for which $4q+1$ is prime)

• Next dg.differential geometry - Variational characterization of curvature?
• Previous ac.commutative algebra - An example of two elements without a greatest common divisor