Fact-checked by Grok 2 weeks ago

Euclid–Euler theorem

The Euclid–Euler theorem is a fundamental result in that fully characterizes all even s, stating that a positive even integer n is perfect—meaning it equals the sum of its proper divisors—if and only if n = 2^{p-1}(2^p - 1) for some p such that $2^p - 1 is a . This theorem combines two key contributions: Euclid's ancient observation in his Elements (circa 300 BCE) that if $2^p - 1 is prime, then $2^{p-1}(2^p - 1) is perfect, and Leonhard Euler's 18th-century proof of the converse, establishing that every even perfect number must take this form. The theorem has profound implications for the study of perfect numbers, as all known perfect numbers are even and thus correspond directly to known Mersenne primes, of which there are verified examples (as of October 2024), yielding perfect numbers up to over 82 million digits. No odd perfect numbers are known, and their existence remains an , but the Euclid–Euler theorem excludes any odd perfect numbers from the even case and provides a complete classification for even ones. Euler's proof relies on the multiplicative property of the sum-of-divisors function \sigma(n), showing that for an even perfect n = 2^{a-1} m with m odd, \sigma(n) = 2n forces m = 2^a - 1 to be prime and a prime. This result not only links perfect numbers to the search for Mersenne primes but also underscores the rarity of perfect numbers, with only finitely many known despite extensive computational efforts.

Statement

Formal statement

The Euclid–Euler theorem states that a positive even integer n is a if and only if it can be expressed as n = 2^{p-1}(2^p - 1), where p is a and $2^p - 1 is a . This biconditional establishes both directions: if $2^p - 1 is a for prime p, then n is (Euclid's sufficiency), and every even must take this form (Euler's necessity).

Illustrative examples

The smallest even perfect number is 6, corresponding to p = 2: $2^{2-1}(2^2 - 1) = 2 \cdot 3 = 6. The proper divisors of 6 are 1, 2, and 3, summing to 6. Next, for p = 3, n = 2^{3-1}(2^3 - 1) = 4 \cdot 7 = 28. The proper divisors are 1, 2, 4, 7, and 14, summing to 28. For p = 5, n = 2^{5-1}(2^5 - 1) = 16 \cdot 31 = 496. The proper divisors sum to 496, confirming perfection. For p = 7, n = 2^{7-1}(2^7 - 1) = 64 \cdot 127 = 8128, with proper divisors summing to 8128. These examples illustrate how known Mersenne primes generate all known even perfect numbers.

Historical context

Euclid's contributions

The study of perfect numbers dates back to ancient times, possibly to the Pythagoreans in the 5th century BCE, who associated the number 6—the smallest perfect number—with concepts of harmony and completeness. Euclid formalized the first key result on even perfect numbers in his Elements, composed around 300 BCE. In Book IX, Proposition 36, Euclid proved that if $2^p - 1 is prime for a prime p, then n = 2^{p-1}(2^p - 1) is a perfect number, equal to the sum of its proper divisors. Euclid's proof relies on the geometric series sum for the divisors of the power of 2 and the primality ensuring the odd part has only 1 and itself as divisors. This construction generated the first four known perfect numbers: 6 (p=2), 28 (p=3), 496 (p=5), and 8128 (p=7). Euclid did not address odd perfect numbers or prove the converse, leaving open whether all even perfect numbers arise this way or if odd ones exist. His work integrated perfect numbers into the broader arithmetic framework of the Elements, linking them to primes and geometric progressions.

Euler's developments

Leonhard Euler advanced the understanding of perfect numbers in the through extensive computations and theoretical proofs. In , he discovered the next perfect number after 8128, corresponding to p=13, which is $2^{12}(2^{13} - 1) = 2305843009213693952. Euler also verified and extended earlier claims, such as disproving a mistaken perfect number proposed by Pietro Antonio Cataldi in 1588. The pivotal contribution came in 1747, when Euler proved the converse of : every even must be of the form $2^{p-1}(2^p - 1) where $2^p - 1 is a . This result, detailed in unpublished manuscripts during his lifetime, was later published posthumously and established the complete characterization of even s, now known as the Euclid–Euler theorem. Euler's proof used the multiplicative property of the sum-of-divisors function \sigma(n), assuming an even n = 2^{a-1} m with m odd and showing that a must be prime and m = 2^a - 1 prime. Euler's work was influenced by correspondence with and others, and it shifted focus toward computational searches for Mersenne primes to find new perfect numbers. While he sought odd perfect numbers, Euler conjectured none exist below certain bounds, fueling ongoing research. His developments bridged ancient with modern , emphasizing the rarity and structure of perfect numbers.

