Mersenne Perfection

How Euclid and Euler found the connection between perfect and prime numbers

September 13, 2025 · John Peach

Perfect numbers

Every integer nn has divisors, or numbers that divide nn evenly. Prime numbers pp are only divisible by 11 and pp, but composite numbers like 1212 have more divisors,

 gp > divisors(12)
%1 = [1, 2, 3, 4, 6, 12]

This uses the divisors function from the PARI/GP language. The PARI/GP reference card lists built-in functions for number theory in the Elementary Arithmetic Functions, such as numdiv, which returns the number of divisors, e.g., numdiv(12) = 6, and the sum of the divisors sigma(12) = 28. We can define a variant of this function, σ∗\sigma^* which is the sum of the divisors less than nn, σ∗(n)=σ(n)−n\sigma^*(n) = \sigma(n) - n, so σ∗(12)=16.\sigma^{\ast} (12) = 16. This is where things get interesting, because if σ∗(n)=n\sigma^*(n) = n then nn is called a perfect number.

Perfect numbers are rather rare - the smallest is 66 because the divisors of 66 are [1,2,3,6][1,2,3,6] and the sum of the divisors less than 66 is 1+2+3=6.1+2+3=6. The next largest is 2828,

 gp > divisors(28)
%2 = [1, 2, 4, 7, 14, 28]

and 1+2+4+7+14=28.1 + 2 + 4 + 7 + 14 = 28. The first five perfect numbers are 6,28,496,8128,33550336,6, 28, 496, 8128, 33550336, and the OEIS (Online Encyclopedia of Integer Sequences) gives the first ten.

If σ∗(n)>n\sigma^*(n)>n then nn is a superabundant number, and if σ∗(n)<n\sigma^*(n)<n, then nn is deficient. Only when σ∗(n)=n\sigma^*(n) = n is nn a perfect number.

Euclid’s insight

Notice that 66 is the sum of the first three integers because they happen to go into 66 evenly. But, it turns out that,

6=1+2+328=1+2+3+4+5+6+7496=1+2+3+…+30+318128=1+2+3+…+126+127\begin{aligned} 6 &= 1+2+3 \\ 28 &= 1+2+3+4+5+6+7 \\ 496 &= 1+2+3+ \ldots + 30 + 31 \\ 8128 &= 1+2+3+ \ldots + 126 + 127 \end{aligned}

which are the sums SS of the first nn integers. A formula for the sum of the first nn integers is S=n(n+1)/2S = n(n+1)/2. For each perfect number SS, we can find the corresponding nn by

S=12n(n+1)2S=n2+nn2+n−2S=0n=12(8S+1−1)\begin{aligned} S &= \frac{1}{2}n(n+1) \\ 2S &= n^2 + n \\ n^2 &+ n - 2S = 0 \\ n &= \frac{1}{2} (\sqrt{8S + 1} - 1) \end{aligned}

using the quadratic formula and discarding the negative root. Try this out in PARI,

 gp > (sqrt(8*496+1)-1)/2
%3 = 31.000000000000000000000000000000000000

which confirms that the perfect number 496496 is the sum of the first 3131 integers. You can write a simple PARI function to calculate nn from SS,

q(S) = (sqrt(8*S+1)-1)/2

You might have noticed that nn is one less than a power of 22, or n+1=2pn+1 = 2^p for some value of pp. Solving for pp,

p=log⁡(n+1)log⁡2,p = \frac{\log(n+1)}{\log{2}},

and the equivalent PARI function is

 r(S) = log(q(S)+1)/log(2)

Input the OEIS list of perfect numbers and you’ll find that the corresponding p=[2,3,5,7,13,17,19,31,61,89].p = [2,3,5,7,13,17,19,31,61,89]. At the time of Euclid, only the first four perfect numbers were known, but Euclid saw the pattern of prime numbers for pp.

We don’t know for sure that prime numbers are connected to perfect numbers, but we can work backwards to go from any prime to a potential perfect number,

