## You are here

Homeproof that there are infinitely many primes using the Mersenne primes

## Primary tabs

# proof that there are infinitely many primes using the Mersenne primes

Like Euclid’s classic proof, this is also a proof by contradiction which starts out from the assumption that there is a largest prime number. But instead of building a primorial or a factorial, a Mersenne number is computed instead.

###### Proof.

Assume that the odd prime $p$ is the largest prime number. Then $2^{p}-1$ is composite, not a Mersenne prime. So what is the integer factorization of $2^{p}-1$? By Fermat’s little theorem we have $2^{{p-1}}\equiv 1\mod p$, doubling that we get $2^{p}\equiv 2\mod p$, therefore $2^{p}-1\mod p$. Since $2^{p}-1$ is composite, it must have at least two prime factors.

If a prime number $q$ is a factor of $2^{p}-1$ (that is, $2^{p}-1\equiv 0\mod q$) then, since $2^{{q-1}}-1\equiv 0\mod q$, assigning $d=\gcd(p,q-1)$, we have $2^{d}-1\equiv 0\mod q$. Then $d$ can not be 1 (for 2 - 1 is not congruent to 0 modulo $q$). Therefore $d=p$ and $q-1$ is multiple of $p$, and thus we derive that $q=np+1$.

Because we stipulated that $p$ is an odd prime and $2^{p}-1$ is also an odd number, $n$ in the formula $np+1$ must be an even number, so we can then set $m=\frac{n}{2}$, giving us the form of the prime factors of $2^{p}-1$ as $2mp+1$.

So now we have to solve for $m$. There must be solutions in the range $0<m<(2^{{p-1}}-1)$. If $m=1$, that gives us $2p+1$ as a prime factor of $2^{p}-1$, but since $(2p+1)>p$ (regardless of which odd prime $p$ is), that also contradicts our first statement that $p$ is the largest prime. With any larger $m$, the number $2mp+1$ is even larger than $p$, and thus our initial statement is contradicted regardless of the primality of $2^{p}-1$. ∎

Two examples to show both scenarios: first, $p=29$ is the largest prime. The corresponding Mersenne number is 536870911, which must be composite. In fact, its factorization, stated in relation to 2 and 29, is $(1+2\times 4\times 29)(1+2\times 19\times 29)(1+2\times 36\times 29)$. Already the least prime factor, 233, is larger than 29, thus 29 can’t be the largest prime.

Second example, $p=31$ is the largest prime. The corresponding Mersenne number is 2147483647, which must be composite. But a search for solutions to $(2mp+1)|(2^{p}-1)$, solving for $m$, yields only two solutions, $m=0$ and $m=2^{{p-1}}-1$, corresponding to 1 and $2^{p}-1$. This means 2147483647 is divisible only by 1 and itself, and is therefore prime, and is in fact a much larger prime than 31.

Note, however, that while this proves there are infinitely many primes, it does not resolve the issue of whether or not there are infinitely many Mersenne primes.

## Mathematics Subject Classification

11A41*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections

## Comments

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

Sorry about that.

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