Mathematical prerequisites

The sum-of-divisors function

The sum-of-divisors function, denoted \sigma(n), for a positive integer n is the sum of all positive divisors of n, including 1 and n itself. For example, \sigma(6) = 1 + 2 + 3 + 6 = 12. This function is fundamental in the study of perfect numbers, as a number n is perfect if \sigma(n) = 2n. If n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} is the prime factorization of n, then \sigma(n) = \prod_{i=1}^k (1 + p_i + p_i^2 + \cdots + p_i^{e_i}) = \prod_{i=1}^k \frac{p_i^{e_i + 1} - 1}{p_i - 1}. In particular, for a prime power p^e, \sigma(p^e) = \frac{p^{e+1} - 1}{p - 1}, and for p = 2, \sigma(2^{a}) = 2^{a+1} - 1. The function \sigma is multiplicative, meaning that if m and n are coprime (gcd(m, n) = 1), then \sigma(m n) = \sigma(m) \sigma(n). This property allows the computation of \sigma for composite numbers by factoring them into coprime parts.

Even numbers and perfectness

Any even positive integer greater than 2 can be uniquely written as n = 2^{a-1} m, where a \geq 2 and m is odd. Using the multiplicativity of \sigma, \sigma(n) = \sigma(2^{a-1}) \sigma(m) = (2^a - 1) \sigma(m). For n to be perfect, \sigma(n) = 2n = 2^a m, so (2^a - 1) \sigma(m) = 2^a m. This equation constrains the possible forms of m and a, leading to the conditions in the Euclid–Euler theorem. Specifically, solving for \sigma(m) = \frac{2^a m}{2^a - 1} requires that $2^a - 1 divides $2 m, and given m odd, this implies specific primality conditions.

Proof

Sufficiency

The sufficiency direction, originally due to , states that if p is prime and $2^p - 1 is also prime (a ), then n = 2^{p-1}(2^p - 1) is a , i.e., \sigma(n) = 2n, where \sigma denotes the sum-of-divisors . Since \sigma is multiplicative and $2^{p-1} and $2^p - 1 are coprime, \sigma(n) = \sigma(2^{p-1}) \cdot \sigma(2^p - 1). The sum of divisors of $2^{p-1} is the $1 + 2 + \cdots + 2^{p-1} = 2^p - 1. For the Mersenne prime q = 2^p - 1, \sigma(q) = 1 + q = 2^p. Thus, \sigma(n) = (2^p - 1) \cdot 2^p = 2^p (2^p - 1) = 2 \cdot 2^{p-1}(2^p - 1) = 2n, confirming that n is perfect.

Necessity

The necessity direction, proved by Euler, asserts that every even has the form $2^{p-1}(2^p - 1) for prime p with $2^p - 1 prime. Assume n is an even , so n = 2^{a} m with m odd and a \geq 1, and \sigma(n) = 2n. By multiplicativity, \sigma(n) = \sigma(2^{a}) \cdot \sigma(m) = (2^{a+1} - 1) \sigma(m) = 2^{a+1} m. Rearranging gives \sigma(m) = \frac{2^{a+1} m}{2^{a+1} - 1}. Since $2^{a+1} - 1 and $2^{a+1} are coprime, $2^{a+1} - 1 must divide m. Let m = (2^{a+1} - 1) k for some odd integer k \geq 1. Substituting yields \sigma(m) = \frac{2^{a+1} (2^{a+1} - 1) k}{2^{a+1} - 1} = 2^{a+1} k. Now, \sigma(m) = \sigma((2^{a+1} - 1) k). If k > 1, since m is odd and greater than 1, \sigma(m) \geq \sigma(2^{a+1} - 1) \sigma(k) \geq (1 + (2^{a+1} - 1)) (1 + k) = 2^{a+1} (1 + k) > 2^{a+1} k unless k = 1 (as \sigma is strictly greater than the identity for composite numbers or primes greater than 1). Thus, k = 1, so m = 2^{a+1} - 1 must be prime, and a + 1 = p must be prime (for ). Hence, n = 2^{p-1}(2^p - 1).

Applications and extensions

Number-theoretic uses

