# Least non primitive root

There is an abundant literature, and even here on MO no shortage of questions, on the question of the smallest prime primitivee root modulo $q$ (where $q$ is a prime, or more generally an odd prime power, so that $(\mathbb Z/q \mathbb Z)^\ast$ is cyclic, and has generators, called primitive root). I wonder if there is any conjecture or result on the following problem:

For $q$ a prime or an odd prime power, estimate the smallest prime $n(q)$ which is not a primitive root modulo $q$.

It is certainly very hard to prove any non-trivial lower bound on $n(q)$, since the statement $n(q)>2$ for all prime $q$ sufficiently large is clearly equivalent to the falsity of Artin's conjecture that $2$ is a primitive root infinitely often. But what about a conjectural lower bound? and what about upper bound?

-
For an upper bound you can estimate, e.g., the smallest prime that is a quadratic residue mod $q$ by using an effective Cebotarev, say Lagarias-Odlysko. I think $n(q)=2$ for infinitely many $q$, or did I not understand the question? – Felipe Voloch Apr 28 '13 at 17:14
Wouldn't it be a more natural question to ask for the smallest $n$ which is coprime to $q$ and neither a perfect power nor a primitive root modulo $q$? -- Or do you need primality for some reason? – Stefan Kohl Apr 28 '13 at 19:56
I think the reason for asking for a prime is to avoid silliness like the following: For each odd prime $q > 3$, one of $2$, $3$, or $6$ is a quadratic residue and so not a primitive root. In terms of an upper bound, there's a nice theorem of Linnik and Vinogradov that bounds the smallest prime quadratic residue modulo an odd prime $q$ by $O(q^{1/4+\epsilon})$. – Anonymous Apr 29 '13 at 0:16

Trivially, any upper bound for the least prime quadratic residue modulo $p$ is also an upper bound for the least prime non-primitive root modulo $q$. I can't recall what's been proved about the latter problem assuming GRH (probably a power of $\log q$), but that will form a good conjectural upper bound.
As for a conjectural lower bound, given an odd integer $n$, there are presumably infinitely many primes $q$ in any fixed residue class $a\pmod{8n}$ such that $(q-1)/2$ is also prime, as long as $a-1$ is not divisible by any prime dividing $n$. Taking $n$ to be the product of all the odd primes up to $z$, so that $n \approx e^z$, we expect to find such a prime $q$ no larger than $e^{(1+o(1))z}$. If we choose $a$ appropriately, then all primes up to $z$ will be quadratic residues modulo $q$; since $(q-1)/2$ is also prime, all quadratic residues are primitive roots. This argument gives a conjectural lower bound of about $\log q$ for the smallest prime non-primitive root.
Yes, the lower bound would apply only for infinitely many $q$. That's the best one can hope for: the only lower bound that would apply for all prime $q$, or even almost all prime $q$, would be $n(q)\ge2$ (assuming Artin's conjecture). – Greg Martin Apr 29 '13 at 6:13