n=2p−1S=12n(n+1)=122p(2p−1)=2p−1(2p−1).\begin{aligned} n &= 2^p - 1 \\ S &= \frac{1}{2} n (n + 1) \\ &= \frac{1}{2} 2^p (2^p - 1) \\ &= 2^{p-1}(2^p-1). \end{aligned}

Written as a PARI function,

S(p) = 2^(p-1)*(2^p - 1)

which returns [6,28,496,8128][6,28,496,8128] for the first four primes.

Figure 1.

Raphael’s fresco “Stanza della Segnatura” (The School of Athens). Euclid is in the red robe on the right, teaching geometry.

Marin Mersenne

Marin Mersenne was a 17th17^{th} century French polymath and Catholic priest who studied mathematics, music, and philosophy. He wrote about music theory and developed formulas relating musical pitch to properties of a stretched string.

Figure 2.

Marin Mersenne.

Mersenne discovered that 2p−12^p-1 is a prime number for some values of pp when pp is also a prime number. The OEIS sequence A000043 lists some of the known Mersenne exponents, and the largest known exponent is p=136,279,841.p = 136,279,841. Notice that in the formula for perfect numbers, S(p)=2p−1(2p−1)S(p) = 2^{p-1}(2^p-1) the second term is a Mersenne prime while the first term is constructed from the same prime exponent.

Mathematicians are still puzzling over many ideas surrounding Mersenne primes. Mersenne published a conjecture in his Cogitata Physico-Mathematica that the primes p=[2,3,5,7,13,17,19,31,67,127,257]p = [2, 3, 5, 7, 13, 17, 19, 31, 67, 127,257] generated Mersenne primes (see OEIS A109461), but 6767 and 257257 do not generate primes, and he missed 61,8961,89, and 107107. During his time, nobody could perform the calculations for any prime greater than 1919, but PARI finds the factors for S(67)S(67),

 gp > factor(2^67-1)
%4 =
[   193707721  1]
[761838257287  1]

A more recent conjecture is the Bateman, Selfridge, and Wagstaff conjecture, which says that for any odd natural number pp if pp is a Mersenne prime and p=2k±1p = 2^k \pm 1 or p=4k±3p = 4^k \pm 3 for some natural number then (2p+1)/3(2^p+1)/3 is a prime.

A more interesting conjecture is that there are infinitely many Mersenne primes, and the number of these primes less than any integer xx is

eγ⋅log⁡2log⁡2(x)e^\gamma \cdot \log_2 \log_2(x)

where γ≈0.57721\gamma \approx 0.57721 is the Euler-Mascheroni constant.

Conjectures are interesting, but what can be proven?

  1. We’ve shown the relationship between Mersenne primes and the sum of the first nn natural numbers, S=2p−1(2p−1),S = 2^{p-1}(2^p - 1), but why is SS a perfect number?
  2. Are there any Mersenne primes 2p−12^p-1 where pp is not a prime number?

Proofs

Figure 3.

How mathematicians do proofs.

The Euclid-Euler Theorem

The Euclid-Euler theorem says that an even number SS is perfect if and only if S=2p−1(2p−1)S = 2^{p-1}(2^p-1) where pp is prime. Euclid proved the forward direction, “if”, while Euler proved the reverse, “only if”.

Theorem: Every Mersenne prime generates an even perfect number (Euclid).

Proof: We need to show that the sum of the divisors of SS (excluding SS itself) is equal to SS, or σ∗(S)=S.\sigma^*(S) = S. Equivalently, we could show that σ(S)=2S.\sigma(S) = 2S. Since 2p−12^p-1 is a Mersenne prime, then the only divisors are 1 and 2p−12^p-1, and the divisors of 2p−12^{p-1} are the powers of 22 up to 2p−12^{p-1}, 1,2,4,8,…,2p−11,2,4,8, \ldots, 2^{p-1}. Then, σ(S)=σ(2p−1(2p−1))=σ(2p−1)σ(2p−1)\sigma(S) = \sigma(2^{p-1}(2^p-1)) = \sigma(2^{p-1})\sigma(2^p-1) since there are no divisors in common with the first and second terms other than 11.

