Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|cite|improve this question
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 2

up vote 2 down vote accepted

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?

share|cite|improve this answer
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

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)

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.