# 8.4: Examples- Perfect Numbers

- Page ID
- 24845

Sometimes it takes a good bit of work and creativity to show that one set is a subset of another or that they are equal. We illustrate this now with examples from number theory involving what are called perfect numbers. Even though this topic is quite old, dating back more than 2000 years, it leads to some questions that are unanswered even today.

The problem involves adding up the positive divisors of a natural number. To begin the discussion, consider the number 12. If we add up the positive divisors of 12 that are less than 12, we obtain \(1+2+3+4+6 = 16\), which is greater than 12. Doing the same thing for 15, we get \(1+3+5 = 9\), which is less than 15. For the most part, given a natural number p, the sum of its positive divisors less than itself will either be greater than p or less than p. But occasionally the divisors add up to exactly p. If this happens, then p is said to be a perfect number.

Definition 8.1

A number \(p \in \mathbb{N}\) is **perfect **if it equals the sum of its positive divisors less than itself. Some examples follow.

- The number 6 is perfect since \(6 = 1+2+3\).
- The number 28 is perfect since \(28 = 1+2+4+7+14\).
- The number 496 is perfect since \(496 = 1+2+4+8+16+31+62+124+248\).

Though it would take a while to find it by trial-and-error, the next perfect number after 496 is 8128. You can check that 8128 is perfect. Its divisors are 1, 2, 4, 8, 16, 32, 64, 127, 254, 508, 1016, 2032, 4064 and indeed

\(8128 = 1+2+4+8+16+32+64+127+254+508+1016+2032+4064\).

Are there other perfect numbers? How can they be found? Do they obey any patterns? These questions fascinated the ancient Greek mathematicians. In what follows we will develop an idea—recorded by Euclid—that partially answers these questions. Euclid lived millennia before set theory was even invented, so he certainly did not use sets. Nonetheless we will phrase his idea in the language of sets.

Since our goal is to understand what numbers are perfect, let’s define the following set:

\(P = \{p \in \mathbb{N} : \text{p is perfect}\}\).

Therefore \(P = \{6,28,496,8128, \cdots\}\), but it is unclear what numbers are in P other than the ones listed. Our goal is to gain a better understanding of just which numbers the set P includes. To do this, we will examine the following set A. It looks more complicated than P, but it will be very helpful for understanding P, as we will soon see.

\(A = \{2^{n-1} (2^{n}-1) : n \in \mathbb{N}, \text{and} 2^{n}-1 \text{is prime}\}\).

In words, A consists of every natural number of form \(2^{n-1} (2^{n}-1)\), where \(2^{n}-1\) is prime. To get a feel for what numbers belong to A, look at the following table. For each natural number n, it tallies the corresponding numbers \(2^{n-1}\) and \(2^{n}-1\). If \(2^{n}-1\) happens to be prime, then the product \(2^{n-1} (2^{n}-1)\) is given; otherwise that entry is labeled with an ∗.

Notice that the first four entries of A are the perfect numbers 6, 28, 496 and 8128. At this point you may want to jump to the conclusion that \(A = P\). But it is a shocking fact that in over 2000 years no one has ever been able to determine whether or not \(A = P\). But it is known that \(A \subseteq P\), and we will now prove it. In other words, we are going to show that every element of A is perfect. (But by itself, that leaves open the possibility that there may be some perfect numbers in P that are not in A.)

The main ingredient for the proof will be the formula for the sum of a geometric series with common ratio r. You probably saw this most recently in Calculus II. The formula is

\(\sum_{k=0}^{n} r^k = \frac{r^{n+1}-1}{r-1}\).

We will need this for the case \(r = 2\), which is

\[\sum_{k=0}^{n} 2^k = 2^{n+1}-1\].

(See the solution for Exercise 19 in Section 7.4 for a proof of this formula.) Now we are ready to prove our result. Let’s draw attention to its significance by calling it a theorem rather than a proposition.

Theorem 8.1

If \(A= \{2^{n-1}(2^{n}-1) : n \in \mathbb{N}, \text{and} 2^{n}-1 \text{is prime}\}\) and \(P = \{p \in \mathbb{N}: \text{p is perfect}\}\), then \(A \subseteq P\).

Proof. Assume A and P are as stated. To show \(A \subseteq P\), we must show that \(p \in A\) implies \(p \in P\). Thus suppose \(p \in A\). By definition of A, this means

\[p = 2^{n-1}(2^{n}-1)\].

for some \(n \in \mathbb{N}\) for which \(2^{n}-1\) is prime. We want to show that \(p \in P\), that is, we want to show p is perfect. Thus, we need to show that the sum of the positive divisors of p that are less than p add up to p. Notice that since \(2^{n}-1\) is prime, any divisor of \(p = 2^{n-1}(2^{n}-1)\) must have the form \(2^k\) or \(2^{k}(2^{n}-1)\) for \(0 \le k \le n-1\). Thus the positive divisors of p are as follows:

