1.16: Perfect Numbers and Mersenne Primes

In this chapter we discuss perfect numbers.\(^{1}\)

Definition \(\PageIndex{1}\): Perfect

An integer \(n>1\) is perfect if \(\sigma^\ast(n)=n\); in other words, \(n\) is perfect if it equals the sum of its proper divisors.

An equivalent way to define perfect numbers is as those numbers \(n\) for which \(\sigma(n)=2n\).

Example \(\PageIndex{1}\)

The proper divisors of \(6\) are \(1\), \(2\) and \(3\). So \(\sigma^\ast(6)=6\). Therefore \(6\) is perfect.

If you do a search for perfect numbers up to 10,000 you will find only the following perfect numbers: \[\begin{aligned} 6 &=2\cdot 3, \\ 28 &=2^2\cdot 7, \\ 496 &=2^4\cdot 31, \\ 8128 &=2^6\cdot 127.\end{aligned}\] Note that \(2^2=4\), \(2^3=8\), \(2^5=32\), \(2^7=128\) so we have: \[\begin{aligned} 6 &=2 \cdot (2^2-1), \\ 28 &=2^2\cdot(2^3-1), \\ 496 &=2^4\cdot(2^5-1), \\ 8128 &=2^6\cdot(2^7-1).\end{aligned}\] Note also that \(2^2-1\), \(2^3-1\), \(2^5-1\), \(2^7-1\) are Mersenne primes. One might conjecture that all perfect numbers follow this pattern. We discuss to what extent this is known to be true. We start with the following result.

Theorem \(\PageIndex{1}\): Mersenne Yields Perfect

If \(2^p-1\) is a Mersenne prime, then \(2^{p-1}\cdot(2^p-1)\) is perfect.

Proof

Write \(q=2^p-1\) and let \(n=2^{p-1}q\). If \(q\) is a Mersenne prime, then since it is odd and prime, by Theorem 1.15.1(2) we have \(\sigma(n)=\sigma\left(2^{p-1}q\right)=\left(\frac{2^p-1}{2-1}\right) \left(\frac{q^2-1}{q-1}\right)=(2^p-1)(q+1) = (2^p-1)2^p = 2n\). That is, \(\sigma(n) = 2n\) and \(n\) is perfect.

Now we show that all even perfect numbers have the conjectured form.

Theorem \(\PageIndex{2}\): Even Perfects

If \(n\) is even and perfect then there is a Mersenne prime \(2^p-1\) such that \(n=2^{p-1}(2^p-1)\).

Proof

Let \(n\) be even and perfect. Since \(n\) is even, \(n=2m\) for some \(m\). We take out as many powers of \(2\) as possible, obtaining \[n=2^k\cdot q,\quad k\ge 1\text{, $q$ odd}.\nonumber \] Since \(n\) is perfect, \(\sigma^\ast(n)=n\), that is, \(\sigma(n)=2n\). Since \(q\) is odd, \(\gcd(2^k,q)=1\), so by Lemmas 1.15.1 and 1.15.2, \[\sigma(n)=\sigma(2^k)\sigma(q)=(2^{k+1}-1)\sigma(q).\nonumber \] So we have \[2^{k+1}q=2n=\sigma(n)=(2^{k+1}-1)\sigma(q),\nonumber \] hence \[\label{eq: thm 16-2 first} 2^{k+1}q=(2^{k+1}-1)\sigma(q).\] Now \(\sigma^\ast(q)=\sigma(q)-q\), so \[\sigma(q)=\sigma^\ast(q)+q.\nonumber \] Putting this in equation \(\eqref{eq: thm 16-2 first}\) we get \[2^{k+1}q=(2^{k+1}-1)(\sigma^\ast(q)+q)\nonumber \] or \[2^{k+1}q=(2^{k+1}-1)\sigma^\ast(q)+2^{k+1}q-q,\nonumber \] which implies \[\label{eq: thm 16-2 second} \sigma^\ast(q)(2^{k+1}-1)=q.\] In other words, \(\sigma^\ast(q)\) is a divisor of \(q\). Since \(k\ge 1\) we have \(2^{k+1}-1\ge 4-1=3\). So \(\sigma^\ast(q)\) is a proper divisor of \(q\). But \(\sigma^\ast(q)\) is the sum of all proper divisors of \(q\). This can only happen if \(q\) has only one proper divisor. This means that \(q\) must be prime and \(\sigma^\ast(q)=1\). Then equation \(\eqref{eq: thm 16-2 second}\) shows that \(q=2^{k+1}-1\). So \(q\) must be a Mersenne prime and \(k+1=p\) is prime. So \(n=2^{p-1}(2^p-1)\), as desired.

