Perfect Numbers and Mersenne Primes: A Twenty-Three-Centuries-Old Hunt

A positive integer is perfect if it equals the sum of its proper divisors. The smallest perfect number is $6$, whose proper divisors are $1, 2, 3$, and $1 + 2 + 3 = 6$. The next is $28 = 1 + 2 + 4 + 7 + 14$. The third is $496$, and the fourth is $8128$. These four were known to the ancient Greeks, who attached great mystical importance to them — Saint Augustine wrote that “God created the world in six days because six is a perfect number.”

After $8128$, the next perfect number is $33{,}550{,}336$. The gap is enormous, and the search for perfect numbers turns out to be one of the oldest open computational projects in mathematics. The question is governed by a single beautiful theorem connecting perfect numbers to a special class of primes called Mersenne primes, and the modern hunt for new perfect numbers is, by way of this theorem, a hunt for new Mersenne primes. This article is about the history of that hunt, why the connection holds, and where things stand twenty-three centuries after Euclid first wrote about it.

The Euclid–Euler theorem

In Book IX of his Elements (around 300 BCE), Euclid proved that if $2^p - 1$ is prime, then $2^{p-1}(2^p - 1)$ is perfect. The proof is short and accessible: factor the candidate, compute the sum of its divisors, and check.

This gives a recipe for making perfect numbers from primes of the form $2^p - 1$. With $p = 2$: $2^2 - 1 = 3$ (prime), so $2^{1} \cdot 3 = 6$ is perfect. With $p = 3$: $2^3 - 1 = 7$ (prime), so $2^2 \cdot 7 = 28$ is perfect. With $p = 5$: $2^5 - 1 = 31$ (prime), so $2^4 \cdot 31 = 496$. With $p = 7$: $2^7 - 1 = 127$ (prime), so $2^6 \cdot 127 = 8128$. The first four perfect numbers fall out of the first four primes $p$ for which $2^p - 1$ is prime.

What Euclid could not prove is the converse — that every even perfect number must have this form. Twenty centuries later, Leonhard Euler did. In his 1747 Tractatus de numerorum doctrina, Euler proved the converse: any even perfect number can be written as $2^{p-1}(2^p - 1)$ with $2^p - 1$ prime. Together, Euclid’s and Euler’s results give the Euclid–Euler theorem:

The even perfect numbers are exactly the numbers $2^{p-1}(2^p - 1)$ where $2^p - 1$ is a prime.

This is a complete classification. Finding new even perfect numbers is equivalent to finding new primes of the form $2^p - 1$. The whole subject, for the past three centuries, has revolved around hunting for such primes.

Mersenne primes

The primes of the form $2^p - 1$ are called Mersenne primes, after the French monk Marin Mersenne (1588–1648), who in 1644 conjectured a list of which exponents $p \leq 257$ make $2^p - 1$ prime. Mersenne’s list contained errors — both inclusions of composites and omissions of true Mersenne primes — but his name has stuck to this entire class of numbers.

A first observation: if $n$ is composite, say $n = ab$ with $1 < a, b < n$, then $2^n - 1$ is composite too, since $2^a - 1$ divides $2^n - 1$. So for $2^p - 1$ to be prime, $p$ itself must be prime. But the converse fails — not every prime $p$ gives a Mersenne prime. For example, $p = 11$ is prime, but $2^{11} - 1 = 2047 = 23 \cdot 89$ is composite.

So Mersenne primes are a thinning of the prime exponents: each prime $p$ is a candidate, but only some of them actually produce Mersenne primes. The known Mersenne-prime exponents $p$ (the first 12 of them) are:

After the ancient Greeks identified four perfect numbers, the next Mersenne prime ($p = 13$) had to wait until the 15th century. The next two ($p = 17, 19$) were found by Pietro Cataldi in 1588. By the time computers entered the picture in the 1950s, only 12 Mersenne primes had been discovered in over two millennia of human computation. As of 2024, 52 Mersenne primes are known, the largest having more than $24$ million digits.

