Mersenne numbers

Here’s a very similar proof using Mersenne numbers.

M_n=2^n-1

Notice that if n=ab, then M_n=M_a(1+2^a+2^{2a}+\cdots+2^{(b-1)a}). This tells us that M_b divides M_n whenever b divides n. But even better is that the converse is also true: If n is not divisible by b, then M_n is not divisible by M_b. If it were, then find the largest a for which ab<n. Obviously M_{ab} is divisible by M_b, so the difference M_n-M_{ab} would have to be divisible by M_b. But this is a problem, because:

M_n-M_{ab}=2^n-2^{ab}=2^{ab}M_{n-ab}

Since 2^{ab} has no odd factors other than 1, it must be that M_{n-ab} is divisible by M_b. But n-ab<b by construction, so the divisibility cannot possibly work out.

Great. This was all to show that M_b\mid M_n if and only if b\mid n. So take just take an infinite list M_p where p is a prime.

EDIT: It was pointed out to me that this result is not strong enough. We in fact need that M_a and M_b are relatively prime, if a and b 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 M_p 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 k primes, and look at M_{p_1}, \dots, M_{p_k}. We’ll use the list to produce a new prime. This list of numbers has at least k primes in the prime factorizations of the numbers. If it doesn’t contain all the primes p_1,\dots, p_k, then there is some new prime q which is not one of the p_i. This means that there is a next prime p_{k+1}. 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 M_{p_1} is just some prime power. This verifiably false, because M_{11}=23\cdot89.

Advertisements

3 Responses to Mersenne numbers

  1. Pingback: No proof today « Andy Soffer

  2. 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?

    • soffer801 says:

      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 p dividing M_a and M_b, it divides their difference, which is M_a-M_b=2^b\cdot M_{a-b} for a>b. Since it doesn’t divide 2^b (as it must be odd), we have p\mid M_{a-b}. Repeating this process (essentially the Euclidean algorithm), gives the desired result.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s