Mersenne primes

One less than a power of two

Take a power of two and subtract one. Sometimes the result is prime, and when it is, we call it a Mersenne prime. The first few are 3 (that's 2² − 1), 7 (2³ − 1), 31 (2⁵ − 1) and 127 (2⁷ − 1).

There's a neat rule about the exponent up top. For 2ⁿ − 1 to have any chance of being prime, n itself must be prime. If n splits into factors, so does 2ⁿ − 1 — so the hunt only ever looks at prime exponents. Notice the powers above: 2, 3, 5, 7 are all primes.

Our example number, 2147483647, is 2³¹ − 1. The exponent 31 is prime, and the whole thing is prime too. It may also look familiar to programmers: it's the biggest value a standard 32-bit signed integer can hold.

Easy to check, so easy to break records

Most huge numbers are painfully slow to test for primality. Mersenne numbers are the lucky exception. A clean, fast method called the Lucas–Lehmer test answers "is 2ⁿ − 1 prime?" by squaring and subtracting in a tight loop — no factoring required.

Because the test is so quick, the very largest primes anyone has ever confirmed are almost always Mersenne primes. They are found by GIMPS, the Great Internet Mersenne Prime Search, where thousands of volunteers lend their computers' spare time to grind through candidate exponents. Each new record is a number with tens of millions of digits.

A secret link to perfect numbers

A perfect number equals the sum of its own divisors (not counting itself): 6 = 1 + 2 + 3, and 28 = 1 + 2 + 4 + 7 + 14. They're rare and a little magical.

Here's the surprise: every even perfect number is built from a Mersenne prime, and every Mersenne prime gives one back. Multiply a Mersenne prime by the power of two just below it and you get a perfect number — 3 makes 6, 7 makes 28, 31 makes 496. This pairing, proved by Euclid long ago and completed by Euler, means the two oldest puzzles in number theory are really the same puzzle.

So whenever GIMPS finds a new Mersenne prime, it quietly hands us a brand-new perfect number for free.