Posted by 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!
May 2, 2011
May 2, 2011
May 2, 2011
May 2, 2011
May 3, 2011
May 4, 2011