Perfect numbers

By the aliquot parts or divisors of a number are meant the divisors, including unity, which are less than the number. A number, like $6=1+2+3$, which equals the sum of its aliquot divisors is called perfect (vollkommen, vollständig). If the sum of the aliquot divisors is less than the number, as is the case with 8, the number is called deficient (diminute, defective, unvollkommen, unvollständig, mangelhaft). If the sum of the aliquot divisors exceeds the number, as is the case with 12, the number is called abundant (superfluos, plus quam-perfectus, redundantem, excédant, übervollständig, überflussig, überschiessende).

Euclid¹ proved that, if $p=1+2+2^2+\cdots+2^n$ is a prime, $2^np$ is a perfect number. He showed that $2^np$ is divisible by $1,2,\ldots,2^n,p,2p,\ldots,2^{n-1}p$, but by no further number less than itself. By the usual theorem on geometrical progressions, he showed that the sum of these divisors is $2^np$.

Fermat,⁵⁹ in a letter to Mersenne, June (?), 1640, stated three propositions which he had proved not without considerable trouble and which he called the basis of the discovery of perfect numbers: if $n$ is composite, $2^n-1$ is composite; if $n$ is a prime, $2^n-2$ is divisible by $2n$, and $2^n-1$ is divisible by no prime other than those of the form $2kn+1$ [cf. Euler⁸⁷]. For example, $2^{11}-1=23\cdot89$, $2^{37}-1$ has the factor 223. Also $2^{23}-1$ has the factor 47, Oeuvres, 2, p. 210, letter to Frénicle, October 18, 1640.

L. Euler,⁹⁷ in a posthumous paper, proved that every even perfect number is of Euclid's type. Let $a=2^nb$ be perfect, where $b$ is odd. Let $B$ denote the sum of the divisors of $b$. The sum $(2^{n+1}-1)B$ of the divisors of $a$ must equal $2a$. Thus $b/B=(2^{n+1}-1)/2^{n+1}$, a fraction in its lowest terms. Hence $b=(2^{n+1}-1)c$. If $c=1$, $b=2^{n+1}-1$ must be a prime since the sum of its divisors is $B=2^{n+1}$, whence Euclid's formula. If $c>1$, the sum $B$ of the divisors of $b$ is not less than $b+2^{n+1}-1+c+1$; hence

$$\frac{B}{b}\geqq\frac{2^{n+1}(c+1)}{b}>\frac{2^{n+1}}{2^{n+1}-1},$$

contrary to the earlier equation. The proof given in another posthumous paper by Euler⁹⁸ is not complete.

L. Euler⁹⁸ proved that any odd perfect number must be of the form $r^{4\lambda+1}P^2$, where $r$ is a prime of the form $4n+1$ [Frénicle⁶⁴]. Express it as a product $ABC\ldots$ of powers of distinct primes. Denote by $a,b,c,\ldots$ the sums of the divisors of $A,B,C,\ldots$, respectively. Then $abc\ldots=2ABC\ldots$. Thus one of the numbers $a,b,\ldots$, say $a$, is the double of an odd number, and the remaining ones are odd. Thus $B,C,\ldots$ are even powers of primes, while $A=r^{4\lambda+1}$. In particular, no odd perfect number has the form $4n+3$. Amplifications of this proof have been given by Lionnet,¹²⁸ Stern,¹³⁷ Sylvester,¹⁴⁹ Lucas.¹⁵⁷ See also Liouville¹³⁰ in Chapter X.

Proper divisors

For a positive integer $n$, a proper divisor is a positive divisor smaller than $n$. Thus 1 is included when $n>1$. Write $s(n)$ for their sum. A number is perfect if $s(n)=n$, deficient if $s(n)<n$, and abundant if $s(n)>n$. The source's examples are $6=1+2+3$, $8$ and $12$, respectively.

Dickson records the synonyms vollkommen, vollständig for perfect; diminute, defective, unvollkommen, unvollständig, mangelhaft for deficient; and superfluos, plus quam-perfectus, redundantem, excédant, übervollständig, überflussig, überschiessende for abundant.

Euclid’s construction

Euclid¹ proves that if

$$q=1+2+2^2+\cdots+2^a$$

is prime, then $N=2^a q$ is perfect. Its proper divisors are precisely

$$1,2,\ldots,2^a,\quad q,2q,\ldots,2^{a-1}q.$$

