View source for Euclid–Euler theorem

{{short description|Characterization of even perfect numbers}}
{{About|the theorem on perfect numbers and Mersenne primes|the theorem on the infinitude of prime numbers|Euclid's theorem}}
{{good article}}
The '''Euclid–Euler theorem''' is a [[theorem]] in [[number theory]] that relates [[perfect number]]s to [[Mersenne prime]]s. It states that an even number is perfect [[if and only if]] it has the form {{math|2<sup>''p''−1</sup>(2<sup>''p''</sup> − 1)}}, where {{math|2<sup>''p''</sup> − 1}} is a [[prime number]]. The theorem is named after mathematicians [[Euclid]] and [[Leonhard Euler]], who respectively proved the "if" and "only if" aspects of the theorem.

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.<ref name="stillwell" />

== Statement and examples ==
A perfect number is a [[natural number]] that equals the sum of its proper [[divisor]]s, the numbers that are less than it and divide it evenly (with [[remainder]] zero). 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 {{math|1=''M''<sub>''p''</sub> = 2<sup>''p''</sup> − 1}}, one less than a [[power of two]]. For a number of this form to be prime, {{mvar|p}} itself must also be prime, but not all primes give rise to Mersenne primes in this way. For instance, {{nowrap|1=2<sup>3</sup> − 1 = 7}} is a Mersenne prime, but {{nowrap|1=2<sup>11</sup> − 1 = 2047 = 23 × 89}} is not.

The Euclid–Euler theorem states that an even natural number is perfect if and only if it has the form {{math|2<sup>''p''−1</sup>''M''<sub>''p''</sub>}}, where {{math|''M''<sub>''p''</sub>}} is a Mersenne prime.<ref name="stillwell">{{citation|title=Mathematics and Its History|series=[[Undergraduate Texts in Mathematics]]|first=John|last=Stillwell|authorlink=John Stillwell|publisher=Springer|year=2010|isbn=978-1-4419-6052-8|page=40|url=https://books.google.com/books?id=V7mxZqjs5yUC&pg=PA40}}.</ref> The perfect number 6 comes from {{math|1=''p'' = 2}} in this way, as {{nowrap|1=2<sup>2−1</sup>{{mvar|M}}<sub>2</sub> = 2 × 3 = 6}}, and the Mersenne prime 7 corresponds in the same way to the perfect number 28.

== History ==
Euclid proved that {{math|2<sup>''p''−1</sup>(2<sup>''p''</sup> − 1)}} is an even perfect number whenever {{math|2<sup>''p''</sup> − 1}} is prime. This is the final result on [[number theory]] in [[Euclid's Elements|Euclid's ''Elements'']]; the later books in the ''Elements'' instead concern [[irrational number]]s, [[solid geometry]], and the [[golden ratio]]. Euclid expresses the result by stating that if a finite [[geometric series]] beginning at&nbsp;1 with ratio&nbsp;2 has a prime sum {{mvar|q}}, then this sum multiplied by the last term {{mvar|t}} in the series is perfect. Expressed in these terms, the sum {{mvar|q}} of the finite series is the Mersenne prime {{math|2<sup>''p''</sup> − 1}} and the last term {{mvar|t}} in the series is the power of two {{math|2<sup>''p''−1</sup>}}. Euclid proves that {{math|''qt''}} is perfect by observing that the geometric series with ratio&nbsp;2 starting at {{mvar|q}}, with the same number of terms, is proportional to the original series; therefore, since the original series sums to {{math|1=''q'' = 2''t'' − 1}}, the second series sums to {{math|1=''q''(2''t'' − 1) = 2''qt'' − ''q''}}, and both series together add to {{math|2''qt''}}, two times the supposed perfect number. However, these two series are disjoint from each other and (by the primality of {{mvar|q}}) exhaust all the divisors of {{math|''qt''}}, so {{math|''qt''}} has divisors that sum to {{math|2''qt''}}, showing that it is perfect.<ref>{{citation|author=[[Euclid]]|title=The Thirteen Books of The Elements, Translated with introduction and commentary by Sir Thomas L. Heath, Vol. 2 (Books III–IX)|edition=2nd|publisher=Dover|year=1956|pages=421–426|isbn=0-486-60089-0}}. See in particular Prop. IX.36.</ref>

Over a millennium after Euclid, [[Alhazen]] {{circa|1000 CE}} conjectured that {{em|every}} even perfect number is of the form {{math|2<sup>''p''−1</sup>(2<sup>''p''</sup> − 1)}} where {{math|2<sup>''p''</sup> − 1}} is prime, but he was not able to prove this result.<ref>{{MacTutor Biography|id=Al-Haytham|title=Abu Ali al-Hasan ibn al-Haytham}}</ref> It was not until the 18th century, over 2000 years after Euclid,<ref>{{citation
 | last1 = Pollack | first1 = Paul
 | last2 = Shevelev | first2 = Vladimir
 | doi = 10.1016/j.jnt.2012.06.008
 | issue = 12
 | journal = Journal of Number Theory
 | mr = 2965207
 | pages = 3037–3046
 | title = On perfect and near-perfect numbers
 | volume = 132
 | year = 2012| arxiv = 1011.6160
 | s2cid = 13607242
 }}</ref> that [[Leonhard Euler]] proved that the formula {{math|2<sup>''p''−1</sup>(2<sup>''p''</sup> − 1)}} will yield all the even perfect numbers.<ref name="stillwell" /><ref>{{citation|first=Leonhard|last=Euler|authorlink=Leonhard Euler|chapter=De numeris amicibilibus|trans-chapter=On amicable numbers|language=Latin|contribution-url=https://scholarlycommons.pacific.edu/euler-works/798/|title=Commentationes arithmeticae|volume=2|year=1849|pages=627–636}}. Originally read to the Berlin Academy on February 23, 1747, and published posthumously. See in particular section 8, p. 88.</ref> 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. After Euler's proof of the Euclid–Euler theorem, other mathematicians have published different proofs, including [[Victor-Amédée Lebesgue]], [[Robert Daniel Carmichael]], [[Leonard Eugene Dickson]], John Knopfmacher, and Wayne L. McDaniel. Dickson's proof, in particular, has been commonly used in textbooks.<ref>{{citation|last=Cohen|first=Graeme L.|date=March 1981|doi=10.2307/3617930|issue=431|journal=[[The Mathematical Gazette]]|jstor=3617930|pages=28–30|title=Even perfect numbers|volume=65|s2cid=125868737 }}</ref>

This theorem was included in a web listing of the "top 100 mathematical theorems", dating from 1999, which later became used by Freek Wiedijk as a [[Benchmark (computing)|benchmark]] set to test the power of different [[proof assistant]]s. By 2024, the proof of the Euclid–Euler theorem had been formalized in 7 of the 12 proof assistants recorded by Wiedijk.<ref>{{citation|first=Freek|last=Wiedijk|url=https://www.cs.ru.nl/~freek/100/|title=Formalizing 100 Theorems|publisher=Radboud University Institute for Computing and Information Sciences|access-date=2024-02-20}}</ref>

== Proof ==
Euler's proof is short<ref name="stillwell" /> and depends on the fact that the [[Divisor function|sum of divisors]] function {{mvar|σ}} is [[multiplicative function|multiplicative]]; that is, if {{mvar|a}} and {{mvar|b}} are any two [[relatively prime]] integers, then {{math|1=''σ''(''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.

=== Sufficiency ===
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 {{math|1=2<sup>''p''</sup> − 1}} is prime,
<math display-block>\sigma(2^{p-1}(2^p - 1)) = \sigma(2^{p-1})\sigma(2^p - 1).</math>
The divisors of {{math|2<sup>''p''−1</sup>}} are {{math|1, 2, 4, 8, ..., 2<sup>''p''−1</sup>}}.  The sum of these divisors is a [[geometric series]] whose sum is {{math|1=2<sup>''p''</sup> − 1}}. Next, since {{math|1=2<sup>''p''</sup> − 1}} is prime, its only divisors are {{math|1}} and itself, so the sum of its divisors is {{math|1=2<sup>''p''</sup>}}.

Combining these,
<math display=block>\begin{align}
   \sigma(2^{p-1}(2^p - 1)) &= \sigma(2^{p-1})\sigma(2^p - 1) \\
   &= (2^p - 1)(2^p) \\
   &= 2(2^{p-1})(2^p - 1).
 \end{align}</math>
Therefore, {{math|2<sup>''p''−1</sup>(2<sup>''p''</sup> − 1)}} is perfect.<ref name="imsp">{{citation|title=Introduction to Mathematical Structures and Proofs|series=Undergraduate Texts in Mathematics|first=Larry|last=Gerstein|publisher=Springer|year=2012|isbn=978-1-4614-4265-3|at=Theorem 6.94, p.&nbsp;339|url=https://books.google.com/books?id=qK9y768b1NQC&pg=PA339}}.</ref><ref name="pp">{{citation|title=A proof that all even perfect numbers are a power of two times a Mersenne prime|website=Prime Pages|url=https://primes.utm.edu/notes/proofs/EvenPerfect.html|access-date=2014-12-02|first=Chris K.|last=Caldwell}}.</ref><ref name="ntfagd">{{citation|title=Number Theory, Fourier Analysis and Geometric Discrepancy|volume=81|series=London Mathematical Society Student Texts|first=Giancarlo|last=Travaglini|publisher=Cambridge University Press|year=2014|isbn=978-1-107-04403-6|pages=26–27|url=https://books.google.com/books?id=mIaYAwAAQBAJ&pg=PA26}}.</ref>

=== Necessity ===
In the other direction, suppose that an even perfect number has been given, and partially factor it as {{math|2<sup>''k''</sup>''x''}}, where {{mvar|x}} is odd. For {{math|2<sup>''k''</sup>''x''}} to be perfect, the sum of its divisors must be twice its value:
{{NumBlk|:|<math>2^{k+1}x = \sigma(2^k x) = (2^{k+1} - 1)\sigma(x).</math>|∗}}
The odd factor {{math|2<sup>''k''+1</sup> − 1}} on the right side of '''(∗)''' is at least 3, and it must divide {{mvar|''x''}}, the only odd factor on the left side, so {{math|1=''x''/(2<sup>''k''+1</sup> − 1)}} is a proper divisor of {{mvar|x}}. Dividing both sides of '''(∗)''' by the common factor {{math|1=2<sup>''k''+1</sup> − 1}} and taking into account the known divisors {{mvar|x}} and {{mvar|''x''/(2<sup>''k''+1</sup> − 1)}} of {{mvar|x}} gives
{{Block indent|left=1.6|<math>2^{k+1}x/(2^{k+1}-1) = \sigma(x) = x + x/(2^{k+1}-1) + {}</math>other divisors<math>{} = 2^{k+1}x/(2^{k+1}-1) + {}</math>other divisors.}}
For this equality to be true, there can be no other divisors. Therefore, {{mvar|''x''/(2<sup>''k''+1</sup> − 1)}} must be {{math|1}}, and {{mvar|x}} must be a prime of the form {{math|1=2<sup>''k''+1</sup> − 1}}.<ref name="imsp" /><ref name="pp" /><ref name="ntfagd" />

== References ==

{{reflist}}

{{DEFAULTSORT:Euclid-Euler theorem}}
[[Category:Theorems in number theory]]
[[Category:Articles containing proofs]]
[[Category:Leonhard Euler]]
[[Category:Mersenne primes]]
[[Category:Perfect numbers]]
[[Category:Euclid]]