\[\begin{array}{cccccc} {2^0,}&{2^1,}&{2^2,}&{\cdots}&{2^{n-2},}&{2^{n-1},} \nonumber \end{array}\]

\[\begin{array}{cccccc} {2^{0}(2^{n}-1),}&{2^1(2^{n}-1),}&{2^2(2^{n}-1),}&{\cdots}&{2^{n-2}(2^{n}-1),}&{2^{n-1}(2^{n}-1),} \nonumber \end{array}\]

Notice that this list starts with \(2^0 = 1\) and ends with \(2^{n-1}(2^{n}-1) = p\).

If we add up all these divisors except for the last one (which equals p) we get the following:

\(\sum_{k=0}^{n-1} 2^k + \sum_{k=0}^{n-2} 2^k(2^n-1) = \sum_{k=0}^{n-1} 2^k+(2^n-1) \sum_{k=0}^{n-2} 2^k\)

\(= (2^n-1) + (2^n-1)(2^{n-1}-1)\)

\(= (1+(2^{n-1}-1))(2^n-1)\)

\(= 2^{n-1}(2^{n}-1)\)

\(= p\)

This shows that the positive divisors of p that are less than p add up to p. Therefore p is perfect, by definition of a perfect number. Thus \(p \in P\), by definition of P.

We have shown that \(p \in A\) implies \(p \in P\), which means \(A \subseteq P\).

Combined with the chart on the previous page, this theorem gives us a new perfect number! The element \(p = 2^{13-1}(2^{13}-1) = 33,550,336\) in A is perfect.

Observe also that every element of A is a multiple of a power of 2, and therefore even. But this does not necessarily mean every perfect number is even, because we’ve only shown \(A \subseteq P\), not \(A = P\). For all we know there may be odd perfect numbers in \(P - A\) that are not in A.

Are there any odd perfect numbers? No one knows.

In over 2000 years, no one has ever found an odd perfect number, nor has anyone been able to prove that there are none. But it is known that the set A does contain every even perfect number. This fact was first proved by Euler, and we duplicate his reasoning in the next theorem, which proves that \(A = E\), where E is the set of all even perfect numbers. It is a good example of how to prove two sets are equal.

For convenience, we are going to use a slightly different definition of a perfect number. A number \(p \in \mathbb{N}\) is **perfect **if its positive divisors add up to 2p. For example, the number 6 is perfect since the sum of its divisors is \(1+2+3+6 = 2 \cdot 6\). This definition is simpler than the first one because we do not have to stipulate that we are adding up the divisors that are less than p. Instead we add in the last divisor p, and that has the effect of adding an additional p, thereby doubling the answer.

Theorem 8.2

If \(A = \{2^{n-1}(2^{n}-1) : n \in \mathbb{N}, \text{and} 2^{n}-1 \text{is prime}\}\) and \(E = \{p \in \mathbb{N}: \text{p is perfect and even}\}\), then \(A = E\).

Proof. To show that \(A = E\), we need to show \(A \subseteq E\) and \(E \subseteq A\).

First we will show that \(A \subseteq E\). Suppose \(p \in A\). This means p is even, because the definition of A shows that every element of A is a multiple of a power of 2. Also, p is a perfect number because Theorem 8.1 states that every element of A is also an element of P, hence perfect. Thus p is an even perfect number, so \(p \in E\). Therefore \(A \subseteq E\).

Next we show that \(E \subseteq A\). Suppose \(p \in E\). This means p is an even perfect number. Write the prime factorization of p as \(p = 2^{k}3^{n_{1}}5^{n_{2}}7^{n_{3}} \cdots\), where some of the powers \(n_{1}, n_{2}, n_{3} \cdots\) may be zero. But, as p is even, the power k must be greater than zero. It follows \(p = 2^{k}q\) for some positive integer k and an odd integer q. Now, our aim is to show that \(p \in A\), which means we must show p has form \(p = 2^{n-1}(2^{n}-1)\). To get our current \(p = 2^{k}q\) closer to this form, let \(n = k+1\), so we now have

\[p = 2^{n-1}q\].

List the positive divisors of q as \(d_{1}, d_{2}, d_{3}, \cdots, d_{m}\). (Where \(d_{1} =1\) and \(d_{m} = q\).)

Then the divisors of p are:

\[\begin{array}{cccc} {2^{0}d_{1}}&{2^{0}d_{2}}&{2^{0}d_{3}}&{\cdots}&{2^{0}d_{m}}\\ \nonumber \end{array}\]

\[\begin{array}{cccc} {2^{1}d_{1}}&{2^{1}d_{2}}&{2^{1}d_{3}}&{\cdots}&{2^{1}d_{m}}\\ \nonumber \end{array}\]

