# Mersenne numbers

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 .

Pingback: No proof today « Andy Soffer

sorry i’m missing something. why must M_{p_1}, … , M_{p_k} have k different prime factors? wouldn’t pairwise indivisibility by itself allow the list to look something like 3^{k-1}, … , 3^{k-n}4^n, … , 4^{k-1} where there are only 2 prime factors?

You bring up a good point. My mistake. Indeed, we need the stronger result that Mersenne numbers are pairwise RELATIVELY PRIME if their indices are relatively prime (not just that they are indivisible). The proof is virtually the same. If we have some dividing and , it divides their difference, which is for . Since it doesn’t divide (as it must be odd), we have . Repeating this process (essentially the Euclidean algorithm), gives the desired result.