18
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ 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). $\endgroup$
    – Greg Marks
    Commented Apr 4, 2011 at 1:41

3 Answers 3

Reset to default
18
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ It would be useful if you gave the journal data for the papers you mentioned. $\endgroup$
    – GH from MO
    Commented Apr 3, 2011 at 16:21
  • 1
    $\begingroup$ 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. $\endgroup$
    – Andreas Thom
    Commented Apr 3, 2011 at 16:22
  • 1
    $\begingroup$ Here is a link with no access restrictions: citeseerx.ist.psu.edu/viewdoc/… $\endgroup$
    – Andreas Thom
    Commented Apr 3, 2011 at 16:27
  • $\begingroup$ @Andreas: Thanks - as usual I was doing something else in another tab. $\endgroup$
    – Charles Matthews
    Commented Apr 3, 2011 at 16:39
  • 3
    $\begingroup$ 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. $\endgroup$
    – Joe Silverman
    Commented Apr 3, 2011 at 22:55
6
$\begingroup$

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

Improve this answer
$\endgroup$
0
0
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ What about cubes? $\endgroup$
    – Dror Speiser
    Commented Apr 4, 2011 at 15:07
  • $\begingroup$ I guess, cubes are not a problem, since 3 does not divide p−1 for too many primes, whereas 2 does. $\endgroup$
    – Andreas Thom
    Commented Apr 5, 2011 at 2:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .