Perfect Numbers and Mersenne Primes

The ancient Greeks called $6$ perfect because its smaller divisors add up to it: $1 + 2 + 3 = 6$. So does $28 = 1 + 2 + 4 + 7 + 14$. With the divisor sum $\sigma$, this becomes a clean equation, and Euclid's recipe for perfect numbers becomes a short proof.

Definitions. A positive integer $n$ is perfect when $\sigma(n) = 2n$, that is, when its proper divisors (all but $n$ itself) add up to $n$. It is deficient when $\sigma(n) < 2n$ and abundant when $\sigma(n) > 2n$.

Worked example: Three kinds

Classify $12$, $14$ and $28$.

$\sigma(12) = (1 + 2 + 4)(1 + 3) = 28 > 24$: abundant.
$\sigma(14) = (1 + 2)(1 + 7) = 24 < 28$: deficient.
$\sigma(28) = (1 + 2 + 4)(1 + 7) = 56 = 2 \cdot 28$: perfect.

Answer: Abundant, deficient, perfect.

Euclid's theorem. If $2^{p} - 1$ is prime, then $N = 2^{p-1}(2^{p} - 1)$ is perfect. Primes of the form $2^{p} - 1$ are called Mersenne primes.

Why it works

Let $q = 2^{p} - 1$, a prime. The factors $2^{p-1}$ and $q$ are coprime, and $\sigma$ is multiplicative, so $$\sigma(N) = \sigma(2^{p-1})\,\sigma(q) = (1 + 2 + \cdots + 2^{p-1})(1 + q) = (2^{p} - 1) \cdot 2^{p} = 2N.$$ About 2,000 years later Euler proved the converse for even numbers: every even perfect number has this form. Whether an odd perfect number exists is still unknown.

Worked example: Building a perfect number

$2^{7} - 1 = 127$ is prime. Which perfect number does it give?

$N = 2^{6} \cdot 127 = 64 \cdot 127 = 8128$.
Check: $\sigma(8128) = (2^{7} - 1)(127 + 1) = 127 \cdot 128 = 16{,}256 = 2 \cdot 8128$.

Answer: $8128$.

Which exponents can work? If the exponent is composite, $n = ab$ with $a, b > 1$, then $2^{a} - 1$ divides $2^{n} - 1$, because $x - 1$ divides $x^{b} - 1$ (take $x = 2^{a}$). For example $2^{6} - 1 = 63 = 7 \cdot 9$ and $2^{3} - 1 = 7$ divides it. So a Mersenne prime needs a prime exponent. But a prime exponent is not enough:

Worked example: A prime exponent that fails

Is $2^{11} - 1$ prime?

$2^{11} - 1 = 2047$. Test primes up to $\sqrt{2047} \approx 45.2$.
$3, 5, 7, 11, 13, 17, 19$ all leave remainders. Then $2047 = 23 \cdot 89$.

Answer: No: $2047 = 23 \cdot 89$.

The first Mersenne numbers with prime exponent.
$p$	$2^{p} - 1$	prime?	perfect number
2	3	yes	6
3	7	yes	28
5	31	yes	496
7	127	yes	8,128
11	2,047 = 23 · 89	no	—
13	8,191	yes	33,550,336

The largest primes known today are Mersenne primes, with tens of millions of digits, because there is a special fast test for numbers of the form $2^{p} - 1$. Only about fifty Mersenne primes are known. Abundant numbers are far more common: $12$ is the smallest, and the smallest odd one is $945$.

Common mistake

Believing that $2^{p} - 1$ is prime whenever $p$ is prime. The first counterexample is $p = 11$: $2^{11} - 1 = 2047 = 23 \cdot 89$. A prime exponent is necessary, not sufficient; each Mersenne number must be tested.

Key idea

$n$ is perfect when $\sigma(n) = 2n$. Whenever $2^{p} - 1$ is prime, $2^{p-1}(2^{p} - 1)$ is perfect, and every even perfect number arises this way.

Perfect Numbers and Mersenne Primes

Practice

Builds on

Leads to

Sources and further reading