MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

If Artin's conjecture on primitive roots is true, then 2 generates $(\mathbb{Z}/p\mathbb{Z})^\times$ for infinitely many primes $p$. Can one at least show that $(\mathbb{Z}/p\mathbb{Z})^\times$ is generated by 2 and 3 for infinitely many primes $p$?

share|cite|improve this question
Hej, I've changed $\mathbb{Z}_p^*$ to $(\mathbb{Z}/p\mathbb{Z})^\times$, because the generally accepted meaning of $\mathbb{Z}_p$ is the $p$-adic integers (though I don't think anyone was confused about what you meant), and because after changing that aspect, the asterisks gave me trouble with the markdown. – Zev Chonoles Jan 28 '11 at 2:07
+1 by the way - neat question. – Zev Chonoles Jan 28 '11 at 2:12
I am going to guess "probably not" - if you can find a prime $p$ and positive integers $j,k$ with $2^{j} \equiv 3^{k} \equiv 1 \, \mathrm{mod} \, p$ and $j*k < p-1$, then you've found a counterexample. – David Hansen Jan 28 '11 at 2:31
Or indeed $\text{lcm}(j,k)<p-1$. But that would only be one counterexample - is there an intuitive reason why we should expect it to occur for all but finitely many primes? – Zev Chonoles Jan 28 '11 at 2:35
@Hej: although your question is quite clear, I think it's natural that people are misreading it (as you mentioned in a comment below). Namely, a primitive root mod p is a generator of (Z/pZ)^*, so it is natural to (mis)read your question as: "Are there infinitely many primes p such that 2 or 3 is a primitive root mod p?" especially if you know about the result of Heath-Brown which is "slightly weaker" than this. You are weakening APR in a somewhat unexpected direction by allowing more than one generator. (Anyway, good question!) – Pete L. Clark Jan 28 '11 at 4:05

I think the best approximation is due to Heath-Brown (Quart. J. Math. Oxford Ser. 37, 27-38.): for infinitely many primes p, one of 2,3,5 is a primitive root mod p.

Actually Heath-Brown's theorem works for any three primes in place of 2,3,5. You can find his paper online here (praise Google).

share|cite|improve this answer
There is also a nice presentation by Murty, "Artin's conjecture for primitive roots", the Mathematical Intelligencer, vol 10 (4) (1988), 59-67. – Andrés E. Caicedo Jan 28 '11 at 1:56
Thank you. I was aware of that result. Maybe my question was not clear. So what I am asking is whether the group generated by 2 and 3 in $\mathbb{Z}_p^*$ is all of $\mathbb{Z}_p^*$. Equivalently, is it true that for infinitely many primes $p$, every number $m$ is congruent to some $2^a3^b$ mod $p$, with $a,b$ natural. – Hej Jan 28 '11 at 1:58
However, $n_1,\ldots,n_k\in\mathbb{Z}$ could still generate $\mathbb{Z}/p\mathbb{Z}^\times$ even if none of them is a primitive root mod $p$. It seems like Hej's question might not require such hard results. – Zev Chonoles Jan 28 '11 at 2:00
Heath-Brown's proof goes by first showing that given three primes, they will generate $(\mathbb{Z}/p)^*$ for infinitely many $p$ and current technology does not allow us to reduce the number of primes to two. His method was inspired by an analogous result of Gupta and Murty on elliptic curves, where you ask if a given set of $m$ rational points (satisfying some obvious necessary condition) generates the group mod $p$ for infinitely many $p$ and this can be proved as long as $m$ is big enough (5 for CM and 8 for non-CM? I forget). The conjecture would be $m=1$, but current tech is not enough. – Felipe Voloch Jan 28 '11 at 2:45
@Felipe: Amusing, I think we were composing our answers at the same time, with more-or-less the same material. – Joe Silverman Jan 28 '11 at 3:03

This is an interesting question. More generally people have considered the following. Let $\Gamma$ be a subgroup of $\mathbf{Q}^*$ generated by $r$ primes. What can one say about $$ N_\Gamma(X)=|\{p < X : \Gamma \bmod p \textrm{ generates } (\mathbf{Z}/p \mathbf{Z})^{\times}\}|. $$

There is also a natural elliptic analogue. Thus let $E/\mathbf{Q}$ be an elliptic curve and let $\Gamma\subset E(\mathbf{Q})$ be a subgroup of rank $r$. Then we can consider $$ N_\Gamma(X)=|\{p < X : \Gamma \bmod p \textrm{ generates } E(\mathbf{Z}/p \mathbf{Z})\}|. $$ Gupta and Murty give a number of results, both conditional and unconditional, in their paper Primitive points on elliptic curves, Compositio Math. 58 (1986), 13–44. For example, if $r\ge6$ and $E$ has complex multiplication, then they prove unconditionally that $N_\Gamma(X)\gg X/(\log X)^2$. In the non-CM case, assuming the GRH, they prove that if $r\ge18$, then $N_\Gamma(X)\gg X/(\log X)$.

It would be interesting to investigate similar questions on higher dimensional algebraic groups, either abelian varieties of dimension $\ge2$, or even on $(\mathbf{Q})^{\times}\times(\mathbf{Q})^{\times}\times\cdots\times(\mathbf{Q})^{\times}$.

share|cite|improve this answer

This is just a comment, but I'm unable to do it, so I post it as an answer:

$2^{11} \equiv 3^{11} \equiv 11 \, \mod 23$.

And a similar situation happens with other primes:

$47, 71, 73, 97, 167, 191, 193, 239, 241, 263, 307, 311, 313, ...$

although not always with $ord_{p}(2)=ord_{p}(3)=\frac{p-1}{2}$.

share|cite|improve this answer
All well and good, but the question is asking for a proof that there are infinitely many primes for which this doesn't happen. – Zev Chonoles Jan 28 '11 at 15:17
Also you mean $2^{11}\equiv 3^{11}\equiv1\bmod 23$ (not 11). – Zev Chonoles Jan 28 '11 at 15:19

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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