The geometric-sum formula gives the sum of these divisors as $2^a q=N$.

Fermat’s reported prime tests

In his letter to Mersenne of June (?) 1640, Fermat⁵⁹ reports three propositions which he had proved with considerable difficulty, calling them the basis for discovering perfect numbers: if $n$ is composite, $2^n-1$ is composite; if $n$ is prime, $2n\mid 2^n-2$, and every prime divisor of $2^n-1$ has the form $2kn+1$ [compare Euler⁸⁷]. His examples are

$$2^{11}-1=23\cdot89,\qquad223\mid 2^{37}-1.$$

The letter to Frénicle of October 18, 1640 also gives $47\mid2^{23}-1$ (Oeuvres, 2, p. 210).

Euler’s converse

Euler's posthumous paper⁹⁷ proves that every even perfect number has Euclid's form. Write $N=2^a m$, with $m$ odd, and set $S=\sigma(m)$, where $\sigma(m)$ denotes the sum of all positive divisors of $m$. Since $N$ is perfect,

$$(2^{a+1}-1)S=2N,\qquad \frac mS=\frac{2^{a+1}-1}{2^{a+1}}.$$

The fraction on the right is reduced, so $m=(2^{a+1}-1)c$. If $c=1$, then $S=2^{a+1}=m+1$, forcing $m$ to be prime and giving Euclid's formula. For $c>1$, the source uses

$$S\ge m+(2^{a+1}-1)+c+1$$

and hence

$$\frac Sm\ge\frac{2^{a+1}(c+1)}m>\frac{2^{a+1}}{2^{a+1}-1},$$

contradicting the preceding equality. Dickson states that the proof in another posthumous paper⁹⁸ is incomplete.

Euler’s necessary form in the odd case

Euler⁹⁸ proves that an odd perfect number must have the form $q^{4k+1}u^2$, with $q$ a prime congruent to 1 modulo 4 [Frénicle⁶⁴]. Write the number as a product of powers of distinct primes, $N=A_1\cdots A_t$, and put $S_i=\sigma(A_i)$. Then

$$S_1\cdots S_t=2A_1\cdots A_t.$$

Exactly one of the $S_i$, say $S_1$, is twice an odd number; the others are odd. Thus $A_2,\ldots,A_t$ are even powers of primes, while $A_1=q^{4k+1}$. In particular $N$ cannot be congruent to 3 modulo 4. Dickson cites amplifications by Lionnet,¹²⁸ Stern,¹³⁷ Sylvester,¹⁴⁹ and Lucas,¹⁵⁷ and refers to Liouville¹³⁰ in Chapter X.

Divisors and their sums

For a positive integer $n$, define

$$\sigma(n)=\sum_{d\mid n}d,\qquad s(n)=\sum_{\substack{d\mid n\\d<n}}d=\sigma(n)-n.$$

The sums run over positive divisors. In particular $\sigma(1)=1$ and $s(1)=0$. A number is perfect, deficient, or abundant according as $s(n)$ equals, is smaller than, or exceeds $n$. Equivalently compare $\sigma(n)$ with $2n$.

The examples $6,8,12$ give

$$\sigma(6)=12,\qquad\sigma(8)=15,\qquad\sigma(12)=28.$$

Lemma (divisor product). If $\gcd(u,v)=1$, then $\sigma(uv)=\sigma(u)\sigma(v)$. Also

$$\sigma(p^a)=1+p+\cdots+p^a=\frac{p^{a+1}-1}{p-1}$$

for a prime $p$ and an integer $a\ge0$.

Proof. Unique prime factorization writes each divisor of $uv$ uniquely as $de$, with $d\mid u$ and $e\mid v$. Summing $de$ over these choices factors the sum. The divisors of $p^a$ are exactly $1,p,\ldots,p^a$, whose sum is geometric. Thus if $n=\prod p_i^{a_i}$,

$$\sigma(n)=\prod_i(1+p_i+\cdots+p_i^{a_i}).$$

Coprimality is essential: $\sigma(4)=7$, whereas $\sigma(2)^2=9$. Also $s$ is not multiplicative: $s(6)=6$, whereas $s(2)s(3)=1$.

Euclid’s construction

Proposition. If $M=2^p-1$ is prime, where $p\ge2$, then $N=2^{p-1}M$ is perfect.

Proof. The factors $2^{p-1}$ and $M$ are coprime, so