The first term σ(2p−1)=1+2+4+8+…+2p−1\sigma(2^{p-1}) = 1+2+4+8+ \ldots + 2^{p-1} is a geometric series, and if we multiply by two and subtract the original, we get

σ(2p−1)=2σ(2p−1)−σ(2p−1)=2+4+8+…+2p−1+2p−(1+2+4+8+…+2p−1)=2p−1\begin{aligned} \sigma(2^{p-1}) &= 2\sigma(2^{p-1}) - \sigma(2^{p-1}) \\ &= 2+4+8+ \ldots + 2^{p-1} + 2^p \\ &- (1+2+4+8+ \ldots + 2^{p-1}) \\ &= 2^p-1 \end{aligned}

and the sum of the divisors of the Mersenne prime is σ(2p−1)=1+(2p−1)=2p\sigma(2^p-1) = 1 + (2^p-1) = 2^p, so

σ(S)=σ(2p−1(2p−1))=σ(2p−1)σ(2p−1)=(2p−1)(2p)=2(2p−1)(2p−1)=2S\begin{aligned} \sigma(S) &= \sigma(2^{p-1}(2^p-1)) = \sigma(2^{p-1})\sigma(2^p-1) \\ &= (2^p-1)(2^p) \\ &= 2(2^{p-1})(2^p-1) = 2S \end{aligned}

so SS is perfect. ■\blacksquare

Theorem: Every even perfect number may be written as 2p−1M2^{p-1}M where MM is a Mersenne prime, M=2p−1M = 2^p-1 (Euler).

Proof: Let SS be an even perfect number, so S=2kqS = 2^k q where qq is odd. Since SS is perfect,

σ(S)=σ(2kq)=σ(2k)σ(q)=(2k+1−1)σ(q)\sigma(S) = \sigma(2^kq) = \sigma(2^k) \sigma(q) = (2^{k+1}-1)\sigma(q)

and so

σ(S)=2S=2⋅2kq=2k+1q=(2k+1−1)σ(q).\begin{aligned} \sigma(S) &= 2S = 2\cdot 2^kq \\ &= 2^{k+1}q = (2^{k+1}-1)\sigma(q). \end{aligned}

We can write σ∗(q)=σ(q)−q\sigma^*(q) = \sigma(q) - q, or σ(q)=σ∗(q)+q\sigma(q) = \sigma^*(q) + q which gives

2k+1q=(2k+1−1)(σ∗(q)+q)2^{k+1}q = (2^{k+1}-1)(\sigma^*(q)+q)

which implies that

2k+1q=(2k+1−1)σ∗(q)+2k+1q−q0=(2k+1−1)σ∗(q)−q⇒q=(2k+1−1)σ∗(q).\begin{aligned} 2^{k+1}q &= (2^{k+1}-1)\sigma^*(q) + 2^{k+1}q - q \\ 0 &= (2^{k+1}-1)\sigma^*(q) - q \\ &\Rightarrow q = (2^{k+1}-1)\sigma^*(q). \end{aligned}

Notice that k≥1k \geq 1 since SS is even, so 2k+1−1≥32^{k+1}-1 \geq 3 and odd, which means that σ∗(q)\sigma^*(q) is a proper divisor of q.q. But, σ∗(q)\sigma^*(q) is the sum of all proper divisors of q,q, which implies that qq has only one proper divisor, meaning qq is prime and σ∗(q)=1.\sigma^*(q) = 1. So, q=2k+1−1q = 2^{k+1} - 1 is a Mersenne prime and k+1=pk+1 = p is a prime. ■\blacksquare

Perfect is the sum of the first MM integers

Theorem: If MM is a Mersenne prime, then S=∑k=1MkS = \sum_{k=1}^M k is a perfect number.

Proof: Every Mersenne prime is of the form M=2p−1M = 2^p-1 by definition. The sum of the first MM integers is

