Mersenne numbers, named after Marin Mersenne, are numbers of the form . The first few Mersenne numbers are therefore , , , , , and so on. Mersenne numbers come up all the time in computer science (for example, is the largest number which can be represented as a binary number with bits, since ).
Last week was my birthday, and my age is now a Mersenne number! More excitingly, my age is a Mersenne number which is also prime. Prime Mersenne numbers are usually just called “Mersenne primes”, and they are of interest because it is much easier to test whether a given Mersenne number is prime than it is to test other, arbitrary numbers of the same size. This is the basis of the Great Internet Mersenne Prime Search, which I’ve written about on several occasions in the past (here, here, here, and here). The largest known prime is a Mersenne prime, namely (as of the time of this writing) .
I’d like to explain how this actually works. Testing whether a Mersenne number is prime can be done using the LucasLehmer test, named after its discoverers. Understanding how to carry out the LucasLehmer test is actually incredibly simple, and I explain how it works below. Understanding why it works is more difficult, but I’ll try to explain (at least one direction of) the proof in a future post.
The LucasLehmer test
The first thing to note is that if a Mersenne number is to have any chance of being prime, itself had better be prime too. In other words, if is composite, then so is . Why is that? Well, I’ll let you think about it, and reveal the solution in a future post. If you want a hint, there’s one at the end of this post.
You could be forgiven for thinking that the converse might be true as well: that is, if is prime then so is . After all, , , , and are all prime. However, the next in the sequence fails: is not prime even though is.
So, if we have a prime number , then has a chance of being prime but it’s not guaranteed. How can we check? Here’s where the LucasLehmer test comes in. It works like this: define , and for define . For example, when , we have
Finally, is prime if and only if . ^{1} That’s all! Here’s some Haskell code:
>  A boring, dumb, slow, but obviously correct primality test: try
>  dividing by 2 and by every odd number up to half the chosen number.
> isPrime :: Integer > Bool
> isPrime 2 = True
> isPrime n = all (\d > n `mod` d /= 0) (2 : [3, 5 .. n `div` 2])
>
>  Use the LucasLehmer test to see whether 2^p  1 is prime.
> lucasLehmer :: Integer > Bool
> lucasLehmer 2 = True
> lucasLehmer p = isPrime p && s (p2) == 0
> where
> mp = 2^p  1
> s 0 = 4
> s n = let s' = s (n1) in (s'*s'  2) `mod` mp
There are various tricks you can use to speed this up (for example, finding the remainder mod can be done using some simple operations on binary numbers instead of actually doing division), but this is the basic idea. If you sign your computer up for GIMPS, this is what it’s computing!
Using the above code I can quickly (in a fraction of a second on my computer) find the exponents of all ten Mersenne primes smaller than :
ghci> filter lucasLehmer [2..100]
[2,3,5,7,13,17,19,31,61,89]
Note that the largest Mersenne prime represented here, , is already pretty big! Testing whether this number is prime using the dumb isPrime
algorithm would take like a trillion bazillion years.
Even using LucasLehmer, testing numbers as big as is not trivial either. We have to compute which requires doing the operation fortythree million times. Since we take the remainder mod at each step, the numbers involved will never get bigger than that, but that’s quite big enough—we’re talking about numbers that take about five megabytes to store! Usually when we say “five megabytes” we are thinking about really big images, or YouTube videos, but here we are talking about individual integers! So, you take a fivemegabyte number, square it to get a tenmegabyte number, subtract two, reduce the result mod —and then repeat 43 million times! Doing this requires many, many hours of computer time, even on the fastest modern computers. But the point is that it’s not even possible to contemplate doing this using a more bruteforce method.
OK, that’s pretty cool, but why does it work? In a subsequent post or three I hope to present (at least a sketch of) a proof that if then is prime.
A hint
Earlier, I posed the challenge of explaining why is composite if is composite. Here’s a hint (don’t read this unless you want a hint!): if is composite, then it’s possible to find another Mersenne number which divides .

Actually, this only works when , but that’s OK, we already know about !↩
I solved for an equation that shows why the Mersenne number of a composite number must also be composite, but in looking at the factors of Mersenne numbers I noticed something that isn’t obvious from my equation, and I’m not sure if it holds for all Mersenne numbers or just the small ones that I tested.
***STOP reading if you don’t want any HINTS!***
Okay, my equation shows that if is any factor of then is a factor of which is sufficient to show that is not prime. However, what I noticed was that it seems if are distinct prime factors of then can be factored from . Do you know if this is always true? With my equation it is obvious for any such that all are also prime or share no prime factors. I’m just not sure that two composite Mersenne numbers from two different primes wouldn’t share a prime factor that wasn’t repeated in the Mersenne number of their product.
I look forward to your future posts on the topic.
Good question! I don’t know.
Is it too much of a hint to say “think in binary”?
Here’s another hint. The decimal expansion of 1/p is periodic, a multiple of some number like 0.000100010001… where the number of 0’s between each 1 is one less than the period. That number is 1/999…9 for some number of 9’s. So 999…9/p is an integer: the repeating digit block in the decimal expansion. This means that every prime except 2 and 5 is a prime factor of for some n, and all its multiples.
What is the equivalent for binary representation?