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.
Assume that the odd prime is the largest prime number. Then is composite, not a Mersenne prime. So what is the integer factorization of ? By Fermat’s little theorem we have , doubling that we get , therefore . Since is composite, it must have at least two prime factors.
So now we have to solve for . There must be solutions in the range . If , that gives us as a prime factor of , but since (regardless of which odd prime is), that also contradicts our first statement that is the largest prime. With any larger , the number is even larger than , and thus our initial statement is contradicted regardless of the primality of . ∎
Two examples to show both scenarios: first, 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 . Already the least prime factor, 233, is larger than 29, thus 29 can’t be the largest prime.
Second example, is the largest prime. The corresponding Mersenne number is 2147483647, which must be composite. But a search for solutions to , solving for , yields only two solutions, and , corresponding to 1 and . 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|
|Date of creation||2013-03-22 18:05:14|
|Last modified on||2013-03-22 18:05:14|
|Last modified by||PrimeFan (13766)|