Euler’s Odd Perfect Numbers Theorem

An ancient proof to give insight into an unsolved problem.

Euler’s Odd Perfect Numbers Theorem
Photo by Tim Mossholder on Unsplash

Perfect numbers have fascinated me for a long time. The concept is simple. Take any number and write out the numbers that divide it (not including itself).

For example: 1,2, and 3 all divide 6 evenly. Now add those factors 1+2+3=6.

When you get the number back like this, the number is called a perfect number.

Later, we’ll want to work with the full sum-of-divisors function.

Define σ(N) to be the sum of all divisors of N (including N itself). Note that when you include the number itself, we get the definition: a number N is perfect if σ(N)=2N.

Most numbers are not perfect. In fact, you can quickly check for yourself that 6 is the smallest perfect number and then the next one is 28. There’s a surprisingly large number of results on the form of perfect numbers, but the two most obvious questions remain unsolved to this day:

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

If you could solve either of these, you’d become famous. They look so simple, and yet they’ve resisted thousands of attempts at proofs or counterexamples.

The first question can be converted into many other famous questions, so we won’t concern ourselves with it today.

What I find interesting is that Euler proved that odd perfect numbers had to have a very specific form back in the 1700s, and yet we still don’t know if they exist!

Currently, computers have checked up to around 10¹⁵⁰⁰ and not found any. New results about odd perfect numbers have been published as recently as this year. So this is still an active area of research.

Today, we’ll go through Euler’s elementary proof of the form of odd perfect integers, and maybe one of you will be able to crack it.

The Form of Odd Perfect Numbers

Despite the fact that we don’t know if any exist, the form an odd perfect number must take has been known for centuries.

Here’s the theorem statement. If N is an odd perfect number, then

where p is a prime number of the form p=4n+1 and does not divide Q. In other words, an odd perfect number must be a perfect square times a specific type of prime number to a specific type of power (1, 5, 9, …).

You can plug in numbers to get a feel for this. If n is 1, then the prime p=5. If Q is 3, then the perfect square is 9. This would make N=45. The (proper) divisors of 45 are 1, 3, 5, 9, 15. Adding these up gives us 33, so 45 is not perfect.

As you see, the theorem doesn’t produce odd perfect numbers. It just tells us if one exists, it must be of that form. Again, there has been a lot of work on this in the centuries since this was first proved, so we have more refined forms these days. I’ll mention those at the end.

For now, let’s actually prove it. The proof is completely elementary and only involves cleverly thinking about evens and odds and working out all possibilities.

Despite involving no high-level math, I will warn you that it’s hard to hold in your head all at once because it just brute force checks all cases. So it’s easy to lose track of what we’re doing and why. I’ll try to make it clear.

Preliminary Concepts

Before we begin, we need formal definitions of even and odd numbers. A number x is odd if it can be expressed as x=2k+1 for some k. A number x is even if it can be expressed as x=2k for some k.

Fact 1: An odd number plus an odd number is always even. You can convince yourself of it by thinking about it, but it can also be proved formally.

Let x and y be odd. Then x=2k+1 and y=2j+1 for some k and j. Thus,

x+y=2k+1+2j+1
=2k+2j+2
=2(k+j+1).

This is the definition of being even, so we’re done.

Fact 2: An odd number plus an even number is always odd. You can prove this for yourself following the above similar proof.

Fact 3: The divisors of pⁿ where p is a prime number are just 1, p, p², …, pⁿ. This is just the definition of being a prime number.

Fact 4: The sum of divisors of pⁿ (notated σ(pⁿ)) is even if and only if n is odd. This is just the combination of the above three facts: 1+p is even, 1+p+p² is odd, 1+p+p²+p³ is even, and so on.

Likewise, σ(pⁿ) is odd if and only if is even.

Fact 5: The sum of divisors is weakly multiplicative. This means that if N and Mhave no prime factors in common, then σ(NM)=σ(N)σ(M).

I won’t prove this in full generality, but a simple example gives the exact flavor of the proof. Try it for N=3 and M=5.

σ(15)=1+3+5+15
=(1+3)(1+5)
=σ(3)σ(5)

The general proof follows this same logic. You break a number into its prime factorization and then factor.

A Proof of Euler’s Form

Let N be an odd perfect integer. Use the Fundamental Theorem of Arithmetic to factor N into its unique prime factorization:

Since N is odd, none of the primes in the factorization are 2. Since N is perfect, we know that σ(N)=2N. Now we’ll use the definition with the above facts to get the key equation we’ll need.

Here’s the key insight. Only one of those factors can be even.

This is because the upper left part of the equation has only a single factor of 2 since N is odd. If two of the bottom right factors were even, we’d be able to factor out 4, a contradiction.

Since only one factor is even, this says all other factors are odd. Fact 4 tells us that all the aᵢ in the prime factorization of N are even except for a single odd one.

In other words, we can write N=pˣQ² where x is odd and p does not divide Q.

Suppose, p=4b+3 for some b. Then we notice that we can factor σ(pˣ)=(1+p)(1+p²+…+pˣ⁻¹)). This means 1+p divides σ(pˣ) which divides 2N, by assumption.

But this is a contradiction, because 1+p=4b+4=4(b+1), and we already said that 4 can be a factor of 2N. Since p is odd, the only other possibility is that it has the form 4b+1 for some b, which is what we set out to prove.

The same type of trick shows us that x also must be of the form 4m+1 (when you substitute in p=4b+1 and multiply out σ(pˣ), you’ll find you can factor out 4 if x=4m+3).

If all that is a bit much to keep track of, don’t worry. The essence of the proof keeps coming down to one fact. The definition of perfect is σ(N)=2N. The definition of N being odd is that we cannot factor out any extra copy of 2 from N.

This just forces different parts σ(N), when written out, to also not contain too many copies of 2.

Thus, if N is an odd perfect number, it must have the form:

where p is a prime number of the form p=4n+1 and does not divide Q.

Other Results

There have been a lot of results since this form was discovered. In 1980, Hagis showed that there must be at least 8 distinct prime factors, and then in 2005, Hare showed it must have at least 75 (not necessarily distinct) factors. In 2012, Ochem and Rao showed it must have at least 101.

Results on the size of factors also have been proved, but computing makes this somewhat less interesting than actual “structure theorems” of an odd perfect number. There are dozens of these types of results about the exponents that can occur and congruence relations involving all of N.

If you want to solve a longstanding problem and gain some fame, this is a good one to tinker with. All you’d have to do is find some guaranteed form for an odd perfect number that contradicts this form and you’ll have proved once and for all that none exist (which is the current consensus guess).

Until then, computers will keep checking.