PlanetMath: proof that there are infinitely many primes using the Mersenne primes

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$ . $\qedsymbol$

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.