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

Artin's Conjecture says that any positive integer, which is not a square, is a primitive root modulo infinitely many primes. Christopher Hooley gave in

  • Hooley, Christopher (1967). "On Artin's conjecture." J. Reine Angew. Math. 225, 209-220.

a proof of this conjecture assuming the Generalized Riemann Hypothesis.

Roger Heath-Brown showed (not using the GRH) in

that there are at most two primes for which Artin's Conjecture fails. Nevertheless, it seems to be unknown whether any single specific prime number satisfies the conjecture. In particular, it is unknown if 2 is a primitive root modulo infinitely many primes.

Question: What is known about the multiplicative order of 2 modulo primes?

More specifically, can one prove interesting statements of the form: For infinitely many primes $p$, the multiplicative order of 2 is larger than some expression in terms of $p$ (which goes to infinity as $p \to \infty$)?

I have to say, that I am not an expert on these kind of questions at all. Given the enormous amount of literature on these questions, I tag this as a reference-request.

share|cite|improve this question
Simple but amusing application: that multiplicative order is the minimal number of perfect shuffles required to restore a deck of $p \pm 1$ cards (the $\pm$ depending on which of the two ways of perfectly shuffling we're talking about). – Greg Marks Apr 4 '11 at 1:41
up vote 15 down vote accepted

The answer is "yes" - the order mod p of 2 is almost always as large as the square root of p (actually you get epsilon less than this in the exponent). If you take r multiplicatively independent numbers and ask for the group they generate mod p, the exponent is r/(r + 1). This is a paper of mine, and then in a paper of the Murtys, and I think is referenced in some form by Heath-Brown (it is the less deep part of his technique - to get something serious out of it you need something like Chen's method for Goldbach).

share|cite|improve this answer
It would be useful if you gave the journal data for the papers you mentioned. – GH from MO Apr 3 '11 at 16:21
Thanks a lot, this answers the question very nicely. I add the link to your paper from 1982. – Andreas Thom Apr 3 '11 at 16:22
Here is a link with no access restrictions:… – Andreas Thom Apr 3 '11 at 16:27
@Andreas: Thanks - as usual I was doing something else in another tab. – Charles Matthews Apr 3 '11 at 16:39
Mike Rosen, Ram Murty, and I wrote a paper on a series that can be used to estimate the average (in some sense) order of t modulo p, and more generally for finitely generated subgroups as in Charles' paper. We also covered finitely generated subgroups of abelian varieties, where the exponent turns out instead to be r/(r+2), due to the quadratic nature of the height. Here's the reference: Variations on a theme of Romanoff, Inter. J. Math. 7 1996, 373-391. – Joe Silverman Apr 3 '11 at 22:55

Just an easy low tech answer: the multiplicative order of 2 modulo $p$ is at least $\log_2 p$, hence tends to infinity with $p$. Indeed, if $r$ is the order, then $2^r-1$ is divisible by $p$, hence $2^r\geq p+1$.

share|cite|improve this answer
Thanks a lot. I was aware of this lower bound. – Andreas Thom Apr 3 '11 at 16:23

A small correction regarding Artin's conjecture is in order: it doesn't just exclude squares. You also need to exclude $-1$.

share|cite|improve this answer
Thanks for the correction. – Andreas Thom Apr 4 '11 at 3:58
What about cubes? – Dror Speiser Apr 4 '11 at 15:07
I guess, cubes are not a problem, since 3 does not divide p−1 for too many primes, whereas 2 does. – Andreas Thom Apr 5 '11 at 2:35

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.