proof that there are infinitely many primes using the Mersenne primes

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


Assume that the odd prime p is the largest prime number. Then 2p-1 is composite, not a Mersenne prime. So what is the integer factorization of 2p-1? By Fermat’s little theorem we have 2p-11modp, doubling that we get 2p2modp, therefore 2p-1modp. Since 2p-1 is composite, it must have at least two prime factorsMathworldPlanetmath.

If a prime number q is a factor of 2p-1 (that is, 2p-10modq) then, since 2q-1-10modq, assigning d=gcd(p,q-1), we have 2d-10modq. Then d can not be 1 (for 2 - 1 is not congruentMathworldPlanetmath to 0 modulo q). Therefore d=p and q-1 is multipleMathworldPlanetmath of p, and thus we derive that q=np+1.

Because we stipulated that p is an odd prime and 2p-1 is also an odd numberMathworldPlanetmathPlanetmath, n in the formulaMathworldPlanetmathPlanetmath np+1 must be an even number, so we can then set m=n2, giving us the form of the prime factors of 2p-1 as 2mp+1.

So now we have to solve for m. There must be solutions in the range 0<m<(2p-1-1). If m=1, that gives us 2p+1 as a prime factor of 2p-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 2p-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 relationMathworldPlanetmath to 2 and 29, is (1+2×4×29)(1+2×19×29)(1+2×36×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)|(2p-1), solving for m, yields only two solutions, m=0 and m=2p-1-1, corresponding to 1 and 2p-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.

Title proof that there are infinitely many primes using the Mersenne primes
Canonical name ProofThatThereAreInfinitelyManyPrimesUsingTheMersennePrimes
Date of creation 2013-03-22 18:05:14
Last modified on 2013-03-22 18:05:14
Owner PrimeFan (13766)
Last modified by PrimeFan (13766)
Numerical id 7
Author PrimeFan (13766)
Entry type Proof
Classification msc 11A41