primitive roots and primes - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T12:09:54Z http://mathoverflow.net/feeds/question/62851 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/62851/primitive-roots-and-primes primitive roots and primes tim 2011-04-24T17:58:32Z 2011-04-27T21:07:37Z <p>Given a positive integer $n > 1$, is it true that there exists infinitely many primes $p$ such that $n$ is a primitive root modulo $p$. </p> http://mathoverflow.net/questions/62851/primitive-roots-and-primes/62856#62856 Answer by Pete L. Clark for primitive roots and primes Pete L. Clark 2011-04-24T20:10:35Z 2011-04-27T21:07:37Z <p>There is a simple answer here, so someone might as well record it.</p> <p>Let $n$ be a nonzero integer. If $n = -1$ or $n$ is a square then there is no prime $p > 3$ such that $n$ is a primitive root modulo $p$. There are no other obvious obstructions. (It is worth thinking for a second why we do not have to rule out $n$ being a cube, for instance: this is a nice exercise in cyclic group theory.)</p> <p>There is a famous conjecture that these obvious necessary conditions are the only ones: namely <a href="http://en.wikipedia.org/wiki/Artin%27s_conjecture_on_primitive_roots" rel="nofollow">Artin's Primitive Root Conjecture</a> asserts that for any integer $n$ which is not $0$, $-1$ and not a square, there are infinitely many prime numbers $p$ such that $n$ is a primitive root modulo $p$. In fact the conjecture is more precise than this: the set of primes $p$ for which such an $n$ is a primitive root is conjectured to have positive relative density among all primes and, at least under some mild additional restrictions, this density is conjectured to be a certain specific number which is independent of $n$:</p> <p>$C = \prod_{p \text{ prime}} \left(1- \frac{1}{p(p-1)} \right)$;</p> <p>this $C$ is known as <strong>Artin's constant</strong>. This conjecture was proved by C. Hooley in 1967 assuming the Generalized Riemann Hypothesis. More recently unconditional results have been given by Gupta, R. Murty and Heath-Brown which consider several numbers $n$ at a time and show that Artin's Conjecture must be true for at least one of them. But the conjecture is still open for any one fixed value of $n$.</p> http://mathoverflow.net/questions/62851/primitive-roots-and-primes/62858#62858 Answer by Aaron Meyerowitz for primitive roots and primes Aaron Meyerowitz 2011-04-24T20:12:49Z 2011-04-24T20:12:49Z <p>It showed up in a <a href="http://mathoverflow.net/questions/62787" rel="nofollow">recent question</a> so one might wonder. The article <a href="http://www.mast.queensu.ca/~murty/mi.dvi" rel="nofollow">Artin's conjecture for primitive roots</a>, Math. Intelligencer, 10 (4) (1988) 59-67 by Ram Murty seems like a good survey. The link is to a dvi copy. It informs one that the result follows from a Generalized Riemann Hypothesis and is unconditionally true for at least one of $2,3,5.$ </p> <p>The first $12000$ primes for which $7$ is a primitive root run from $11$ to $378011$. This proportion $\frac{12000}{32141} \approx 0.3734$ agrees well with the theoretical expected proportion of $\prod(1-\frac{1}{p(p-1)}) \approx 0.3739$ where the product is over the primes. The distribution according to congruence class $\mod 7$ is $[1, 1748], [2, 2074], [3, 2032], [4, 2058], [5, 2065], [6, 2023].$ This slight deficit in congruence class 1 seems to hold through this range.</p>