Mersenne numbers

May 11, 2012 3 Comments

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

About these ads

Filed under Number Theory

3 Responses to Mersenne numbers

Pingback: No proof today « Andy Soffer
Gabor Kittenhuffer Revesz says:

May 19, 2012 at 12:01 pm

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?

Reply
- soffer801 says:
  
  May 19, 2012 at 5:49 pm
  
  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.
  
  Reply