# Reference of primitive root mod p

Can any body give me a reference of the result about primitive root mod p for a class of prime number p. The result that I am looking for is something along this line:

$2$ is a primitive root mod $p$ for all prime $p$ of the form $p=4q+1$ where $q$ is also a prime.

Thanks in advance.

-
This is not homework. Probably you misunderstood my question. I am looking for all known result of this kind. For example 3 is a primitive root of what kind of prime. We even don't know if 2 is a primitive root of infinitely many prime. – user808 Dec 9 '09 at 13:45
Yeah, you're right. I misread it. – Harry Gindi Dec 9 '09 at 13:50
I'm not accusing you of wanting this reference for homework, but I can personally attest to having assigned this problem as homework a couple of months ago. – Ben Webster Dec 9 '09 at 20:07

## 2 Answers

Take a look at "A criterion on primitive roots modulo p" by H.Park, J.Park, D.Kim. There is a collection of various criteria including the above for small primes to appear as primitive roots. I hope it helps, or are you looking for something more general?

-
Thanks a lot. At the moment this paper is general enough for me. – user808 Dec 9 '09 at 23:07

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)

-