proof that there are infinitely many primes using the Mersenne primes

Primary tabs

Major Section:
Reference
Type of Math Object:
Proof
Parent:

Mathematics Subject Classification

A litle gap in your proof?

I don't understand how you prove that any prime factor of 2^p-1 is of the form 2mp+1, I know it is true but it does not follow from the fact that 2^p-1=1 mod p because 21=1 mod 5 although none of its factors are congruent with 1 mod 5.
I would try in this way. If q is a factor of 2^p-1 (i.e. 2^p-1 = 0 mod q) then, since 2^{q-1}-1 = 0 mod q, 2^d-1 = 0 mod q, where d is the greatest common divisor of p and q-1. Since d can not be 1 (2-1 is congruent to 0 mod q) then d=p and q-1 is multiple of p (i.e. p=np+1).

And the second paragraph could much shorter: if 2^p-1 is greater than 1 then has a factor greater than 1 which, by being the form 2mp+1, will be greater than p.

Re: A litle gap in your proof?

I was about to say the same thing. I was reading it, it was all making sense, next thing I know, I'm backtracking thinking I missed where he proves the factors 2^p - 1 HAVE to be of that form 2np + 1. It is a gap. The way Crandall and Pomerance prove it (in that book PrimeFan calls "the bible of prime numbers") is by referring to finite groups, but here something a little more elementary, such as the way you suggest, would be more appropriate, imho.

Re: A litle gap in your proof?

> I would try in this way. If q is a factor of 2^p-1 (i.e. 2^p-1 = 0 mod q) then, since 2^{q-1}-1 = 0 mod q, 2^d-1 = 0 mod q, where d is the greatest common divisor of p and q-1. Since d can not be 1 (2-1 is congruent to 0 mod q) then d=p and q-1 is multiple of p (i.e. _q_ =np+1).

So if 23 is a factor of 2^11 - 1 = 2047 (i.e., 2047 = 0 mod 23) then, since 2^22 - 1 = 0 mod 23, then 2^d - 1 = 0 mod 23, where d is the gcd of 11 and 22. Since d can not be 1 (2 - 1 = 0 mod 23) then d = 11 and 23 - 1 = 22 is a multiple of 11 (i.e., 23 = 2 * 11 + 1). I think this checks out.

But I worry it might be too simple. Why didn't C & P include it in their book? They don't strike me as the kind of people who need to refer to groups or concepts like that in order to impress anyone.

Re: A litle gap in your proof?

>Since d can not be 1 (2-1 is congruent to 0 mod q)

I mean: Since d can not be 1 (2-1 is NOT congruent to 0 mod q)

>And the second paragraph could much shorter

I mean: And the second paragraph could much BE shorter

Re: A litle gap in your proof?

I don't know... I think there is still an unexplained jump somewhere in there. The numerical example you give checks out, but... how do you explain that it doesn't work at all when the index of the Mersenne number is composite? e.g., 2^4 - 1 = 15 = 3 x 5, and only the latter factor is congruent to 1 mod the index.

Re: A litle gap in your proof?

When you take a composite index k (like your example k=4) there is no reason to g.c.d.(q-1,k)=k for any prime factor q of 2^k-1.

Re: A litle gap in your proof?

It wasn't until today that I logged in again after the Memorial Day weekend. So I'm feeling a little rushed in reading all the messages on this topic and I have to admit that while I acknowledge there is a gap in the proof, I'm having trouble understanding the proposed elementary way to prove that the factors of 2^p - 1 must be congruent to 1 mod p. It's easy enough to show they can't be congruent to anything other than -1 or +1 and that's actually sufficient for the purpose here. But I still want to understand how to rule out -1, so I'll continue to ponder this and reread the messages.

error not fixed

Sorry but xy=1 mod p doesn't imply x=y=1 or x=y=-1 as it shows the following example: 3*4=1 mod 11.

Re: error not fixed: so hard to prove 2mp+1 divides 2^p-1

>Sorry but xy=1 mod p doesn't imply x=y=1 or x=y=-1 as it shows the following example: 3*4=1 mod 11.

This is the beauty of dealing with actual numbers. Mistakes can be identified and corrected. No one dares correct CyclotomicQ about transfinite Lamarckian trundles because no one can even _tell_ if he made a mistake!

lynx is right, 3*4=1 mod 11. But while 3 can theoretically be a factor of 2047, 4 must be rejected out of hand. I would suggest to PrimeFan changing the congruence to modulo 2p, then all the potential even factors are easily dismissed. But then lynx would point out that 3*15=1 mod 22. Then I would say but 3 and 15 are not both prime nor even pairwise coprime. And then I don't know what lynx would say after that. But it doesn't have to be lynx, it could be anyone.

Re: error not fixed: so hard to prove 2mp+1 divides 2^p-1

What I don't understand is why PrimeFan didn't just use the way lynx first suggested:

> I would try in this way. If q is a factor of 2^p-1 (i.e. 2^p-1 = 0 mod q) then, since 2^{q-1}-1 = 0 mod q, 2^d-1 = 0 mod q, where d is the greatest common divisor of p and q-1. Since d can not be 1 (2-1 is congruent to 0 mod q) then d=p and q-1 is multiple of p (i.e. p=np+1).

Both he and I have said that we can't find any holes in it, but the path PrimeFan chose to down is full of potholes ;-)

Re: error not fixed: so hard to prove 2mp+1 divides 2^p-1

I didn't just want to copy what lynx wrote, just as I didn't just want to copy Crandall & Pomerance.

I still can't find any holes with lynx's reasoning. But then again, I didn't see the gap in my first draft until it was pointed out to me.