In last week's post, we discussed Mersenne primes. These were primes of the form:
\[
2^p-1, \phantom{x} \textrm{where} \phantom{x} p \phantom{x} \textrm{is prime.}
\]
I mentioned that such primes are relevant to the problem of finding perfect numbers. So how about we flesh that out?
Let's define a function that takes in positive integers and records the sum of their divisors. We shall denote this function with the Greek letter sigma, so that
\[
\sigma(n)=\sum_{d|n} d = \phantom{x} \textrm{the sum of the divisors of} \phantom{x} n.
\]
Here are some sample values:
\[
\sigma(3)=1+3=4
\]
\[
\sigma(4)=1+2+4=7
\]
\[
\sigma(6)=1+2+3+6=12
\]
\[
\sigma(10)=1+2+5+10=18
\]
\[
\sigma(40)=1+2+4+5+8+10+20+40=90
\]
The number six might catch your eye, since it is the only one on our list with the property that
\[
\sigma(n)=2n
\]
Numbers with this property are said to be perfect numbers, and they have a pedigree going back at least to Euclid. Why are they so interesting? Well, keep in mind that every number is a divisor of itself. If we decline to consider that when evaluating our sums, then we can say that a perfect number is one whose “proper” divisors (which is to say all of the divisors except for the number itself) add up to the original number. The first three examples of this are 6, 28 and 496, since we have:
\[
1+2+3=6
\]
\[
1+2+4+7+14=28
\]
\[
1+2+4+8+16+31+62+124+248=496
\]
Granted, that might be a somewhat idiosyncratic definition of perfection, but it certainly is awfully cool.
Now, notice something interesting about our three perfect numbers. We have:
\[
6=2 \times 3 =2^1(2^2-1)
\]
\[
28=4 \times 7 = 2^2(2^3-1)
\]
\[
496=16 \times 31 = 2^4(2^5-1)
\]
In each case the number in parentheses is a Mersenne prime! The other factor is a power of two. It was known already to Euclid that any number of the form:
\[
N=2^{p-1}(2^p-1),
\]
with the second factor prime, is a perfect number. The most concise way of proving this requires an interesting fact about our sum of divisors function. I claim that if the numbers m and n are relatively prime then we have
\[
\sigma(mn)=\sigma(m) \sigma(n).
\]
A formal proof of this fact would be more tedious than it's worth, but the main idea can be seen by considering the special case of a product of two prime numbers. In that case we have
\[
\sigma(p) \sigma(q)=(1+p)(1+q)=1+p+q+pq=\sigma(pq).
\]
It would seem that we obtain every divisor of the product by taking one divisor from each of the factors, multiplying them together, and then repeating that procedure in all possible ways. As an example of this formula in action, consider that
\[
\sigma(40)=\sigma(8)\sigma(5)=(1+2+4+8)(1+5)=(15)(6)=90,
\]
which matches the value we computed earlier.
Can we apply this to N? Indeed we can! Any power of two is relatively prime to any odd number. Now, keep in mind that the only divisors of a prime are one and itself, and the only divisors of a power of two are all the other powers of two with smaller positive exponent. This leads us to
\[
\sigma(N)=\sigma(2^{p-1})\sigma(2^p-1)
\]
\[
=(1+2+2^2+\dots+2^{p-1})(1+(2^p-1))=(2^p-1)(2^p),
\]
where we used the standard formula for the sum of a geometric series to evaluate the first term. Now we bring it home by noticing that we have:
\[
\sigma(N)=(2^p)(2^p-1)=2(2^{p-1}[2^p-1])=2N,
\]
precisely as desired. As I said, Euclid already noticed this. But it fell to Euler to prove that every even perfect number has that form (of a power of two times a Mersenne prime). That proof is a bit long, but it's very pretty and completely elementary. We shall consider it next week. Stay tuned!
- Log in to post comments
Nice!
Very interesting. Euler is always Euler
Very good! Does anyone else confuse Euclid and Euler, at least until they stop and think "okay, it's EUCLID-ian geometry, not EULER-ian"? Maybe it's just me.
I'm interested to see how the even-ness criteria comes about, since Wikipedia doesn't delve into that. (Thus, I don't see why you'd worry about the existence of odd perfect numbers.) Actually, looking back at this post, odd numbers are hosed from the get-go via the 2^x term. Yup ... even more confused about how there's even a possibility for odd perfect numbers. :)
cheglabratjoe --
Well, as we'll see next week the assumption that you're dealing with an even perfect number allows you to do certain tricks that you just can't do with an odd number. So the proof just doesn't address the question of odd perfect numbers. There are several theorems that show that an odd perfect number, if it exists, would have to be very large and have lots of primes in their factorizations. But until someone can prove they are logically impossible they will remain a possibility.
Love the Monday Math series.
Thanks again for replying, Jason!
If you don't mind my continued asking, is it strange that theorems exist that demonstrate an odd perfect number would have to be really big? I understand that you could manually (sequentially) check increasingly big numbers, and thus ensure that numbers smaller than some N you've checked up to aren't perfect. But, I guess I'm not grasping how you could do a proof akin to the ones you've been doing and "prove" a size-dependent phenomenon. These proofs "feel" pretty all-or-nothing to me, but again I'm sure the lack of understanding is entirely on my end.
cheglabratjoe:
The function f(n) = sigma(n)/n -- note: n is perfect iff f(n)=2 -- is "multiplicative", meaning that (as Jason said) f(mn)=f(m)f(n) when m,n have no common factors, so that f(n) = product of f(p^r) when n = product of p^r. And f(p^r) = 1 + 1/p + ... + 1/p^r, which is somewhere between 1+1/p and 1+1/(p-1).
If p=2 then that sum can be made nice and close to 2, which means you can try to make an even perfect number by having a factor of 2^large -- which has f(2^large) just slightly less than 2 -- and arranging the odd prime factor(s) of n to fix up the shortfall. It turns out (without too much difficulty, as it happens) that you can do this provided 2^(large+1)-1 is prime, and not otherwise.
But if your number is odd, you don't have that nice simple mechanism for getting f(n) close to 2, which means you're dependent on finding prime powers for which the product of f(n) just happens to land very near to 2. For that, you need to get lucky; and since f(p^r) rapidly approaches 1+1/(p-1) as r increases, you can (kinda) treat "all large enough powers of p" in the same way. In this way, it's not so very difficult to rule out possibilities built entirely out of small prime numbers, to prove that the smallest prime factors can't be too large, etc.
Important note: I haven't actually looked at the proofs of any of those theorems about odd perfect numbers, but the above is a handwavy explanation for why it shouldn't be surprising that there are such theorems.