In last week's post we discussed perfect numbers. These were numbers, like 6, 28 and 496, that are equal to the sums of their proper divisors. We referred to Euler's formula, which claims that every even perfect number has the form
\[
2^{p-1} \left(2^p-1 \right),
\]
where the term in parentheses is prime. As we discussed last week, the term in parentheses is known as a Mersenne prime, which entails that the exponent p is prime as well.
Our goal this week is to prove this formula. This is a very beautiful proof, in my view. It has tremendous flow, by which I mean that there is no one step that requires a really brilliant idea. Rather, as we go along there always seems to be a clear next step. If we keep at it long enough our result just sort of appears.
Our main ingredient will be the sum of divisors function that we defined last week. We have
\[
\sigma(n)=\sum_{d|n} d = \ \textrm{the sum of the divisors of} \phantom{x} n.
\]
As we saw last week, we have that if m and n are relatively prime (meaning that they have no divisors, other than one, in common, then
\[
\sigma(mn)=\sigma(m) \sigma(n).
\]
Finally, since a perfect number is the sum of its proper divisors, and since the sigma function includes the number itself in the summation, we have that
\[
\sigma(N)=2N
\]
for any perfect number N. With that background we can now begin the proof. Here we go!
Let N be an even perfect number. Then it is possible to find a largest power of two that divides N. So we can write:
\[
N=(2^k)(m),
\]
where m is an odd number. Of course, for all we know at this point we could have m=1, which would occur if N is a power of two.
Since any power of two is relatively prime to any odd number we have:
\[
\sigma(N)=\sigma(2^k)\sigma(m).
\]
For now there isn't much we can do about the second factor in the product, but we can do better with the first term. The divisors of a power of two are just all the other powers of two with smaller positive exponent. Keeping in mind the standard formula for the sum of a geometric series, we obtain:
\[
\sigma(2^k)=1+2+2^2+\dots+2^k=2^{k+1}-1.
\]
Combining this with the fact that N is a perfect number now gives us:
\[
\sigma(N)=2N=2(2^k m)=2^{k+1}m=\left( 2^{k+1}-1 \right) \sigma(m).
\]
Time to take stock. Look at the final two terms in our chain of equalities. Notice that we have this:
\[
2^{k+1}m \phantom{x} \textrm{is a multiple of} \phantom{x} 2^{k+1},
\]
and also have this:
\[
2^{k+1}-1 \phantom{x} \textrm{is odd.}
\]
The conclusion is that sigma of m itself must be divisible by as many powers of two as on we find on the left-hand side, meaning that there must be an integer c such that
\[
\sigma(m)=2^{k+1}c.
\]
By substitution we now obtain
\[
2^{k+1}m=\left( 2^{k+1}-1 \right)2^{k+1}c, \phantom{x} \textrm{and therefore}
\]
\[
m=\left( 2^{k+1}-1 \right) c.
\]
We're halfway home! The next observation is that the numbers m and sigma of m are both multiples of this mysterious number c. I claim that, actually, we must have that c=1. To establish this we shall proceed by contradiction. Assume for the moment that c > 1. Then we would have that
\[
m=\left( 2^{k+1}-1 \right) c
\]
has at least three distinct divisors, namely 1, c and m. There could be other divisors as well, but we have enough for our purposes. For we now observe that
\[
\sigma(m) \geq 1+c+m=1+c+\left(2^{k+1}-1 \right)c =1+2^{k+1}c.
\]
This should strike you as very odd. If you go back a few lines you will see that we had another expression for sigma of m. Comparing that equation with this one leads to the conclusion that
\[
2^{k+1}c \geq 1+2^{k+1}c.
\]
which is clearly impossible. We conclude that c=1, precisely as asserted.
Now let's go back and substitute c=1 into our earlier equations. We get
\[
m=2^{k+1}-1 \phantom{x} \textrm{and} \phantom{x} \sigma(m)=2^{k+1}=m+1.
\]
We now ask, which numbers have the property that
\[
\sigma(m)=m+1?
\]
Only the prime numbers! You see, every number is divisible by the number one and by itself. That means that for any integer m, we have that sigma of m is at least m+1. We can only get equality if the only divisors are one and the number itself, which is to say we can get it only if m is prime.
Our discussion about Mersenne primes from last week shows that if a prime number is one less than a power of two, then the exponent must itself be prime. So we must have k+1=p, and k=p-1, for some prime number p. But if we now go back to the first equation in the proof we obtain:
\[
N=2^{p-1} \left(2^p-1 \right),
\]
where the term in parentheses is prime. Just as we claimed! Thus concludes the proof.
Impressed? I sure was. This was the kind of thing that got me interested in studying number theory in the first place. I suppose there is no accounting for taste, but I find that very beautiful. If you find yourself getting caught up in wondering why anyone would care about this, I must politely suggest you have missed the point.
And in the interests of giving credit where credit is due, this proof comes from Joseph Silverman's book A Friendly Introduction to Number Theory.
- Log in to post comments
Don't know what you are using but I am seeing the markup for the formulas - not the formulas, so the output is unreadable mostly. Firefox Ubuntu with JS allowed for page. No go.
Hmmm, I'm not sure what the problem is. It comes up fine for me in Firefox, Explorer and Safari.
same for me. IE, too.
The formula for Mersenne numbers does not produce only primes. According to the proof, I believe that only the Mersenne numbers which are primes would satisfy the requirement of producing perfect numbers. This distinction is not quite clear in the writeup.
Love the Monday Math.
I can see the formulae OK, except the longer ones. Their right end disappears in bit heaven, because my netbook doesn't have a big screen. Please use shorter lines.
Hmmm, I'm not sure what the problem is. It comes up fine for me in Firefox, Explorer and Safari.
A beautiful proof! Thanks for posting it.