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
    Commented 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
    Commented Mar 19, 2021 at 23:11
  • $\begingroup$ That is what I was thinking when I wrote conditional. $\endgroup$
    – Dr. Pi
    Commented 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
    Commented 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$ Commented Mar 21, 2021 at 12:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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