The Euclid–Euler theorem is a theorem in mathematics that relates perfect numbers to Mersenne primes. It states that every even perfect number has the form 2n − 1(2n − 1), where 2n − 1 is a prime number. The prime numbers of the form 2n − 1 are known as Mersenne primes, and require n itself to be prime.
It has been conjectured that there are infinitely many Mersenne primes. Although the truth of this conjecture remains unknown, it is equivalent, by the Euclid–Euler theorem, to the conjecture that there are infinitely many even perfect numbers. However it is also unknown whether there exists even a single odd perfect number.
A perfect number is a natural number that equals the sum of its proper divisors, the numbers that are less than it and divide it evenly. For instance, the proper divisors of 6 are 1, 2, and 3, which sum to 6, so 6 is perfect. A Mersenne prime is a prime number of the form Mp = 2p − 1; for a number of this form to be prime, p itself must also be prime. The Euclid–Euler theorem states that an even natural number is perfect if and only if it has the form 2p−1Mp where Mp is a Mersenne prime.
Euclid proved that 2p − 1(2p − 1) is an even perfect number whenever 2p − 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 2p − 1 and the last term T in the series is the power of two 2p − 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.
It was not until the 18th century that Leonhard Euler proved that the formula 2p − 1(2p − 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.
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: Every Mersenne prime gives rise to an even perfect number. When 2p − 1 is prime, σ(2p − 1(2p − 1)) = σ(2p − 1)σ(2p − 1). The sum of divisors for 2p − 1 is 2p − 1, e.g. for p=5 we get 16 (25 − 1) and the sum of its divisors is 31 (1 + 2 + 4 + 8 + 16 = 31 = 2p − 1). 2p − 1 being a prime implies that the sum of its divisors is 2p since its constituents are the number itself and 1 so σ(2p − 1) = (2p − 1) + 1 = 2p.
Taking this into account leads to:
In the other direction, suppose that an even perfect number has been given, and partially factor it as 2kx, where x is odd. For 2kx to be perfect, its sum of divisors must be twice its value:
2k + 1x = σ(2kx) = (2k + 1 − 1)σ(x).
The odd factor 2k + 1 − 1 on the right side of (∗) is at least 3, and it must divide or equal x, the only odd factor on the left side, so y = x/(2k + 1 − 1) is a proper divisor of x. Dividing both sides of (∗) by the common factor 2k + 1 − 1 and taking into account the known divisors x and y of x gives
- 2k + 1y = σ(x) = x + y + other divisors = 2k + 1y + other divisors.
- Stillwell, John (2010), Mathematics and Its History, Undergraduate Texts in Mathematics, Springer, p. 40, ISBN 9781441960528.
- Euclid (1956), The Thirteen Books of The Elements, Translated with introduction and commentary by Sir Thomas L. Heath, Vol. 2 (Books III–IX) (2nd ed.), Dover, pp. 421–426.
- O'Connor, John J.; Robertson, Edmund F., "Abu Ali al-Hasan ibn al-Haytham", MacTutor History of Mathematics archive, University of St Andrews.
- Euler, Leonhard (1849), "De numeris amicibilibus" [On amicable numbers], Commentationes arithmeticae (in Latin), 2, pp. 627–636. Originally read to the Berlin Academy on February 23, 1747, and published posthumously. See in particular section 8, p. 88.
- Gerstein, Larry (2012), Introduction to Mathematical Structures and Proofs, Undergraduate Texts in Mathematics, Springer, Theorem 6.94, p. 339, ISBN 9781461442653.
- Caldwell, Chris K., "A proof that all even perfect numbers are a power of two times a Mersenne prime", Prime Pages, retrieved 2014-12-02.
- Travaglini, Giancarlo (2014), Number Theory, Fourier Analysis and Geometric Discrepancy, London Mathematical Society Student Texts, 81, Cambridge University Press, pp. 26–27, ISBN 9781107044036.