3
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\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
    Commented Apr 28, 2013 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 ♦
    Commented Apr 28, 2013 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
    Commented Apr 29, 2013 at 0:16

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\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
    Commented Apr 29, 2013 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
    Commented Apr 29, 2013 at 6:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .