Mersenne Primes and the Search for Huge Numbers

In October 1903, mathematician Frank Nelson Cole walked to the blackboard at a meeting of the American Mathematical Society and, without saying a word, calculated 2⁶⁷ − 1. On another part of the board, he multiplied 193,707,721 × 761,838,257,287. The two results matched. He sat down to a standing ovation.

Cole had shown that a number believed prime for over 250 years wasn't. He later said the factorization took him "three years of Sundays." Numbers of the form 2ᵖ − 1, called Mersenne numbers, have been at the center of the hunt for giant primes ever since.

The Biggest Primes Are the Easiest to Prove

You'd expect that the larger a number, the harder it is to prove prime. For general numbers, that's true. But for numbers of the special form 2ᵖ − 1, there's a test so efficient that primes with tens of millions of digits can be confirmed.

That's why, for most of the computer age, nearly every record-holding prime has been a Mersenne prime. The record isn't set by the most random big numbers, but by the ones with the most helpful structure.

What Is a Mersenne Prime?

A Mersenne number is:

Mₚ = 2ᵖ − 1

When it's prime, it's a Mersenne prime. In binary, it's simply a string of p ones: 2⁵ − 1 = 31 = 11111₂. See that pattern with the binary to decimal converter.

A key fact: if 2ᵖ − 1 is prime, then p must be prime. If p = ab, then 2ᵃ − 1 divides 2ᵖ − 1. But a prime p isn't enough, as p = 11 shows. Check it with the prime checker for 2,047.

Marin Mersenne's List

Marin Mersenne was a 17th-century French friar who corresponded with Fermat, Descartes and Pascal. In 1644, he claimed that 2ᵖ − 1 is prime for p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 and 257, and composite for every other prime p up to 257.

He couldn't possibly have checked most of these. His list turned out to contain errors: M₆₇ and M₂₅₇ are composite, and he missed M₆₁, M₈₉ and M₁₀₇, which are prime. Cole's 1903 blackboard calculation was the dramatic disproof for M₆₇.

The Lucas–Lehmer Test

Mersenne numbers are special because of a test developed by Édouard Lucas in the 1870s and refined by Derrick Henry Lehmer in the 1930s:

s₀ = 4
sₖ₊₁ = (sₖ² − 2) mod Mₚ
Mₚ is prime  ⟺  sₚ₋₂ = 0

Let's test M₇ = 127 (p − 2 = 5 steps):

s₁ = 4² − 2 = 14
s₂ = 14² − 2 = 194 mod 127 = 67
s₃ = 67² − 2 = 4,487 mod 127 = 42
s₄ = 42² − 2 = 1,762 mod 127 = 111
s₅ = 111² − 2 = 12,319 mod 127 = 0  ✓

It lands on 0, so 127 is prime. Confirm with the prime checker for 127.

For a p-digit exponent, the test needs only p − 2 squarings. Computers speed up each squaring of enormous numbers using the Fast Fourier Transform, turning multiplication into a signal-processing problem.

In 1876, Lucas used an early version of his method to prove that M₁₂₇, a 39-digit number, is prime. It remained the largest known prime for 75 years, until computers took over in 1951.

An Insider Reference: GIMPS and the Record Hunters

In 1996, programmer George Woltman founded the Great Internet Mersenne Prime Search (GIMPS). Volunteers download free software that tests Mersenne numbers in the background on their computers.

GIMPS has found 18 Mersenne primes. Its milestones include:

• 2008: M₄₃,₁₁₂,₆₀₉, found at UCLA, the first prime with over 10 million digits, which won a $100,000 award from the Electronic Frontier Foundation
• 2018: M₈₂,₅₈₉,₉₃₃, with 24,862,048 digits, found by volunteer Patrick Laroche
• October 2024: M₁₃₆,₂₇₉,₈₄₁, with 41,024,320 digits, found by Luke Durant, a former NVIDIA engineer who organized thousands of cloud GPUs across multiple data centers

The EFF still offers $150,000 for the first prime with 100 million digits and $250,000 for one with a billion.

As of the 2024 discovery, 52 Mersenne primes are known. Whether there are infinitely many remains an open question, though mathematicians widely expect so.

A Link to Perfect Numbers

Every Mersenne prime creates a perfect number, a number equal to the sum of its proper divisors:

2ᵖ⁻¹ × (2ᵖ − 1)

M₃ = 7 gives 4 × 7 = 28 = 1 + 2 + 4 + 7 + 14. Euclid proved this direction around 300 BC, and Euler proved that every even perfect number arises this way. Read more in Perfect Numbers: Numbers That Equal the Sum of Their Parts.

Two Concepts Worth Knowing

Modular Arithmetic

The Lucas–Lehmer test keeps every value mod Mₚ, so numbers never grow beyond p bits. And reducing mod 2ᵖ − 1 is especially cheap in binary: you just add the high bits to the low bits.

Primality Certificate

A deterministic test like Lucas–Lehmer gives a definite yes or no. That's stronger than probabilistic tests, which only make "composite but passed" extremely unlikely.

Quick Answer: What Is a Mersenne Prime?

A Mersenne prime is a prime number of the form 2ᵖ − 1, such as 3, 7, 31 and 127. The exponent p must be prime, but not every prime p works. The Lucas–Lehmer test can check them very efficiently, which is why the largest known primes, including the 41-million-digit record from 2024, are Mersenne primes.

Try Them Yourself

• Is 127 Prime?: the Mersenne prime from our worked test
• Is 2,047 Prime?: the first Mersenne number with prime exponent that fails
• Binary to Decimal Converter: Mersenne numbers are all 1s in binary
• Base-2 Logarithm Table: powers of two at a glance
• Number 127: facts about M₇
• Pierre de Fermat: Mersenne's famous correspondent

Run the Lucas–Lehmer test by hand for M₅ = 31 (only 3 steps). If you reach 0, you've proved a prime the same way GIMPS does.