Mersenne and Fermat Primes

Every few years, a headline announces "the largest known prime number" — a number with tens of millions of digits, far too big to ever check with ordinary trial division. How could anyone possibly prove such a monster is prime? The secret is that record-hunters don't test random giant numbers at all. They test numbers of one very special shape: 2^p - 1, called a Mersenne number, or 2^{2^k} + 1, a Fermat number.

That special shape isn't just tidy-looking — it's the whole trick. For a general number with a million digits, no fast primality test exists; you'd be stuck forever. But for a Mersenne or Fermat number of exactly that size, a dedicated fast test (the Lucas–Lehmer test for Mersenne numbers, Pépin's test for Fermat numbers) can settle the question in a reasonable time. The special form buys you a shortcut that a random number never gets — which is exactly why every record-sized prime you'll ever hear about has one of these two shapes.

Mersenne primes: 2^n - 1

Named after the French friar Marin Mersenne, a Mersenne number is M_n = 2^n - 1; when it happens to be prime, we call it a Mersenne prime.

A neat constraint cuts the search down enormously: if 2^n - 1 is prime, then n must itself be prime. The reason is a factoring identity — if n = ab with both factors bigger than $1$, then 2^a - 1 divides 2^n - 1 exactly:

2^{ab} - 1 = (2^a - 1)\big(2^{a(b-1)} + \dots + 2^a + 1\big).

So a composite exponent guarantees a composite Mersenne number — there's no point even testing $2^{12}-1$ or $2^{15}-1$, since $12$ and $15$ are composite. That already throws away most candidates for free, before any expensive testing begins.

Worked example: testing the small Mersenne numbers

Let's check the Mersenne numbers for every prime exponent up to $11$, one at a time.

So $2, 3, 5, 7$ all give Mersenne primes, but $11$ — despite being just as prime as the others — does not. A prime exponent buys you a chance at a Mersenne prime, never a guarantee.

This is one of the classic traps in all of number theory, and Mersenne primes are the textbook example of it:

The same trap catches $23$ and $29$: both prime, yet 2^{23}-1 = 8388607 = 47 \times 178481 and 2^{29}-1 = 536870911 = 233 \times 1103 \times 2089 are both composite. Meanwhile $13, 17, 19$, and $31$ all do give Mersenne primes. There's no shortcut to knowing which — you have to test.

Fermat primes: 2^{2^k} + 1

Named after Pierre de Fermat, a Fermat number is F_k = 2^{2^k} + 1. Just as with Mersenne numbers, the exponent's shape matters: 2^m + 1 can only possibly be prime when $m$ itself is a power of two — any odd factor in $m$ produces a factoring identity that forces a composite result, exactly mirroring the Mersenne case but for $+1$ instead of $-1$.

Worked example: testing the Fermat numbers

Five in a row, all prime — Fermat conjectured in 1650 that every $F_k$ would be, forever. A century later, Leonhard Euler checked the very next one by hand and found the pattern's dramatic end:

F_5 = 2^{32} + 1 = 4{,}294{,}967{,}297 = 641 \times 6{,}700{,}417.

Not only is $F_5$ composite, but in the centuries since, no Fermat prime beyond $F_4$ has ever been found — mathematicians have tested dozens of further Fermat numbers, all composite, though nobody has proved there can never be another.

Euler didn't get lucky guessing $641$ — he was clever. He proved that any factor of $F_5$ must have the special form $64k + 1$ for some whole number $k$, which shrinks the list of divisors worth trying down to almost nothing. Testing candidates of that shape — $193, 257, 449, 577, 641, \dots$ — he hit $641$ on essentially his first serious attempt and found it divided $F_5$ exactly.

It's a lovely lesson in its own right: even when you can't test every possible factor, finding the right narrower family to search — just as with restricting Mersenne exponents to primes — turns an impossible search into an easy one.

A startling bridge to geometry

Gauss proved that a regular polygon with N sides is constructible with straightedge and compass precisely when N is a power of two times a product of distinct Fermat primes. That is why the regular 17-gon can be drawn (and Gauss, aged just $19$, was so proud of the discovery that he asked for a regular $17$-gon on his tombstone) but the regular 7-gon cannot — $7$ is prime, but it isn't a Fermat prime. Mersenne primes, meanwhile, generate every even perfect number — a link we will trace later.

Here's the payoff for all that special structure: every single one of the largest known primes today is a Mersenne prime. The reason is the Lucas–Lehmer test — a beautifully simple recipe that can certify a Mersenne number prime (or not) without ever trying a single division by a candidate factor, making it practical on numbers with tens of millions of digits.

Since 1996, the hunt has been crowd-sourced: the Great Internet Mersenne Prime Search (GIMPS) lets anyone download free software that tests candidate exponents using their computer's spare processing time, day and night. Volunteers around the world have found every record-breaking prime since — by the mid-2020s the record-holder had grown to over $41$ million digits, so large that printing it in an ordinary book would take thousands of pages of nothing but digits. The search is still running today; the next record could be found on somebody's laptop while they sleep.

See it explained