Fork me on GitHub
Math for the people, by the people.

User login

proof that there are infinitely many primes using the Mersenne primes

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

Mathematics Subject Classification

11A41 no label found

Comments

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.

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.

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

>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

Sorry about that.

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.

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.

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.

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.

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

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

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.

Subscribe to Comments for "proof that there are infinitely many primes using the Mersenne primes"