May 11, 2012 3 Comments
Here’s a very similar proof using Mersenne numbers.
Notice that if , then . This tells us that divides whenever divides . But even better is that the converse is also true: If is not divisible by , then is not divisible by . If it were, then find the largest for which . Obviously is divisible by , so the difference would have to be divisible by . But this is a problem, because:
Since has no odd factors other than , it must be that is divisible by . But by construction, so the divisibility cannot possibly work out.
Great. This was all to show that if and only if . So take just take an infinite list where is a prime.
EDIT: It was pointed out to me that this result is not strong enough. We in fact need that and are relatively prime, if and are relatively prime. See the comments below.
If you’re perplexed at this point, you have a right to be. How do I know the list of is infinite? Doesn’t that exactly mean there are infinitely many primes? I can’t assume that! True, but there’s a cool work-around.
Take the first primes, and look at . We’ll use the list to produce a new prime. This list of numbers has at least primes in the prime factorizations of the numbers. If it doesn’t contain all the primes , then there is some new prime which is not one of the . This means that there is a next prime . If it does contain all of them, look to see if it happens to have another prime. If it does, again, we win. Otherwise, each is just some prime power. This verifiably false, because .