The multiplicative order of 2 modulo primes - MathOverflow

The multiplicative order of 2 modulo primes

2011-04-03T15:10:33Z

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.

Answer by Charles Matthews for The multiplicative order of 2 modulo primes

2011-04-03T16:08:06Z

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

Answer by GH for The multiplicative order of 2 modulo primes

2011-04-03T16:15:43Z

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

Answer by DavidLHarden for The multiplicative order of 2 modulo primes

2011-04-04T00:26:31Z

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

Answer by BenJammin for The multiplicative order of 2 modulo primes

2012-11-21T22:50:34Z

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$