The Mysterious Math of Perfect Numbers

Mona Lisa’s smile. Mary Lou Retton’s Olympic vault. Mariah Carey’s musical pitch. All are considered perfect. So are the numbers 6 and 28. With feats of artistry and athleticism, perfection lies in the eye of the beholder. But for numbers, perfection is mathematically defined. “Perfect numbers” are equal to the sum of their “proper” divisors (positive integers that divide a number evenly, not counting itself). For example, 6 = 3 + 2 + 1, and 28 = 14 + 7 + 4 + 2 + 1. While these mathematical curiosities are about as likely to grace the walls of the Louvre as they are to perform a twisting layout back somersault, they do offer something irresistible: a perfect mystery. Euclid laid out the basics of perfect numbers over 2,000 years ago, and he knew that the first four perfect numbers were 6, 28, 496 and 8,128. Since then, many more perfect numbers have been discovered. But, curiously, they’re all even. No one has been able to find an odd perfect number, and after thousands of years of unsuccessful searching, it might be tempting to conclude that odd perfect numbers don’t exist. But mathematicians haven’t been able to prove that either. How is it that we can know so much about even perfect numbers without being able to answer the simplest question about an odd one? And how are modern mathematicians trying to resolve this ancient question? Our exploration of mathematical perfection begins with divisors. We know that 6 is a divisor of 12 since $latex \frac{12}{6}$ = 2, and we know 25 is a divisor of 100 since $latex \frac{100}{25}$ = 4. As we said, we know a number is perfect when it is equal to the sum of its proper divisors — those divisors that are less than the number itself. We can also define a number as perfect when the sum of all its divisors, proper and improper, is twice the number. This works out because the only improper divisor of a number is the number itself. We see that 28 is still perfect by this definition: Its proper divisors are 1, 2, 4, 7 and 14, its improper divisor is 28, and the sum of all its divisors, 1 + 2 + 4 + 7 + 14 + 28, is 56, which is 2 × 28. Including the improper divisor in the sum is convenient for some of the algebra we’ll do with perfect numbers, as we’ll see shortly. When working with perfect numbers we end up saying “the sum of the divisors of a number” a lot, so mathematicians made things easier by turning this into a function. We’ll define σ(n), or “sigma of n,” to be the sum of the divisors of n. We already know that σ(28) = 56. Some other examples: σ(1) = 1, σ(6) = 1 + 2 + 3 + 6 = 12, and σ(10) = 1 + 2 + 5 + 10 = 18. Notice that 6 is a perfect number, since σ(6) = 2 × 6, but 1 and 10 are not. As we’ll see, this function σ has some special properties that are perfect for studying perfect numbers. So we’ve got our basic definition of perfect numbers and a new mathematical tool to help us find them. Where should we start looking? We’ll start where mathematicians always start when studying numbers and their patterns: the primes. A prime number, by definition, is divisible only by itself and 1. This makes computing σ for a prime number quite easy: σ(2) = 1 + 2 = 3, σ(3) = 1 + 3 = 4, σ(5) = 1 + 5 = 6, and σ(7) = 1 + 7 = 8. In general, for any prime number p, σ(p) = 1 + p. Could a prime number be perfect? Only if σ(p) = 1 + p = 2p. A little bit of algebra tells us this will be true whenever p = 1, but since prime numbers are greater than 1 by definition, no prime could be perfect. So we know primes can’t be perfect. Where should we look next? Powers of primes — numbers like 24, 53 or 1136 — are a good next step, as their divisors are easy to organize. Consider a prime power like 16, or 24. The only divisors of 24 are the powers of 2 up to 24: 20 = 1, 21 = 2, 22 = 4, 23 = 8, 24 = 16. So σ(24) can be computed like this: σ(24) = 1 + 2 + 22 + 23 + 24 = 1 + 2 + 4 + 8 + 16 = 31. And this generalizes. For any prime power pn σ(pn) = 1 + p + p2 + p3 + … + pn. This becomes even easier if we use a formula from algebra class. Notice that each of the terms being added up in σ(pn) is p times the previous term. This makes this a so-called geometric series, and there’s a nice formula for the sum of a geometric series: 1 + p + p2 + p3 +…+ pn = $latex \frac{p^{n+1}-1}{p-1}$. (For more on this amazing formula, see the exercises at the end of the column.) Thanks to the geometric series formula, we don’t have to list out all the divisors of pn to compute σ(pn). We can just use the formula: σ(pn) = 1 + p + p2 + p3 +…+ pn = $latex \frac{p^{n+1}-1}{p-1}$. For example, we’ve already seen that σ(24) = 1 + 2 + 22 + 23 + 24 = $latex \frac{2^{5}-1}{2-1}$ = $latex \frac{32-1}{1}$ = 31. And we can compute the sum of the divisors of other prime powers by just plugging them into the formula: σ(27) = σ(33) = $latex \frac{3^{4}-1}{3-1}$ = $latex \frac{81-1}{2}$ = 40 and σ(121) = σ(112) = $latex \frac{11^{3}-1}{11-1}$ = $latex \frac{1331-1}{10}$ = 133. Notice that none of these prime powers satisfies the condition for being perfect: σ(24) ≠ 2 × 24, σ(33) ≠ 2 × 33, and σ(112) ≠ 2 × 112. In fact, no prime power can be perfect. To get a perfect number we need σ(pn) = 2pn, which would mean: 1 + p + p2 + p3 + … + pn-1 + pn = 2pn. We can subtract pn from both sides of the equation to give us: 1 + p + p2 + p3 + … + pn-1 = pn. Now we’ll use the geometric series formula on the left-hand side of this equation: Since 1 + p + p2 + p3 + … + pn-1 = $latex \frac{p^{n}-1}{p-1}$ we get $latex \frac{p^{n}-1}{p-1}$ = pn. We need this to be true for pn to be perfect. But notice that pn – 1 is smaller than pn, and dividing pn – 1 by p – 1 will make it even smaller, so $latex \frac{p^{n}-1}{p-1}$ < pn. And thus no prime power pn can be perfect. So no perfect primes, and no perfect prime powers. What can be perfect? Well, we know 28 is perfect, and it is the product of two distinct prime powers: 28 = 22 × 7. Any number that isn’t a prime or a prime power can be written as the product of distinct prime powers like this. And these factorizations, together with a special property of the function σ, can help us determine if a number is perfect. We already know that σ(28) = 1 + 2 + 4 + 7 + 14 + 28, but let’s take a closer look at that sum. Notice that each of the last three numbers is a multiple of 7: We can factor out that 7 to reveal some hidden structure: σ(28) = (1 + 2 + 4) + 7 × (1 + 2 + 4). And with some more clever factoring with the distributive property, we can write σ(28) = (1 + 2 + 4)(1 + 7). This doesn’t tell us anything we didn’t already know: σ(28) = (1 + 2 + 4)(1 + 7) = 7 × 8 = 56, which confirms that 28 is perfect. But there’s something important hiding inside that multiplication: $latex \begin{aligned}σ(28) &= (1 + 2 + 4) (1 + 7)\\&= (1 + 2^1 + 2^2)(1 + 7^1).\end{aligned}$ Those expressions in parentheses look familiar: 1 + 21 + 22 = σ(22), and 1 + 71 = σ(7). This means that we can actually write σ(28) = σ(22)σ(7). To compute σ(28) = σ(22 × 7) we can actually compute σ(22) and σ(7) and multiply them. This is a surprise, and it’s true in general: Any time you factor a number into primes like this you can use this shortcut to compute σ. For example, since 100 = 22×52, we can compute σ(100) like this: σ(100) = σ(22)σ(52) = (1 + 2 + 4)(1 + 5 + 25) = 7 × 31 = 217, which is a bit easier than listing all nine divisors of 100 and adding them up. Why does this work? Well, the divisors of a number come from its prime factors. Consider 28 again, which is the product of 22 and 7, and think about the multiplication table below: x 1 2 4 1 7 Along the top are the powers of 2 that evenly divide 28, and down the side are the powers of 7 that evenly divide 28. Notice what happens when we fill out this multiplication table. x 1 2 4 1 1 2 4 7 7 14 28 We get all the divisors of 28. That’s because every divisor of 28 is a combination of divisors of 22 and 7, the prime powers that appear in the factorization of 28. Now compare the multiplication table with the expression (1 + 2 + 4)(1 + 7). When we multiply this out using the distributive property, this also produces all the divisors of 28 and then adds them up: (1 + 2 + 4)(1 + 7) = 1 × 1 + 2 × 1 + 4 × 1 + 7 × 1 + 7 × 2 + 7 × 4. In other words, (1 + 2 + 4)(1 + 7) is exactly σ(28). But (1 + 2 + 4)(1 + 7) is also σ(22)σ(7). So σ(22)σ(7) = σ(28). This example demonstrates a very useful fact about σ: In the language of number theory, this function is “multiplicative.” That means that σ(ab) = σ(a)σ(b) whenever the numbers a and b are “relatively prime,” meaning they have no factors in common. This is the special feature of σ that’s perfect for helping us study perfect numbers. Euclid used this fact 2,000 years ago to create a formula for finding perfect numbers, with help from a special kind of prime and a clever argument about products and divisors. In doing so, he took the first step toward determining what every even perfect number has to look like. Let’s see how he did it. First, notice that for any power of 2 we have σ(2k) = $latex \frac{2^{k+1}-1}{2-1}$ = 2k+1 – 1. This is a consequence of the geometric series formula we discussed earlier. Now consider the following thought experiment: What if 2k+1 – 1 is prime? Well, since σ(p) = 1 + p for any prime, we know that σ(2k+1 – 1) = 1 + 2k+1 – 1 = 2k+1. And notice that 2k+1 is exactly twice 2k, because of the law of exponents that says 2 × 2k = 2k+1. So we have the following two interesting relationships between the numbers 2k and 2k+1 – 1: σ(2k) = 2k+1 – 1 and σ(2k+1 – 1) = 2k+1 = 2 × 2k. Euclid noticed a clever way to leverage these relationships: He put the two numbers together to make the number M = 2k × (2k+1 – 1), and as long as (2k+1 – 1) is prime, this number is perfect! To see this, we’ll compute σ(M) and show it is equal to 2M. First, notice that 2k+1 – 1 is one less than an even number so it must be odd. This means 2k+1 – 1 is not divisible by 2. But 2k is only divisible by powers of 2. So 2k and 2k+1 – 1 have no common factors and are thus relatively prime. This allows us to use the multiplicative property of σ: We already know that σ(2k) = 2k+1 – 1 and σ(2k+1 – 1) = 2k+1 = 2 × 2k, so we can find σ(M): $latex \begin{aligned}\sigma(M)&=\sigma\left(2^{k} \times\left(2^{k+1}-1\right)\right)\\&=\sigma\left(2^{k}\right) \sigma\left(2^{k+1}-1\right)\\&=\left(2^{k+1}-1\right)\left(2 \times 2^{k}\right)\\&=\left(2 \times 2^{k}\right)\left(2^{k+1}-1\right)\\&=2\left(2^{k} \times\left(2^{k+1}-1\right)\right)\\&=2(M).\end{aligned}$ So M = 2k × (2k+1 – 1) is perfect, as claimed. Keep in mind that this relies on the assumption that the number 2k+1 – 1 is prime. These numbers are called Mersenne primes, and you might have heard of them because of the Great Internet Mersenne Prime Search (GIMPS), a collaborative online computing effort to find huge Mersenne primes. Anytime you hear about the discovery of a new largest prime number, it’s probably the result of GIMPS. And thanks to Euclid’s proof, anytime a new Mersenne prime is discovered, a new perfect number is discovered as well. For example, 25 – 1 = 31 is a Mersenne prime, and so 24(25-1) = 16 × 31 = 486 is a perfect number. Also, 22 – 1 = 3 is a Mersenne prime, so 21(22 – 1) = 2 × 3 = 6 is perfect. And 23 – 1 = 7 is a Mersenne prime, so 22(23 – 1) = 4 × 7 = 28 is perfect. You may have noticed that all these perfect numbers are even. This makes sense, because as long as k > 0, the number 2k × (2k+1 – 1) will be even. (And if k = 0 then 2k+1 – 1 is 1, which is not a prime.) You may also have noticed that all the perfect numbers we’ve discussed so far seem to involve Mersenne primes. That’s no coincidence: 2,000 years after Euclid showed that this formula generates perfect numbers, Leonhard Euler proved that this is the only way to get even perfect numbers. But the question of what odd perfect numbers might be like (if they exist) remained open. And it remains open today. Although they can’t find one, mathematicians have a lot of information about what a hypothetical odd perfect number might look like. It can’t be divisible by 105. It would have to have at least nine distinct prime factors, the second-largest of which would have to be greater than 10,000. And it would have to have a remainder of 1 when divided by 12 or a remainder of 9 when divided by 36. It might seem strange to prove results about numbers that might not even exist. But every new rule narrows the search a little more. And if they’re lucky, mathematicians might just prove that odd perfect numbers have to satisfy two incompatible criteria, which would prove once and for all that no odd perfect number exists. On the hunt for incompatible criteria, mathematicians have even started looking at numbers that aren’t quite perfect. A “spoof perfect number” is a number that looks perfect if you pretend one of its non-prime factors is actually prime. For example, 60, the product of 3, 4 and 5, can be considered “spoof perfect”: If you pretend that the 4 in its factorization is a prime, then the shortcuts we developed for σ give us (1+3)(1+4)(1+5) = 4 × 5 × 6 = 120. If σ(60) equaled 120, then 60 would be perfect. Of course, σ(60) doesn’t actually equal 120, but it looks like it if we pretend 4 is a prime. That’s what makes it a spoof. These spoofs are like generalizations of perfect numbers, and so anything true about a spoof would have to be true about a perfect number as well. Understanding odd spoofs would be especially useful, since any rule discovered for odd spoofs could be added to the existing rules for odd perfect numbers, increasing the chances of finding contradictory criteria and tightening the overall search space. René Descartes, yet another famous mathematician drawn into the mystery of perfect numbers, discovered the first odd spoof perfect number, and he challenged mathematicians to find others. In taking up the challenge, mathematicians have broadened the concept of a spoof and have discovered a new class of numbers to study. For the most part, investigations into these spoof perfect numbers are done simply for the joy of mathematical exploration. But perhaps something we learn about spoofs will help us prove that actual odd perfect numbers can’t exist, or perhaps it will lead us to one. It may seem strange to spend thousands of years hunting for numbers with curious properties, proving theorems about objects that might not even exist, and inventing new and even stranger worlds of numbers to explore. But to a mathematician, it makes perfect sense. Exercises 1. A number is called “abundant” if it is less than the sum of its proper divisors. For example, 36 is abundant, since 1 + 2 + 3 + 4 + 6 + 9 + 12 + 18 = 55, which is greater than 36. What’s the smallest abundant number? 2. A number is “deficient” if it is greater than the sum of its proper divisors. For example, 35 is deficient, since 1 + 5 + 7 = 13, which is less than 35. Are prime powers deficient or abundant? 3. Use the distributive property to multiply (p – 1)(1 + p + p2 + p3 + … + pn) and simplify. 4. Suppose N is an odd number and assume that M = 2N and is perfect. Show that N must be equal to 3. Answers Click for Answer 1: The smallest abundant number is 12. The smallest odd abundant number is much, much larger! You can prove that there are infinitely many abundant numbers by proving that the multiple of an abundant number is abundant. Click for Answer 2: Above, we proved that 1 + p + p2 + p3 + … + pn-1 = $latex \frac{p^{n}-1}{p-1}$ < pn, which makes prime powers deficient. Of course, primes are deficient since the sum of the proper divisors of a prime is always 1. Notice that this proves that there are infinitely many deficient numbers. Click for Answer 3: Using the distributive property, we get Notice that since (p-1)(1 + p + p2 + p3 + … + pn) = pn+1 – 1, we can divide both sides of the equation by p – 1 to get 1 + p + p2 + p3 + … + pn = $latex\frac{p^{n+1}-1}{p-1}$, the formula for the sum of a geometric series. Click for Answer 4: Since M = 2N and is perfect, we have σ(M) = σ(2N) = 4N. But since N is odd, N and 2 are relatively prime, so σ(2N) = σ(2)σ(N) = 3σ(N). So 4N = 3σ(N). Since both sides of this equation are integers and 3 does not divide 4, 3 must divide N. So we can write 4$latex \frac{N}{3}$ = σ(N). Since $latex \frac{N}{3}$ must be an integer, it is also a divisor of N. N is also a divisor of N, so we know that the sum of the divisors of N is at least the sum of these two. That is, σ(N) ≥ N + $latex \frac{N}{3}$ = $latex \frac{4}{3}$N. But we already know that σ(N) = $latex \frac{4}{3}$N. If N had any more divisors, σ(N) would be greater than $latex \frac{4}{3}$N, so 3 must be its only divisor. Thus N = 3 as claimed. This is a specific application of Euler’s proof that every even perfect number is of the form M = 2k × (2k+1 – 1), where 2k+1 – 1 is a Mersenne prime.