The multiplicative order of 2 modulo primes - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T06:40:09Z http://mathoverflow.net/feeds/question/60441 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/60441/the-multiplicative-order-of-2-modulo-primes The multiplicative order of 2 modulo primes Andreas Thom 2011-04-03T15:10:33Z 2012-11-21T22:50:34Z <p><a href="http://en.wikipedia.org/wiki/Artin%27s_conjecture_on_primitive_roots" rel="nofollow">Artin's Conjecture</a> says that any positive integer, which is not a square, is a primitive root modulo infinitely many primes. Christopher Hooley gave in</p> <ul> <li>Hooley, Christopher (1967). "<em>On Artin's conjecture.</em>" J. Reine Angew. Math. 225, 209-220.</li> </ul> <p>a proof of this conjecture assuming the Generalized Riemann Hypothesis.</p> <p>Roger Heath-Brown showed (not using the GRH) in</p> <ul> <li>Heath-Brown, D.R. (1986). "<em><a href="http://qjmath.oxfordjournals.org/content/37/1/27.extract" rel="nofollow">Artin's conjecture for primitive roots.</a></em>" Quart. J. Math. Oxford Ser. 37(1), 27-38.</li> </ul> <p>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.</p> <blockquote> <p><strong>Question:</strong> What is known about the multiplicative order of 2 modulo primes?</p> </blockquote> <p>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$)?</p> <p>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.</p> http://mathoverflow.net/questions/60441/the-multiplicative-order-of-2-modulo-primes/60444#60444 Answer by Charles Matthews for The multiplicative order of 2 modulo primes Charles Matthews 2011-04-03T16:08:06Z 2011-04-03T16:38:15Z <p>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).</p> http://mathoverflow.net/questions/60441/the-multiplicative-order-of-2-modulo-primes/60445#60445 Answer by GH for The multiplicative order of 2 modulo primes GH 2011-04-03T16:15:43Z 2011-04-03T16:15:43Z <p>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$. </p> http://mathoverflow.net/questions/60441/the-multiplicative-order-of-2-modulo-primes/60508#60508 Answer by DavidLHarden for The multiplicative order of 2 modulo primes DavidLHarden 2011-04-04T00:26:31Z 2011-04-04T00:26:31Z <p>A small correction regarding Artin's conjecture is in order: it doesn't just exclude squares. You also need to exclude $-1$.</p> http://mathoverflow.net/questions/60441/the-multiplicative-order-of-2-modulo-primes/114114#114114 Answer by BenJammin for The multiplicative order of 2 modulo primes BenJammin 2012-11-21T22:50:34Z 2012-11-21T22:50:34Z <p>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 :-)</p> <p>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$.</p> <p>$$(1) \quad p = 2^k-1 \Rightarrow x = k$$</p> <p>$$(2) \quad p = 2^k+1 \Rightarrow x = 2k$$</p> <p>$$(3) \quad p = 2q+1 \quad \text{and \quad q \equiv 3 \mod 4,\quad q prime } \Rightarrow x = q$$</p> <p>$$(4) \quad p = 4k+3, \quad p \not\equiv \pm 1 \mod 8 \Rightarrow x = p-1$$</p> <p>$(1)$ is trivial. </p> <p>$(2)$ follows from the fact that $2^k \equiv -1 \mod p$ then just squaring. </p> <p>$(3)$ is basically just the statement of a theorem <a href="http://en.wikipedia.org/wiki/Mersenne_prime" rel="nofollow">Mersenne Primes Theorem number 7</a>. </p> <p>$(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:</p> <p>$$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$</p>