The Euclid–Euler theorem establishes a correspondence between even perfect numbers and Mersenne primes, reducing the search for even perfect numbers to the discovery of primes of the form $2^p - 1. This has driven extensive computational efforts, notably the (GIMPS), a project that has identified all known Mersenne primes since 1996. As of October 2024, 52 Mersenne primes are known, yielding 52 even perfect numbers, the largest having over 41 million digits. The theorem also informs the study of the \sigma(n), highlighting the multiplicative structure required for perfection. It underscores the rarity of perfect numbers and provides a framework for analyzing their properties, such as being triangular numbers or having exactly one representation in the without consecutive 1s. Additionally, it motivates bounds and constraints on potential odd perfect numbers, though none are known.

Generalizations

The Euclid–Euler theorem has been extended to other classes of numbers beyond perfect ones. For instance, it generalizes to certain \alpha-perfect numbers, where \sigma(n) = \alpha n for rational \alpha > 1, using similar techniques involving the prime factorization and the multiplicativity of \sigma. One such extension shows that for specific \alpha, even \alpha-perfect numbers take forms analogous to Euclid's, with the odd part being a prime of a generalized Mersenne form. Further generalizations include S-perfect numbers, a broader class incorporating subsets of divisors, and results on multiperfect numbers (k-perfect, where \sigma(n) = k n for integer k > 2), where even multiperfect numbers often exhibit similar Euclidean forms, though complete characterizations remain open. These build on Euler's proof strategy, applying it to more general abundance conditions. The theorem's methods also influence research in harmonic and ideal numbers, as well as algorithmic for generating and verifying abundant/deficient numbers.

