Reference of primitive root mod p

2009-12-09T13:31:09Z

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.

Answer by Gjergji Zaimi for Reference of primitive root mod p

2009-12-09T16:42:10Z

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?

Answer by Victor Miller for Reference of primitive root mod p

2010-02-07T04:57:20Z

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)

Reference of primitive root mod p - MathOverflow

Reference of primitive root mod p

Answer by Gjergji Zaimi for Reference of primitive root mod p

Answer by Victor Miller for Reference of primitive root mod p