∑k=1Mk=1+2+…+M=12M(M+1)=12(2p−1)2p=2p−1(2p−1)=2p−1M.\begin{aligned} \sum_{k=1}^M k &= 1 + 2 + \ldots + M \\ &= \frac{1}{2}M(M+1) \\ &= \frac{1}{2}(2^p-1)2^p \\ &= 2^{p-1}(2^p-1) \\ &= 2^{p-1}M. \end{aligned}

The previous theorem showed that every perfect number S=2p−1M.  ■S = 2^{p-1}M. \; \blacksquare

Product theorem for σ\sigma

Before we get to the next theorem, let’s look at an example. Suppose you calculate the sum of the divisors of a number, say 2424, which has divisors [1,2,3,4,6,8,12,24],[1, 2, 3, 4, 6, 8, 12, 24], soσ(24)=60\sigma(24) = 60. The prime factors of 2424 are 232^3 and 33, which means that

σ(24)=σ(23⋅3)=σ(23)⋅σ(3).\sigma(24) = \sigma(2^3 \cdot 3) = \sigma(2^3) \cdot \sigma(3).

In this case, σ(23)=σ(8)=15\sigma(2^3) = \sigma(8) = 15 and σ(3)=4\sigma(3) = 4 and their product is 6060. We’ve been using this fact without proof, but we’ll show how it is derived in the next theorem.

Theorem: If n=abn = ab is a composite integer and gcd⁡(a,b)=1\gcd(a,b) = 1 (a,b>0a,b > 0) then σ(n)=σ(ab)=σ(a)σ(b).\sigma(n) = \sigma(ab) = \sigma(a)\sigma(b).

Proof: Since the gcd⁡(a,b)=1\gcd(a,b) = 1, then aa and bb have only 11 as a common divisor, so the divisors of nn are the products of the divisors of aa and the divisors of bb. Suppose these divisors are [1,a1,a2,…,ai][1,a_1,a_2, \ldots, a_i] for aa and [1,b1,b2,…,bj][1,b_1,b_2, \ldots, b_j] for bb. The sum of the divisors is σ(a)=1+a1+a2+⋯+ai\sigma(a) = 1 + a_1 + a_2 + \cdots + a_i and σ(b)=1+b1+b2+⋯+bj,\sigma(b) = 1 + b_1 + b_2 + \cdots + b_j, so we can write the divisors of n=abn = ab as

1,b1,b2,…,bja1⋅1,a1⋅b1,a1⋅b2,…,a1⋅bja2⋅1,a1⋅b1,a2⋅b2,…,a2⋅bj⋮ai⋅1,ai⋅b1,ai⋅b2,…,ai⋅bj.\begin{aligned} 1,b_1,b_2, &\ldots, b_j \\ a_1 \cdot 1, a_1 \cdot b_1, a_1 \cdot b_2, &\ldots, a_1 \cdot b_j \\ a_2 \cdot 1, a_1 \cdot b_1, a_2 \cdot b_2, &\ldots, a_2 \cdot b_j \\ &\vdots \\ a_i \cdot 1, a_i \cdot b_1, a_i \cdot b_2, &\ldots, a_i \cdot b_j. \\ \end{aligned}

Summing each row gives

1+b1+b2+…+bj=σ(b)a1⋅1+a1⋅b1+a1⋅b2+…+a1⋅bj=a1σ(b)a2⋅1+a1⋅b1+a2⋅b2+…+a2⋅bj=a2σ(b)⋮ai⋅1+ai⋅b1+ai⋅b2+…+ai⋅bj=a1σ(b)=(1+a1+a2+⋯+ai)σ(b)=σ(a)σ(b).  ■\begin{aligned} 1 + b_1 + b_2 + &\ldots + b_j = \sigma(b) \\ a_1 \cdot 1 + a_1 \cdot b_1 + a_1 \cdot b_2 + &\ldots + a_1 \cdot b_j = a_1 \sigma(b) \\ a_2 \cdot 1 + a_1 \cdot b_1 + a_2 \cdot b_2 + &\ldots + a_2 \cdot b_j = a_2 \sigma(b) \\ &\vdots \\ a_i \cdot 1 + a_i \cdot b_1 + a_i \cdot b_2 + &\ldots + a_i \cdot b_j = a_1 \sigma(b) \\ &= (1 + a_1 + a_2 + \cdots + a_i) \sigma(b) \\ &= \sigma(a) \sigma(b). \; \blacksquare \end{aligned}