References

  1. [1]
    [PDF] Section 8. Perfect Numbers
    Apr 3, 2022 · the “Euclid-Euler Theorem.” Theorem 8.2 (Euler). If n is an even perfect number, then n = 2p−1(2p − 1) for some prime p, and 2p − 1 is ...
  2. [2]
    [PDF] Even Perfect Numbers and Sums of Odd Cubes - UMD CS
    The following is the Euclid-Euler theorem since Euclid proved one direction, and Euler the other. Theorem 2.3 n is an even perfect number iff there exists p ...
  3. [3]
    [PDF] A Study of the Sum of Divisors - Scholars' Mine
    known as the Euclid-Euler theorem in which he built upon Euclid's work by proving conversely that all perfect numbers must follow the formula Euclid discovered.
  4. [4]
    [PDF] A relationship between Mersenne primes and perfect numbers
    Apr 9, 2025 · This nice problem is, at its core, the well-known Euclid-Euler theorem, which in addition tells us that any even number with the property of ...
  5. [5]
    Sum of Squares Function -- from Wolfram MathWorld
    A positive integer can be represented as the sum of two squares iff each of its prime factors of the form 4k+3 occurs as an even power.
  6. [6]
    [PDF] Euler's proof of the Sums of Two Squares the- orem
    Theorem: (Fermat's two squares theorem) Every odd prime p is a sum of two squares if and only if p ≡ 1 (mod 4). For the avoidance of ambiguity, ...Missing: Euclid- | Show results with:Euclid-<|control11|><|separator|>
  7. [7]
    [PDF] Many More Names of (7, 3, 1) - Virginia Tech
    Euclid gives a proof of the Pythagorean theorem in Book I, Proposition 47 ... which gives the product of two sums of two squares as a sum of two squares.
  8. [8]
    [PDF] Numbers, Groups and Cryptography Gordan Savin
    Euclid was a Greek mathematician who lived in Alexandria around 300. B.C. He ... This formula says that a product of two sums of two squares is again a sum.
  9. [9]
    De numeris, qui sunt aggregata duorum quadratorum
    Sep 25, 2018 · De numeris, qui sunt aggregata duorum quadratorum. English Title. On ... Published Date. 1758. Written Date. 1749. Original Source Citation.
  10. [10]
    sums of two squares - PlanetMath.org
    Nov 19, 2013 · Theorem. The set of the sums of two squares of integers is closed under multiplication ... Brahmagupta's identity. Synonym, Fibonacci's identity.Missing: representation properties
  11. [11]
    Brahmagupta-Fibonacci Identity
    But in 1748 Euler reported a four-square identity: (a_1^2+a_2^2+a_3^2+a_4^2)(b_1^2+b_2^2+b_3^2+b_4^2)\\ \space\space\space =(a_1 b_1 - a_2 b_2 - a_3 b_3 ...Missing: Euclid | Show results with:Euclid
  12. [12]
    Landau-Ramanujan Constant -- from Wolfram MathWorld
    Let S(x) denote the number of positive integers not exceeding x which can be expressed as a sum of two squares (i.e., those n<=x such that the sum of ...
  13. [13]
    [PDF] SUMS OF TWO SQUARES IN SHORT INTERVALS Antal Balog
    ... sums of two squares has precise order y/. √ log x. Thus there exist positive constants A1 and A2 so that, in the sense of natural density, for almost all y one ...
  14. [14]
    None
    Summary of each segment:
  15. [15]
    [PDF] expressing a number as a sum of two squares - Purdue Math
    As the Gaussian integers form a UFD, it follows that every non-zero non-unit Gaussian integer factors uniquely as a unit times a product of prime, first- ...
  16. [16]
    G. Lejeune Dirichlet's werke - Internet Archive
    Mar 30, 2008 · G. Lejeune Dirichlet's werke, published in 1889, is a 2-volume work in German and French, digitized by Google, with part of the text in French.
  17. [17]
    [PDF] Proof of a theorem of Fermat that every prime number of the form 4n ...
    thus, if a and b are numbers prime between themselves, and d is a divisor of a number of the form aa+bb, then d will also be a sum of two squares; I have given.
  18. [18]
    Disquisitiones arithmeticae : Gauss, Carl Friedrich, 1777-1855
    Aug 11, 2018 · Disquisitiones arithmeticae ; Publication date: 1801 ; Topics: Number theory ; Publisher: Lipsiae : In commiss. apud Gerh. Fleischer, jun.
  19. [19]
    [PDF] Sums of two squares and lattices - Keith Conrad
    Fermat's two-square theorem states an odd prime p is a sum of two squares if and only if p ≡ 1 mod 4.
  20. [20]
    [PDF] Section 18. Sums of Two Squares—Proofs of Theorems
    Mar 23, 2022 · Lemma 18.A. If the prime-power decomposition of n contains a prime congruent to 3 (mod 4) which is raised to an odd power, then n cannot be.
  21. [21]
    [PDF] the gaussian integers - keith conrad
    ... even powers of primes ≡ 3 mod 4 is a sum of two squares. Now we treat the converse direction: any n > 1 which is a sum of two squares has even multiplicity ...
  22. [22]
    [PDF] On Cornacchia's algorithm for solving the diophantine equation u - LIX
    Sep 12, 1990 · We give a new proof of the validity of Cornacchia's algorithm for finding the primitive solutions (u, v) of the diophantine equation u2 + dv2 = ...
  23. [23]
    [PDF] Quarternions and the four square theorem - UChicago Math
    The Four Square Theorem was proved by Lagrange in 1770: ev- ery positive integer is the sum of at most four squares of positive integers, i.e. n = A2 + B2 + C2 ...
  24. [24]
    [PDF] A simple proof of Jacobi's two-square theorem
    A simple proof of Jacobi's two-square theorem. 1. In a recent note, John A. Ewell [1] derives Fermat's two-square theorem: A prime p = 4n + 1 is the sum of ...
  25. [25]
    [1905.10704] Continued Fractions and Factoring - arXiv
    May 26, 2019 · The paper shows that the continued fraction expansion of sqrt(N) with odd period leads to sum of two squares, and even period to a factor of ...
  26. [26]
    [PDF] Thue's lemma in Z[i] and Lagrange's four-square theorem
    Lagrange's 1770 theorem that every positive integer is a sum of four squares seems destined to stand the test of time as one of the most beautiful results in.
  27. [27]
    [PDF] Primes of the form x2+ny2
    Every prime number which surpasses by one or three a multiple of eight is composed of a square and the double of another square. Examples are 3, 11, 17, 19, 41, ...
  28. [28]
    [PDF] The Hasse-Minkowski Theorem - Digital Commons @ UConn
    Mar 8, 2006 · Here are two results along these lines. Theorem 1.5. If an integer is a sum of two rational squares then it is a sum of two integer squares.
  29. [29]
    [PDF] Quadratic forms and Genus Theory - HAL
    Dec 7, 2022 · When R = K[X], we show that the Genus Theory map is the quadratic form version of the 2-descent map on a certain hyperelliptic curve.