Corollary \(\PageIndex{1}\)

There is a one-to-one correspondence between even perfect numbers and Mersenne primes.

Even knowing of the strong connection between perfect numbers and Mersenne primes, a number of well-known questions remain.

Open questions

• Are there infinitely many perfect numbers?
• Are there any odd perfect numbers?

Of course showing that there are infinitely many Mersenne primes would answer the first question.

So far no one has found a single odd perfect number. It is known that if an odd perfect number exists, it must be \(>10^{50}\).

The idea of a perfect number is pretty old, as is the result of Theorem \(\PageIndex{1}\). Euclid’s Elements\(^{2}\) defines perfect numbers at the beginning of Book VII, and a proof that Mersenne primes can be used to build the even perfect numbers appears as Proposition 36 in Book IX. Of course, Euclid’s use of “Mersenne” primes dates to about 1800 years before Mersenne was born, so he didn’t use exactly that terminology (or our modern algebraic notation), but the ideas are similar and worth a read.

Some even think that Euclid’s knowledge that \(2^{p-1}(2^p-1)\) is perfect when \(2^p-1\) is prime may have been his motivation for defining prime numbers.

Exercises

Exercise \(\PageIndex{1}\)

Use the definition of perfect numbers to determine which of the following numbers are perfect, showing your work.

1. \(n=28\)
2. \(n=32\)
3. \(n=128\)
4. \(n=496\)
5. \(n=900\)
6. \(n=1024\)
7. \(n=8128\)

Exercise \(\PageIndex{2}\)

Prove that if \(n\) is a perfect number, then \(\displaystyle\sum_{d \mid n} \frac{1}{d} = 2,\) where the sum is over positive divisors \(d\) of \(n\).

(Hint: If you cleared the denominators in this equation, what would the equation look like?)

Exercise \(\PageIndex{3}\)

1. Using results from this chapter, show that if \(M\) is a Mersenne prime, then \(\frac{1}{2}M(M+1)\) is a perfect number.
2. Show that if \(M\) is a Mersenne prime, then the sum \[1+2+3+\dots + M\nonumber \] is a perfect number. (Hint: use part (a), and if necessary, look at the formula in Exercise 1.3.3.)

The next two exercises show that the sets of perfect squares (numbers of the form \(n^2\)) and of perfect numbers do not overlap.

Exercise \(\PageIndex{4}\)

Show that if \(n\) is odd, then \(n^2\) is not perfect.

(Hint: Compare the parities of \(n^2\) and \(\sigma^*(n^2)\).)

Exercise \(\PageIndex{5}\)

Show that if \(n\) is even, then \(n^2\) is not perfect.

(Hint: use Theorem \(\PageIndex{2}\).)

Footnotes

[1] Note that our usage of "perfect" here and the expression "perfect square" elsewhere in the text are unrelated; squares of integers are never perfect numbers (see Exercises \(\PageIndex{4}\) and \(\PageIndex{5}\) at the end of the chapter), so there is no perfect perfect square!

[2] Remember that we've already come across Elements in Sections 1.8 and 1.11 and 1.12. This ancient text definitely contains some gems!