\[\begin{array}{cccc} {2^{2}d_{1}}&{2^{2}d_{2}}&{2^{2}d_{3}}&{\cdots}&{2^{2}d_{m}}\\ \nonumber \end{array}\]

\[\begin{array}{cccc} {2^{3}d_{1}}&{2^{3}d_{2}}&{2^{3}d_{3}}&{\cdots}&{2^{3}d_{m}}\\ \nonumber \end{array}\]

\[\begin{array}{cccc} {\cdots}&{\cdots}&{\cdots}&{\cdots}&{\cdots}\\ \nonumber \end{array}\]

\[\begin{array}{cccc} {2^{n-1}d_{1}}&{2^{n-1}d_{2}}&{2^{n-1}d_{3}}&{\cdots}&{2^{n-1}d_{m}}\\ \nonumber \end{array}\]

Since p is perfect, these divisors add up to 2p. By Equation (8.3), their sum is \(2p = 2(2^{n-1}q) = 2^{n}q\). Adding the divisors column-by-column, we get

\(\sum_{k=0}^{n-1} 2^{k}d_{1}+\sum_{k=0}^{n-1} 2^{k}d_{2}+\sum_{k=0}^{n-1} 2^{k}d_{2}+\cdots+\sum_{k=0}^{n-1} 2^{k}d_{m}= 2^{n}q\).

Applying Equation (8.1), this becomes

\((2^{n}-1)d_{1}+(2^{n}-1)d_{2}+(2^{n}-1)d_{3}+\cdots+(2^{n}-1)d_{m} = 2^{n}q\)

\((2^{n}-1)(d_{1}+d_{2}+d_{3}+\cdots+d_{m}) = 2^{n}q\)

\(d_{1}+d_{2}+d_{3}+\cdots+d_{m} = \frac{2^{n}q}{2^{n}-1}\)

so that

\(d_{1}+d_{2}+d_{3}+\cdots+d_{m} = \frac{(2^{n}-1+1)q}{2^{n}-1} = \frac{(2^{n}1)q+q}{2^{n}-1} = q+\frac{q}{2^{n}-1}\).

From this we see that \(\frac{q}{2^{n}-1}\) is an integer. It follows that both q and \(\frac{q}{2^{n}-1}\) are positive divisors of q. Since their sum equals the sum of all positive divisors q, it follows that q has only two positive divisors, q and \(\frac{q}{2^{n}-1}\). Since one of its divisors must be 1,it must be that \(\frac{q}{2^{n}-1} = 1\), which means \(q=2^{n}-1\). Now a number with just two positive divisors is prime, so \(q = 2^{n}-1\) is prime. Plugging this into Equation (8.3) gives \(p = 2^{n-1}(2^{n}-1)\), where \(2^{n}-1\) is prime. This means \(p \in A\), by definition of A. We have now shown that \(p \in E\) implies \(p \in A\), so \(E \subseteq A\).

Since \(A \subseteq E\) and \(E \subseteq A\), it follows that \(A = E\).

Do not be alarmed if you feel that you wouldn’t have thought of this proof. It took the genius of Euler to discover this approach.

We’ll conclude this chapter with some facts about perfect numbers.

- The sixth perfect number is \(p = 2^{17-1}(2^{17}-1) = 8589869056\).
- The seventh perfect number is \(p = 2^{19-1}(2^{19}-1) = 137438691328\).
- The eighth perfect number is \(p = 2^{31-1}(2^{31}-1) = 2305843008139952128\).
- The twentieth perfect number is \(p = 2^{4423-1}(2^{4423}-1)\). It has 2663 digits.
- The twenty-third perfect number \(p = 2^{11,213-1}(2^{11,213}-1)\). has 6957 digits.
- The fiftieth perfect number is \(p = 2^{77,232,917-1}(2^{77,232,917}-1)\).

As mentioned earlier, no one knows whether or not there are any odd perfect numbers. It is not even known whether there are finitely many or infinitely many perfect numbers. It **is **known that the last digit of every even perfect number is either a 6 or an 8. Perhaps this is something you’d enjoy proving.

We’ve seen that perfect numbers are closely related to prime numbers having the form \(2^{n}-1\). Such prime numbers are called **Mersenne primes**, after the French scholar Marin Mersenne (1588–1648), who popularized them. The first several Mersenne primes are \(2^2-1 = 3\), \(2^3-1 = 7\), \(2^5-1 = 31\), \(2^7-1 = 127\) and \(2^{13}-1 = 8191\). To date, only 51 Mersenne primes are known, the largest of which is \(2^{82,589,933}-1\). There is a substantial cash prize for anyone who finds a \(52^{nd}\). (See https://www.mersenne.org/.) You may have better luck with the exercises.