The Lucas–Lehmer test

The reason computer searches for Mersenne primes have been so successful is the existence of an efficient primality test specific to Mersenne numbers, the Lucas–Lehmer test (refined by Édouard Lucas in 1876, then by Derrick Henry Lehmer in 1930).

Define the sequence $s_1 = 4$ and $s_k = s_{k-1}^2 - 2$. Then for an odd prime $p$, the Mersenne number $M_p = 2^p - 1$ is prime if and only if $s_{p-1} \equiv 0 \pmod{M_p}$.

The test takes $O(p)$ modular squarings to run, which is fast even for huge $p$. With $p$ around $80$ million, the test takes hours or days on a modern desktop — much faster than testing a random large number for primality, where no comparable shortcut exists. This is why nearly all of the largest known primes are Mersenne primes: there is a fast specialised test, and there is no fast equivalent for general numbers.

GIMPS: distributed computing for primes

Since 1996, the Great Internet Mersenne Prime Search (GIMPS), a volunteer distributed computing project, has been systematically testing Mersenne candidates. Volunteers download a client program that runs the Lucas–Lehmer test on assigned exponents and reports back. By December 2018, GIMPS had found 17 Mersenne primes, including the current largest known prime $M_{82{,}589{,}933}$, which has $24{,}862{,}048$ decimal digits.

GIMPS offers monetary prizes for new Mersenne primes (currently three thousand dollars for any new find), and the Electronic Frontier Foundation has long-standing prizes for primes with 100 million and 1 billion digits — both still unclaimed.

Mersenne prime exponents become exponentially rarer as $p$ grows. A heuristic argument by Lenstra, Pomerance, and Wagstaff predicts that the count of Mersenne primes with exponent up to $N$ grows like $C \log_2 N$ for some constant $C$. By the heuristic, we should expect a few new Mersenne primes per decade of search range, which is roughly what GIMPS has been observing.

Odd perfect numbers: the great open question

The Euclid–Euler theorem classifies even perfect numbers, but says nothing about odd ones. Are there any odd perfect numbers?

No one knows. None has ever been found. But no one has proved that none can exist, either. Modern research has accumulated a long list of constraints that any odd perfect number would have to satisfy:

• Larger than $10^{1500}$ (Ochem and Rao, 2012).
• At least $101$ distinct prime factors, the largest of which must exceed $10^8$ (Goto and Ohno, 2008).
• The smallest prime factor must be at most about $\log\log n$.
• The number must have at least $9$ prime factors counted with multiplicity.
• Many other tight constraints on its prime structure.

Each new constraint rules out a slightly larger class of potential odd perfect numbers, but none of them comes close to proving impossibility. Most number theorists believe odd perfect numbers do not exist, but the proof remains elusive after thousands of years of search.

Why the questions are deep

Perfect numbers and Mersenne primes might appear, on the surface, to be a recreational curiosity. The reason mathematicians take them seriously is what they encode about the multiplicative structure of the integers.

Perfect numbers are about the sum-of-divisors function $\sigma(n)$: a number is perfect when $\sigma(n) = 2n$. The function $\sigma$ is multiplicative — $\sigma(mn) = \sigma(m)\sigma(n)$ when $\gcd(m, n) = 1$ — and lives in the same family of “arithmetic functions” as the totient function $\varphi$. Understanding when $\sigma(n) = 2n$ requires understanding subtle multiplicative coincidences.

Mersenne primes are about the factorisation properties of numbers of a very specific form. They sit at the intersection of two large theoretical themes: the density of primes (how many Mersenne primes are there?) and the algebraic structure of cyclotomic extensions (the factorisation of $x^n - 1$). Whether there are infinitely many Mersenne primes is a question about the asymptotic density of primes in a sparse sequence, and it remains far beyond the reach of current techniques.

A continuous thread

