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?

  • $\begingroup$ 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? $\endgroup$ – Felipe Voloch Apr 28 '13 at 17:14
  • 1
    $\begingroup$ 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? $\endgroup$ – Stefan Kohl Apr 28 '13 at 19:56
  • $\begingroup$ 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})$. $\endgroup$ – 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.

  • $\begingroup$ As I said in my comment, Lagarias-Odlyzko gives a bound for the least prime quadratic non-residue. Under GRH it is a power of log q. Your lower bound applies only for infinitely many q, no? $\endgroup$ – Felipe Voloch Apr 29 '13 at 2:41
  • $\begingroup$ 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). $\endgroup$ – Greg Martin Apr 29 '13 at 6:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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