Let $a$ be an integer which is neither a square nor $-1$. Artin's conjecture states that there are infinitely many primes $p$ for which $a$ is a primitive root modulo $p$. My question is whether there is anything on the literature for

(1) the (conjectural) size of the smallest such prime $p$.

(2) Conditional or unconditional upper or lower bounds.

Regarding (2), one can chase down the implied constants in Hooley's paper (Hooley, Christopher (1967). "On Artin's conjecture." J. Reine Angew. Math. 225, 209-220) to show that his asymptotic must kick in after $x\geq x_0=|a|^{C\log \log 3|a|}$ for some absolute $C>0$. Thus, under GRH the least prime is at most $$|a|^{C\log \log 3|a|}.$$

  • $\begingroup$ Heuristically, one should probably expect there to be a constant $k$ such that that the least prime is at most $|a|^k$. I don't know if this is in the literature anywhere unfortunately. I'd be also willing to go out on a limb and say that $|a|^{2 +\epsilon}$ is likely the correct bound. $\endgroup$
    – JoshuaZ
    Mar 16, 2021 at 12:43
  • $\begingroup$ An upper bound without using something substantial is unlikely. If each integer $a$ that's not $-1$ or a perfect square is a primitive root modulo at least one prime $p$ that's not a Fermat prime, then you can show each integer $a$ that's not $-1$ or a perfect square is a primitive root modulo infinitely many primes, which is the qualitative form of Artin's primitive root conjecture. This is similar to proving there are infinitely many primes $p \equiv a \bmod m$ whenever $(a,m) = 1$ if there is at least one $p \equiv a \bmod m$ whenever $(a,m)=1$. So getting one prime in general is hard! $\endgroup$
    – KConrad
    Mar 19, 2021 at 23:11
  • $\begingroup$ That is what I was thinking when I wrote conditional. $\endgroup$
    – Dr. Pi
    Mar 20, 2021 at 10:36

1 Answer 1


One would guess much smaller. If p=2q+1 where p and q are prime, then a is a primitive root mod p IFF (a/p)=-1 and p does not divide a+1. One would guess from the usual heuristics that there is such a prime p once one has tested about c log |a| loglog |a| of them. Therefore we would expect to find such a p which is << log |a| (log log |a|)^3. For most a, one of the first 100 Sophie Germain primes will work; indeed I very much doubt you can compute an example where they will not.

  • $\begingroup$ This is great, many thanks! Do you have a guess what happens to $\log |a| (\log_2 |a|)^3$ if $(p-1)/2$ is, say, a product of 2 distinct primes? I would naively guess $\log |a| (\log_2 |a|)^a$ for some $a<3$. I think in general the true size ought to be $o(\log |a| )$ but have no idea how to justify this. $\endgroup$
    – Dr. Pi
    Mar 20, 2021 at 11:35
  • 1
    $\begingroup$ Since the conjecture for the least prime quadratic residue mod p is << log p loglog p $\endgroup$ Mar 21, 2021 at 12:36

You must log in to answer this question.

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