No. 001 · Section M
Interactive · Open Source
In 1644, a French friar named Marin Mersenne wrote down a short list of exponents $p$ for which he claimed $2^p - 1$ was prime. He got a few wrong and missed a couple — but the name stuck, and the hunt he started is still running almost four centuries later.
The first thing to notice is a hard constraint. If the exponent $p$ is composite, then $M_p$ is composite too — it factors algebraically. Write $p = ab$, and
$$2^{ab} - 1 = \bigl(2^a - 1\bigr)\bigl(2^{a(b-1)} + 2^{a(b-2)} + \cdots + 1\bigr).$$
So we only ever need to test prime exponents. That’s the necessary condition. The cruel twist — the thing that makes this a hunt and not a lookup — is that it isn’t sufficient. A prime exponent often produces a composite Mersenne number anyway. The smallest betrayal is $p = 11$: it’s prime, but $M_{11} = 2047 = 23 \times 89$.
So how do you actually check a number with hundreds of millions of digits? Not by trial division — you’d never finish. You use a test built for exactly this shape of number.
Fig. 1 — every number is computed in your browser with exact BigInt arithmetic. Nothing is hard-coded.
The test that does the catching
What you just watched on the right is the Lucas–Lehmer test, and its beauty is that it’s deterministic and almost embarrassingly simple. For an odd prime $p$, build a sequence starting at $4$ and squaring as you go, always reducing modulo $M_p$:
$$s_0 = 4, \qquad s_{k+1} = s_k^{\,2} - 2 \;\bmod\; M_p.$$
Run it exactly $p - 2$ times. Then the verdict is a single equality:
$$M_p \text{ is prime} \iff s_{p-2} \equiv 0 \pmod{M_p}.$$
That’s the whole algorithm. No factoring, no guessing, no probability — a clean yes or no after $p-2$ squarings. The reduction $\bmod\, M_p$ is the other gift: because $M_p$ is a string of $p$ ones in binary, taking a remainder modulo it is a shift-and-add, not a division. Squaring a number and folding it back is so cheap that machines can carry it out on numbers with tens of millions of digits.
That’s why every record-breaking prime for decades has been a Mersenne prime. The test is purpose-built for them, so they are simply the cheapest enormous primes to certify.
A prime done by hand, and a prime found by the world
In 1876, before anything we’d call a computer existed, Édouard Lucas proved that $M_{127}$ — a 39-digit number — is prime, using an early form of this very test. It held the record for the largest known prime for 75 years, the largest ever found without a machine.
$$M_{127} = 170{,}141{,}183{,}460{,}469{,}231{,}731{,}687{,}303{,}715{,}884{,}105{,}727.$$
Today the search is a planetary collaboration called GIMPS — the Great Internet Mersenne Prime Search — where tens of thousands of volunteer machines grind through candidate exponents. Only 52 Mersenne primes are known. The hunt below stops at $p = 31$ because that’s where the numbers fit comfortably on the page — but the real frontier sits past 80 million digits.