# The multiplicative order of 2 modulo primes

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.

• 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

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).

• 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 blms.oxfordjournals.org/content/14/2/149 to your paper from 1982. – Andreas Thom Apr 3 '11 at 16:22
• Here is a link with no access restrictions: citeseerx.ist.psu.edu/viewdoc/… – 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$.

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

• 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