The Fundamental Theorem of Arithmetic says that every positive integer n>1n > 1 may be written in exactly one way as the product of primes. For the example of 24=23⋅324 = 2^3 \cdot 3 the Product Theorem for σ\sigma says that σ(24)=σ(23)⋅σ(3)=σ(8)⋅σ(3)=15⋅4=60.\sigma(24) = \sigma(2^3) \cdot \sigma(3) = \sigma(8) \cdot \sigma(3) = 15 \cdot 4 = 60. However, if you split the power of 22 so that 24=6⋅424 = 6 \cdot 4 the theorem doesn’t hold, σ(6)⋅σ(4)=12⋅7=84≠60.\sigma(6) \cdot \sigma(4) = 12 \cdot 7 = 84 \neq 60.

MM is prime only when pp is prime

Theorem: No Mersenne prime exists where M=2p−1M = 2^p - 1 and pp is not prime.

Proof: Suppose pp is composite, so p=r⋅sp = r \cdot s. Then 2p−1=2r⋅s−1=(2r)s−12^p - 1 = 2^{r \cdot s} - 1 = (2^r)^s - 1 is a binomial number, which factors into (2r−1)((2r)s−1+(2r)s−2+…+2r+1).  ■(2^r-1)((2^r)^{s-1} + (2^r)^{s-2} + \ldots + 2^r + 1). \; \blacksquare

GIMPS

The oldest unsolved problem in mathematics is the question: Are there any odd perfect numbers? The question may remain open for a while longer, but if you would like to search for the next Mersenne prime, you can sign up at the Great Internet Mersenne Prime Search (GIMPS) website. Currently, the largest known Mersenne prime is 2136279841−12^{136279841} - 1, but you can use their software to search for the next one.

GIMPS consists of a team of volunteers who run a program on their computers that searches for Mersenne primes. The program uses the Fermat primality test, which can quickly estimate the probability of a number being prime. More details can be found on the How GIMPS Works page.

Exercises

There are some very nice exercises in the LibreTexts chapters Number Theoretic Functions and Perfect Numbers and Mersenne Primes, or you might like to try a few problems using PARI/GP. For details about installing and using PARI/GP and Notepad++, see our article Put Another KenKen on the Barbie.

  1. Scan a range for Mersenne primes: For primes p≤2000p≤2000, print the exponents pp such that M​=2p−1M​=2^p−1 is prime. Hint: Use forprime and isprime.
  2. Generate even perfect numbers and verify perfection: For each Mersenne prime found in (1), compute the corresponding even perfect number S=2p−1(2p−1)S = 2^{p-1}(2^p-1) and verify σ∗(S)=S.\sigma^*(S) = S. Hint: Use sigma.
  3. Test that when nn is a composite number, 2n−12^n-1 is also composite. Try this for all values of 4≤n≤3004 \leq n \leq 300.
  4. Count the number of Mersenne primes in an interval, for example, using p∈[2,10000]p \in [2,10000], how many result in 2p−12^p-1 is also prime?
  5. For each prime p≤2000p \leq 2000, compute the perfect number S=2p−1(2p−1)S = 2^{p-1}(2^p-1), and count the number of digits in SS. Hint: Use digits(S).

Code for this article

The PARI/GP functions are quite simple, and you can easily write your own:

# Sum of the first n numbers for perfect number S.
q(S) = (sqrt(8*S+1)-1)/2 

# Prime exponent for perfect number S.
r(S) = log(q(S)+1)/log(2)

# Perfect number S generated by prime p. Not every p generates a perfect S.
S(p) = 2^(p-1)*(2^p - 1)

Software

References

Image credits