$$\sigma(N)=(1+2+\cdots+2^{p-1})(1+M)=(2^p-1)2^p=2N.$$

The first cases $p=2,3,5,7$ give $6,28,496,8128$. Euclid's divisor list is precisely what the product formula packages: one chooses a power of 2 and either 1 or $M$. The historical calculation remains a useful way to reconstruct that product.

Necessary tests and actual certificates

If $p=ab$ with $a,b>1$, the factorization

$$2^p-1=(2^a-1)(1+2^a+\cdots+2^{a(b-1)})$$

shows that $2^p-1$ is composite. Hence $p$ must be prime. The converse fails: $2^{11}-1=2047=23\cdot89$. The number $2^{10}\cdot2047$ is consequently not a perfect number merely because it has Euclid's algebraic shape.

For an odd prime $p$, every prime divisor $q$ of $2^p-1$ satisfies $q\equiv1\pmod{2p}$. Congruence modulo $q$ means equality of remainders on division by $q$.

Proof. Let $d$ be the least positive exponent with $2^d\equiv1\pmod q$. Dividing $p$ by $d$ shows that $d\mid p$. Since $d\ne1$, $d=p$. Multiplication by 2 permutes the nonzero residues modulo the odd prime $q$. Comparing their products and cancelling gives $2^{q-1}\equiv1\pmod q$. The same division argument gives $p\mid q-1$. Since $q-1$ is even and $p$ is odd, $2p\mid q-1$.

This proves a restriction on possible divisors, not primality. A failed search below a cutoff proves primality only if the cutoff reaches the square root: every composite integer has a prime divisor at most its square root. Dickson's long sequence of tests and corrections should be read with that distinction in mind. His p. 12 report does not explicitly exclude $p=2$; the assertions involving $2p$ need that exclusion.

The last digits of perfect numbers do not alternate: the examples for $p=13$ and $p=17$ are $33550336$ and $8589869056$, both ending in 6. Dickson reports Cataldi's correction on p. 10. Checking the prime factors in the formula explains why earlier lists built from every odd exponent were unreliable.

The converse: exhausting the available divisors

Theorem. Every even perfect number is $2^{p-1}(2^p-1)$ with $2^p-1$ prime.

Proof (Dickson, p. 30). Write $N=2^a m$ with $a\ge1$ and $m$ odd. Multiplicativity and perfection give

$$(2^{a+1}-1)\sigma(m)=2^{a+1}m.$$

Subtract $(2^{a+1}-1)m$ and put $d=\sigma(m)-m$. Then

$$d=\frac{m}{2^{a+1}-1}.$$

Thus $d$ is a positive integer divisor of $m$ and $d<m$. The sum of all divisors of $m$ is exactly $m+d$, so there can be no further positive divisor. Since 1 is a divisor, $d=1$; therefore $m$ is prime and equals $2^{a+1}-1$. Put $p=a+1$.

The decisive step is positivity: two known distinct divisors already exhaust the sum. This proof avoids the four-divisor lower bound in the p. 19 account. It is Dickson's argument, not an argument discovered by this reconstruction. Together with Euclid it is a classification of even perfect numbers; it does not settle existence or nonexistence in the odd case.

The odd case: one exceptional prime power

Proposition. An odd perfect number, if there is one, has the form

$$N=q^{4k+1}u^2,\qquad q\equiv1\pmod4,\qquad\gcd(q,u)=1.$$

Here $q$ is prime, $k\ge0$, and $u$ is odd.

Proof. In the factorization $N=\prod p_i^{a_i}$, all $p_i$ are odd. Hence $\sigma(p_i^{a_i})$ is odd exactly when $a_i$ is even. Since $\sigma(N)=2N$ contains exactly one factor of 2, precisely one exponent is odd. Call its prime $q$ and its exponent $e$; all other prime powers form a square.

If $q\equiv3\pmod4$, the terms in $1+q+\cdots+q^e$ can be paired, each pair congruent to 0 modulo 4. This contradicts the requirement of exactly one factor of 2. Hence $q\equiv1\pmod4$, and the same sum is congruent to $e+1$ modulo 4. It must be congruent to 2, so $e\equiv1\pmod4$.

This is a necessary shape, not a construction: for instance 5 has the shape and is not perfect. The parity argument in the source gives the skeleton; the calculation modulo 4 supplies the omitted justification for the two congruence restrictions.