Reference of primitive root mod p - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T03:00:35Z http://mathoverflow.net/feeds/question/8345 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/8345/reference-of-primitive-root-mod-p Reference of primitive root mod p watchmath 2009-12-09T13:31:09Z 2010-02-28T08:36:22Z <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:</p> <p>$2$ is a primitive root mod $p$ for all prime $p$ of the form $p=4q+1$ where $q$ is also a prime.</p> <p>Thanks in advance.</p> http://mathoverflow.net/questions/8345/reference-of-primitive-root-mod-p/8366#8366 Answer by Gjergji Zaimi for Reference of primitive root mod p Gjergji Zaimi 2009-12-09T16:42:10Z 2009-12-09T16:42:10Z <p>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?</p> http://mathoverflow.net/questions/8345/reference-of-primitive-root-mod-p/14464#14464 Answer by Victor Miller for Reference of primitive root mod p Victor Miller 2010-02-07T04:57:20Z 2010-02-07T04:57:20Z <p>There are two things that you might want.</p> <p>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</p> <p>$a^{(p-1)/q_i} \ne 1 \bmod p$ for all $i$.</p> <p>In the particular case you give $p-1 = 2^2 q$. So the criterion reduces to:</p> <p>$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$.</p> <p>2) You might be interested in Artin's conjecture on primitive roots:</p> <p>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 <a href="http://en.wikipedia.org/wiki/Artin%27s_conjecture_on_primitive_roots" rel="nofollow">http://en.wikipedia.org/wiki/Artin%27s_conjecture_on_primitive_roots</a></p> <p>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)</p>