Welcome to MathOverflow

Question

5

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

flag	asked Nov 10 at 15:22 Oliver Kayende 85●2

8

The first counterexample is $p=1093$. See en.wikipedia.org/wiki/Wieferich_prime – François Brunault Nov 10 at 16:10

1

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. – quid Nov 10 at 18:34

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). – GH Nov 10 at 19:33

1

Related to an old (rather feeble!) question of mine: mathoverflow.net/questions/27579/… – David Loeffler Nov 11 at 9:10

Geoff Robinson · Accepted Answer · 2012-11-11 11:21:22Z UTC

9

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

edited Nov 11 at 11:21

answered Nov 10 at 16:23

Geoff Robinson
9,856●1●21●27

	And 3511 is the second smallest and, for all we know, also the largest such prime. oeis.org/A000793 – Gerry Myerson Nov 11 at 23:00
	Oh, I did not realise that only two such primes were known for sure to exist at present. – Geoff Robinson Nov 11 at 23:49
	@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. – quid Nov 12 at 20:32
	@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. – Gerry Myerson Nov 22 at 22:11

M Khan · Answer 2 · 2012-11-10 15:43:34Z UTC

0

No. Just look at p=3. Just look at the proof of the existence of primitive roots for prime powers --- if r is a primitive root mod p, then either r or r+p is a primitive root for all prime powers.

All of this routine in an introductory course in number theory, and so your question is not appropriate for this forum.

answered Nov 10 at 15:43

M Khan
17●1

8

I do not understand this answer. What does p=3 tell? The multiplicative order of 2 modulo 3 is 2. The multiplicative order of 2 modulo 9 is 6. So it is strictly smaller for p than for p^2 in this case. – quid Nov 10 at 15:52

3

@quid: did you look at it? – Dror Speiser Nov 10 at 18:09

1

@Dror Speiser: I am not completely sure if there is a subtle message, if so I missed it, but actually I assume you are somehow joking, which is fine. Generally, why does this answer get yet another upvote?! It seems clearly based on misunderstanding the question. – quid Nov 11 at 13:56

@quid: I think Dror meant that we are supposed to look at $p=3$ (with wide open eyes). – GH Nov 12 at 11:00

1

I found the double use of "just look at" amusing, especially with the answer being a bit off, and thought others might too. Now that I have explained, I am even more confident of my ever sharp wit. – Dror Speiser Nov 14 at 4:55

multiplicative order of 2 mod p

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

2 Answers

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.