The hunt for perfect numbers is, perhaps, the longest continuously-pursued problem in mathematics. Pythagoras’s students were studying them in the 6th century BCE. Euclid wrote about them around 300 BCE. Mersenne, Fermat, Descartes, and Euler all worked on them. Lucas and Lehmer developed the modern primality test. Computers, beginning with Robinson’s ENIAC calculations in 1952, joined the search. GIMPS, since 1996, has distributed the search across hundreds of thousands of volunteer computers worldwide.

In the entire arc of this twenty-three-century pursuit, the basic question has not changed: which numbers of the form $2^p - 1$ are prime, and (equivalently) what are the perfect numbers? Every mathematician who has worked on the problem has used progressively more sophisticated tools, but they have all been chasing the same simple-looking quantity. That is the hallmark of a problem at the right level of depth: easy to state, hard to settle, and connected to enough other parts of mathematics that progress at any one point teaches something about all of them. Perfect numbers and Mersenne primes are the prototype.

The next Mersenne prime might be found by GIMPS this year, or in five years, or in fifty. Whoever finds it — likely a volunteer running a free program on a personal computer — will be the latest link in a chain of inquirers stretching back to Euclid. Few mathematical traditions span so many centuries with such an unbroken continuity. Perfect numbers connect us, in a small but real way, to the very beginnings of the mathematical project.

Frequently asked

What is a perfect number, exactly?

A positive integer n is perfect if it equals the sum of its proper positive divisors — that is, all positive divisors of n except n itself. The first few perfect numbers are 6 (= 1 + 2 + 3), 28 (= 1 + 2 + 4 + 7 + 14), 496, 8128, 33550336, and 8589869056. The sequence grows quickly: only 52 perfect numbers are known as of 2024. The ancient Greeks knew the first four; the fifth was found in the 15th century; and modern numbers have been discovered using distributed computing.

What is the Euclid–Euler theorem?

It says that every even perfect number has the form 2^(p−1)(2^p − 1), where 2^p − 1 is a prime number. Euclid proved in around 300 BCE that any number of this form is perfect (provided 2^p − 1 is prime); Euler proved in 1747 that every even perfect number must have this form. The theorem completely classifies even perfect numbers: they are in bijection with Mersenne primes.

What is a Mersenne prime?

A Mersenne prime is a prime number of the form 2^p − 1, where p is itself prime. (It's not always the case that 2^p − 1 is prime when p is; for example, 2^11 − 1 = 23 × 89 is not prime.) Named after the French monk Marin Mersenne (1588–1648), who studied them. The largest known prime as of 2024 — 2^82,589,933 − 1 — is a Mersenne prime with more than 24 million decimal digits, found in 2018 by the Great Internet Mersenne Prime Search (GIMPS), a volunteer distributed-computing project.

Are there infinitely many Mersenne primes, or any odd perfect numbers?

Both are major unsolved problems. It is conjectured but not proved that infinitely many Mersenne primes exist; the heuristic estimates predict the count of Mersenne primes among the first N exponents grows logarithmically. As for odd perfect numbers, none has ever been found, and any that exists must be larger than 10^1500 and satisfy many other extreme constraints proved over the past century. Most number theorists believe odd perfect numbers do not exist, but a proof has never been produced. These two questions are arguably the oldest open problems in mathematics, both dating back to Euclid.

Continue reading

Person

Leonhard Euler

Swiss mathematician of extraordinary range and productivity. Formulated Euler's identity, founded graph theory, and produced more mathematical output than any mathematician before or since.

Read →Blog

RSA Encryption: How Two Primes Lock the World's Secrets

Pick two large primes. Multiply them. Publish the product. Every HTTPS connection and every encrypted message rests on the fact that nobody can factor that product back into the two primes.

Read →Blog

Euler's Totient Function: Counting the Numbers That Share Nothing With n

How many integers from 1 to n share no common factor with n? That simple-looking count, written φ(n), turns out to control the structure of modular arithmetic — and the security of the modern web.

Read →