Mersenne Primer

What is a Mersenne prime?

A Mersenne prime is a prime number (a number divisible only by itself and 1) of the form 2^n-1; for instance, 7 = 2^3-1. They are named for Marin Mersenne, who investigated prime numbers, especially of this form.

Not all numbers of the form 2^n-1 are prime; actually they are quite rare. For starters, for 2^n-1 to be prime, 'n' must be prime. For this reason you will usually see the form written as 2^p-1, where 'p' is a prime number. Even so, most numbers of the form 2^p-1 are still not prime. They are known as Mersenne numbers, and only called Mersenne primes if they are prime. Both are sometimes represented as 'Mp'.

Mersenne primes and perfect numbers

A perfect number is a number that is equal to the sum of its factors, provided you count '1' as a factor but not the number itself. Why is that? I don't know, you'd have to ask the ancient Greeks. Probably because if you don't use that definition then there are no perfect numbers.

Now it just so happens that all known perfect numbers are of the form (2^p-1)*2^(p-1). The first two are 6 (=1+2+3) and 28 (=1+2+4+7+14). They are given by the formula for p = 2 and p = 3. You may have noticed that the first half of that formula is the form of a Mersenne prime. It also holds true that the number given by the formula will not be a perfect number unless 2^p-1 is prime. There's a good reason for that.

Let's look again at that perfect number formula. It's always a Mersenne number times a power of 2. Let's let n = p-1, so that can be rewritten as "Mp * 2^n". The factors of 2^n are [1, 2, 4, 8,... 2^(n-1), 2^(n)], which add up to 2^(n+1)-1. So the factors of our alleged perfect number (Mp*2^n) will contain those powers of 2, plus Mp, plus Mp times powers of 2 up to 2^(n-1). (We can't count Mp times 2^n because that is the number itself.) Now the sum of Mp times powers of two from 1 to 2^(n-1) is Mp*(2^n-1).

That covers all the factors of our alleged perfect number, provided that Mp is itself prime. The 'power of 2' factors add up to 2^(n+1)-1. But since n = p-1, this is equal to 2^p-1, which is Mp. The second set of factors add up to Mp*(2^n-1), and when we add the first set (Mp) that gives us a total of Mp*(2^n). Once again, since n = p-1 and Mp = 2^p-1, that gives us (2^p-1)*2^(p-1), which is our starting number. Perfect!

So what happens when 2^p-1 is not prime? Simplest example is when p=4, and the formula gives us (2^4-1)*(2^3), or 15*8, which is 120. The 2^x factors are [1,2,4,8] and the 15*2^x factors are [15,30,60], and these factors do indeed add up to 120. But since 15 isn't prime, there are other factors like 3, 5, and multiples thereof.

"Hey, you can't let p = 4; 4 isn't prime!"

OK, make things more difficult then. Eleven is prime, we'll use that. (2^11-1)*(2^10) = 2047*1048 = 2096128. The 2^x factors are [1,2,4,8,16,32,64,128,256,512,1024] and the 2047*2^x factors are [2047,4094,8188,16376,32752,65504,131008,262016,524032,1048064] which do add up to 2096128. But since 2047 = 23 * 89, there are other factors as well.

BTW, did you notice that the factors of 2^11-1 are 2*11+1 and 8*11+1? Turns out that if 2^p-1 is not prime, then its factors will always be of the form 2kp+1 (including 1 and 2^p-1 itself, so that actually holds true even if it IS prime). It does not hold true for 2^n-1 where n is not prime. If n is even, then 2^n-1 = (2^(n/2)-1) * (2^(n/2)+1).

Why look for more Mersenne primes?

Same reason people keep climbing higher mountains... because they're there! (At least we hope so!)


Back