I was recently compiling some notes for an undergrad-level course on number theory, and I went over the proof of the fact that $(\mathbb{Z}/p\mathbb{Z})^\times$ is cyclic for any prime $p$: it's a finite abelian group and thus the direct sum of cyclic groups, and the fact that $X^r - 1\in (\mathbb{Z}/p\mathbb{Z})[X]$ has at most $r$ zeros forces $(\mathbb{Z}/p\mathbb{Z})^\times$ to be cyclic itself. It's a completely nonconstructive proof, and there aren't many tools available at that level for digging any deeper into the problem.

So, what is the current state of the art for primitive roots mod $p$? I'm not a number theorist, and I don't know much about the problem aside from Artin's conjecture (which, as far as I know, is still a conjecture). I think it's known that it holds for infinitely many primes unconditionally and all but a small, finite number modulo a particular form of the generalized Riemann hypothesis, but those results are both several decades old. (Even the most relevant questions on this site I could find are more than a decade old.) Are there any newer results or any new methods that look promising, or is this just an untractable problem for now? Or, for that matter, is the last result I mentioned considered a satisfying answer? (To clarify, I'm asking for my own benefit and am not looking for an undergrad-level answer.)

  • 4
    $\begingroup$ I would not call a theorem that is based on enumerative exhaustion of a finite set "non-constructive", it is merely inefficient. The theorem clearly proves that if you run through the numbers $2,\dots,p-2 $, (a finite set) you *will* find an $a$ such that its order is exactly $p-1$. If it helps, think of the factorisation of a number into a product of primes. This is not considered "non-constructive" merely inefficient. $\endgroup$
    – Kapil
    Aug 18 at 15:06
  • $\begingroup$ @Kapil: Sure, but my point is that there's no way to control or predict what the generator of that group is going to be. It doesn't construct an explicit generator of that group, and that's the part I care about in the context of Artin's conjecture and similar results. $\endgroup$
    – anomaly
    Aug 18 at 15:11
  • 9
    $\begingroup$ A relevant comment by Victor Shoup in the notes to Section 11.4 of his book A Computational Introduction to Number Theory and Algebra: "there is no known way to efficiently recognize a primitive root modulo $p$ without knowing the prime factorization of $p − 1$." That is a statement being made over all primes $p$. $\endgroup$
    – KConrad
    Aug 18 at 16:07
  • 2
    $\begingroup$ Two other related results: Let $g_p$ be the smallest positive integer which is a primitive root mod $p$. Then Grosswald showed that $g_p = O(p^{0.499})$, and Shoup has shown that if one assumes GRH, then $g_p = O( (\log p)^6))$. $\endgroup$
    – JoshuaZ
    Aug 19 at 1:31
  • 4
    $\begingroup$ The ultimate reference (and still mostly up to date) is Moree: arxiv.org/abs/math/0412262 $\endgroup$ Aug 19 at 11:05

1 Answer 1


Artin's conjecture on primitive roots has a qualitative version and quantitative version. The qualitative version says if $a \in \mathbf Z$ is not $-1$ or a perfect square then $a \bmod p$ is a primitive root mod $p$ for infinitely many $p$. The quantitative version says for such $a$ that the number of $p \leq x$ such that $a \bmod p$ is a primitive root mod $p$ is asymptotic to $c_ax/\log x$, where $c_a$ is an explicit positive constant depending on $a$. The quantitative version was completely proved by Hooley assuming GRH for zeta-functions of a certain infinite set of number fields (no "all, but a small finite number" as you wrote).

In what I write below, I will be referring to the qualitative version of the conjecture ("infinitely many").

You wrote "I think it's known that it holds for infinitely many primes unconditionally". The correctness of that statement depends on the kind of result you are after.

  1. For no specific integer $a$ in $\mathbf Z$ is it known (without using GRH) that $a \bmod p$ is a primitive root for infinitely many $p$.

  2. In 1984, Gupta and Murty showed there are infinitely many $a$ such that Artin's conjecture is true for $a$, but they could not make that infinite list of $a$ completely explicit. See Theorem 4 in Murty's Math. Intelligencer article on Artin's conjecture for a precise statement, or the original paper of Gupta and Murty here, where you'll see the main result relies on quantitative estimates, but not involving the constant $c_a$ from the quantitative form of Artin's conjecture.

  3. In 1985, Heath-Brown proved that Artin's primitive root conjecture is true for all but at most two prime values of $a$ and all but at most three squarefree $a > 1$. For example, at least one of $2$, $3$, or $5$ is a primitive root mod $p$ infinitely often. Certainly we expect the conjecture is true for every prime value of $a$ and every squarefree value of $a > 1$ with no exceptions at all, but that can't be shown without using GRH as in Hooley's work.

There are a lot of generalizations of the original Artin primitive root conjecture: replace powers of a single integer mod $p$ by powers of a finite set of integers mod $p$ (or a finite set of rational numbers mod $p$, ignoring the finitely many $p$ dividing one of the denominators), by powers of an algebraic integer modulo prime ideals, by multiples of the mod $p$ reductions of a rational point on an elliptic curve over $\mathbf Q$, and so on. Many of these generalizations can be proved using some version of GRH, or weaker versions can be proved without GRH using sieve theory.


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.