## The multiplicative order of 2 modulo primes

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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

• Heath-Brown, D.R. (1986). "Artin's conjecture for primitive roots." Quart. J. Math. Oxford Ser. 37(1), 27-38.

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.

-
The first link--"Artin's Conjecture"--seems to be broken! – drbobmeister Apr 3 2011 at 15:56
Thanks. I fixed the link. – Andreas Thom Apr 3 2011 at 16:12

1
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 2011 at 1:41

## 4 Answers

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 Apr 3 2011 at 16:21

1
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 2011 at 16:22

1
Here is a link with no access restrictions: citeseerx.ist.psu.edu/viewdoc/… – Andreas Thom Apr 3 2011 at 16:27
@Andreas: Thanks - as usual I was doing something else in another tab. – Charles Matthews Apr 3 2011 at 16:39

3
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 2011 at 22:55

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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

-

Thanks a lot. I was aware of this lower bound. – Andreas Thom Apr 3 2011 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$.

-

Thanks for the correction. – Andreas Thom Apr 4 2011 at 3:58
What about cubes? – Dror Speiser Apr 4 2011 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 2011 at 2:35

I am not sure if this was in Charles' answer. I couldn't really follow what was being said in the link. If it is I apologise. Here is what I found in the most exciting 2 weeks of my undergraduate so far. Hence why I am eager to share :-)

So we are looking for the minimal $x$ such that $2^x \equiv 1 \mod p, \quad p \quad \text{prime}$. I only managed to get a few cases depending on the nature of $p$.

$$(1) \quad p = 2^k-1 \Rightarrow x = k$$

$$(2) \quad p = 2^k+1 \Rightarrow x = 2k$$

$$(3) \quad p = 2q+1 \quad \text{and $\quad q \equiv 3 \mod 4,\quad q$ prime } \Rightarrow x = q$$

$$(4) \quad p = 4k+3, \quad p \not\equiv \pm 1 \mod 8 \Rightarrow x = p-1$$

$(1)$ is trivial.

$(2)$ follows from the fact that $2^k \equiv -1 \mod p$ then just squaring.

$(3)$ is basically just the statement of a theorem Mersenne Primes Theorem number 7.

$(4)$ follows from the fact that $c^2 \equiv 2 \mod p$ is solvable iff $p \equiv \pm 1 \mod 8$. Clearly $2^{p-1} \equiv 1$ so the question is what is $2^{\frac{p-1}{2}}$ congruent to. If $p = 4k+3$ then $\frac{p-1}{2} = 2k+1$. So if we assume that:

$$2^{\frac{p-1}{2}} \equiv 1 \mod p$$ then for some $d$ $$2^{\frac{p-1}{2}+1}= (2^d)^2 \equiv 2 \mod p$$ Therefore $2^d$ is a solution to $c^2 \equiv 2 \mod p$ but by assumption $p \not\equiv \pm 1 \mod 8$ so we have a contradiction and thus $2^{\frac{p-1}{2}} \equiv -1 \mod p$ and so $x = p-1$

-

1
Sorry, but (4) is false : for example $p=43$ gives $x=14$. – François Brunault Nov 21 at 23:06
Proving that $2^{(p-1)/2} \not\equiv1\pmod p$ is not enough to show that the order of $2$ equals $p-1$; you would have to prove that $2^{(p-1)/q} \not\equiv 1\pmod p$ for every $q$ dividing $p-1$. That's the error in the argument of (4). – Greg Martin Nov 22 at 8:29
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 41, "mathjax_display_tex": 6, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9242205023765564, "perplexity_flag": "head"}