6
$\begingroup$

Can anyone tell me whether or not it is true that for all odd primes p the multiplicative order of 2 modulo p is strictly less than the multiplicative order of 2 modulo p^2 ? What are some good references regarding this problem ? Thank you

$\endgroup$
4
  • 10
    $\begingroup$ The first counterexample is $p=1093$. See en.wikipedia.org/wiki/Wieferich_prime $\endgroup$ Nov 10, 2012 at 16:10
  • 1
    $\begingroup$ I am a bit surprised this gets ever more votes to close (four already). In my opinion this is an alright question. Could someone at least say why they want this to be closed. $\endgroup$
    – user9072
    Nov 10, 2012 at 18:34
  • $\begingroup$ I think people voted against this question, because it is easily equivalent to a question that is discussed in introductory textbooks (e.g. Hardy-Wright, Ireland-Rosen, Nathanson). $\endgroup$
    – GH from MO
    Nov 10, 2012 at 19:33
  • 1
    $\begingroup$ Related to an old (rather feeble!) question of mine: mathoverflow.net/questions/27579/… $\endgroup$ Nov 11, 2012 at 9:10

1 Answer 1

10
$\begingroup$

It is well-known that there are primes $p$ such that $2^{p-1} \equiv 1$ (mod $p^{2}$), a question which arises in connection with Fermat's Last Theorem. For such a prime $p,$ let $e$ be the smallest positive integer such that $p$ divides $2^{e}-1,$ and write (as we may) $p-1 = ed$ with $d$ an integer. Then we see easily that $2^{p-1}-1 \equiv d(2^{e}-1)$ (mod $p^{2}$). Certainly $d$ is not divisible by $p,$ so we must already have $2^{e} \equiv 1$ (mod $p^{2}$). Hence for such a prime $p,$ the multiplicative order of $2$ (mod $p$) is the same as the multiplicative order of $2$ mod $p^{2}.$ I see in the meantime that Francois Brunault has made a comment to similar effect, and that $1093$ is the smallest such prime

$\endgroup$
4
  • 1
    $\begingroup$ And 3511 is the second smallest and, for all we know, also the largest such prime. oeis.org/A000793 $\endgroup$ Nov 11, 2012 at 23:00
  • $\begingroup$ Oh, I did not realise that only two such primes were known for sure to exist at present. $\endgroup$ Nov 11, 2012 at 23:49
  • $\begingroup$ @Gerry Myerson: I guess you meant to link to this sequence oeis.org/A001220 instead. Furthermore, I am not sure perhaps you mean this anyway but 'the largest' is confusing for me, it is the largest known at the moment but AFAIK the expectation is there are infinitely many (count growing like about log log x); the heuristic being that 2^(p-1) has p possible values mod p^2 and one is 'good' so pob 1/p; and sum 1/p diverges like log log x. $\endgroup$
    – user9072
    Nov 12, 2012 at 20:32
  • $\begingroup$ @quid, thanks for providing the correct link. When I wrote "for all we know, the largest such prime," I meant two things: first, that we don't know any larger such primes, and, second, that we don't have a proof that larger primes of the type exist. I don't deny that the expectation is that there are infinitely many. $\endgroup$ Nov 22, 2012 at 22:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.