Euclid–Euler theorem

The Euclid–Euler theorem is a theorem in mathematics that relates perfect numbers to Mersenne primes. It states that every even perfect number can be represented by the form 2^n − 1(2ⁿ − 1), where 2ⁿ − 1 is a prime number. The prime numbers of this form are known as Mersenne primes, and thus require n itself to be prime.

Statement

An even positive integer is a perfect number, that is, equals the sum of its proper divisors, if and only if it has the form 2^p−1M_p where M_p is a Mersenne prime (i.e. a prime number of the form M_p = 2^p − 1).

History

Euclid proved that 2^{p − 1}(2^p − 1) is an even perfect number whenever 2^p − 1 is prime (Euclid, Prop. IX.36). This is the final result on number theory in Euclid's Elements; the later books in the Elements instead concern irrational numbers, solid geometry, and the golden ratio. Euclid expresses the result by stating that if a finite geometric series beginning at 1 with ratio 2 has a prime sum P, then this sum multiplied by the last term T in the series is perfect. Expressed in these terms, the sum P of the finite series is the Mersenne prime 2^p − 1 and the last term T in the series is the power of two 2^{p − 1}. Euclid proves that PT is perfect by observing that the geometric series with ratio 2 starting at P, with the same number of terms, is proportional to the original series; therefore, since the original series sums to P = 2T − 1, the second series sums to P(2T − 1) = 2PT − P, and both series together add to 2PT, two times the supposed perfect number. However, these two series are disjoint from each other and (by the primality of P) exhaust all the divisors of PT, so PT has divisors that sum to 2PT, showing that it is perfect.

Over a millennium after Euclid, Alhazen c. 1000 CE conjectured that every even perfect number is of the form 2^{p − 1}(2^p − 1) where 2^p − 1 is prime, but he was not able to prove this result.

It was not until the 18th century that Leonhard Euler proved that the formula 2^{p − 1}(2^p − 1) will yield all the even perfect numbers. Thus, there is a one-to-one relationship between even perfect numbers and Mersenne primes; each Mersenne prime generates one even perfect number, and vice versa.

Proof

Euler's proof is short, and depends on the fact that the sum of divisors function σ is multiplicative; that is, if a and b are any two relatively prime integers, then σ(ab) = σ(a)σ(b). For this formula to be valid, the sum of divisors of a number must include the number itself, not just the proper divisors. A number is perfect if and only if its sum of divisors is twice its value.

One direction of the theorem (the part already proved by Euclid) immediately follows from the multiplicative property: when 2^p − 1 is prime, σ(2^{p − 1}(2^p − 1)) = σ(2^{p − 1})σ(2^p − 1) = (2^p − 1)2^p = 2(2^p−1(2^p − 1)).

In the other direction, suppose that an even perfect number has been given, and partially factor it as 2^kx where x is odd. For 2^kx to be perfect, its sum of divisors must be twice its value:

2k + 1x = σ(2kx) = (2k + 1 − 1)σ(x).

(∗)

The odd factor 2^{k + 1} − 1 on the right hand side of (∗) is at least three, and it must divide or equal x, the only odd factor on the left hand side, so y = x/(2^{k + 1} − 1) is a proper divisor of x. Dividing both sides of (∗) by the common factor 2^{k + 1} − 1, and taking into account the known divisors x and y of x, gives

2^{k + 1}y = σ(x) = x + y + other divisors = 2^{k + 1}y + other divisors.

For this equality to be true, there can be no other divisors. Therefore, y must be 1, and x must be a prime of the form 2^{k + 1} − 1.