Definition. A number is perfect if . Equivalently, n is perfect if it is equal to the sum of its divisors other than itself.
Example. Show that 6 and 28 are perfect.
6 is perfect, because
28 is perfect, because
It is not known whether there are any odd perfect numbers, or whether there are infinitely many even perfect numbers. The existence of infinitely many even perfect numbers is related to the existence of infinitely many Mersenne primes by the following result. One implication is in Euclid's Elements, and the other implication is due to Euler.
Theorem. n is an even perfect number if and only if , where is a Mersenne prime.
Proof. Here are some preliminaries before I start the proof. If n is an even integer, write , where and . Then
I'll use this notation in both parts of the proof.
Suppose that n is perfect, so .
Note that s is the sum of the divisors of m other than m. Note also that , since .
Suppose . Note that , since . Then 1 and s are distinct divisors of m other than m, so , which is a contradiction.
Thus, . This implies , so m is prime.
Moreover, I get .
It follows that , where is prime.
On the other hand, suppose , where is a Mersenne prime. Then
Therefore, n is an even perfect number.
Example. What perfect number corresponds to the Mersenne prime ?
I now know that finding even perfect numbers is equivalent to finding Mersenne primes --- primes of the form . I showed earlier that is prime implies that n is prime. So to look for Mersenne primes, I only need to look at for n prime. Next, I'll derive a result which simplifies checking that is prime. First, here's an amusing lemma.
Proof. Assume without loss of generality that . The greatest common divisor of two numbers doesn't change if I subtract the smaller from the larger, so
Since is odd, it has no factors in common with the in the first term. So
Now I see that the " " in each slot is just along for the ride: All the action is taking place in the exponents. And what is happening is that the subtraction algorithm for computing greatest common divisors is operating in the exponents! --- the original pair a, b, was replaced by , b.
It follows that the exponents will "converge" to , because this is what the subtraction algorithm does. And when the algorithm terminates, I'll have , proving the result.
Example. Compute .
This is surely not obvious, especially when you consider that and !
Theorem. Let p be an odd prime. Every factor of has the form for some .
Proof. It suffices to prove that the result holds for prime factors of . For
so products of numbers of the form also have that form.
Suppose then that q is a prime factor of . Fermat's theorem says . The preceding lemma implies that
Now and implies . In particular, , since it's divisible by the prime q. This in turn implies that . Now p is prime, so this is only possible if . In particular, .
Write , so . q is odd, so is even, and is even. Since p is odd, t must be even: for some k. Then , which is what I wanted to show.
Example. Use the criterion to determine whether is prime.
. If has a proper prime factor, it must have one less than 362, and the prime factor must have the form . So I need to check the primes less than 362 to see if they divide 131071.
Therefore, is prime.
Bruce Ikenaga's Home Page
Copyright 2017 by Bruce Ikenaga