NTIC Perfect Numbers

Subsection 19.4.1 A perfect definition and theorem

Definition 19.4.1.

When the ratio $\frac{σ (n)}{n}$ is exactly $2,$ we say $n$ is a perfect number.

This is a big definition, and it goes back at least to Euclid, who defines the notion at the beginning of the number-theoretic books of the Elements. It is easy to see this is the same thing as

n

being the sum of all of its proper divisors¹, which is Euclid's characterization. Indeed, the Greek is τέλειος ἀριθμός, which might better be translated as “complete number”, as is done in many languages. In modern English usage, ‘completeness’ captures the concept of being comprised of everything (and hence also being without flaw) better than ‘perfection’, but in English these numbers are universally called perfect.

Historically these were called aliquot parts in this context.

🔗

Euclid only mentions this concept again over one hundred propositions later, where he proves that certain numbers are, in fact, perfect. (A careful reader will notice that the primes in question are, in fact, the Mersenne primes of Definition 12.1.6!) Such a conclusion is a fitting end, as William Dunham says in his book, Journey through Genius [E.5.5].

🔗

Theorem 19.4.2.

If $n$ is a number such that $2^{n} - 1$ is prime, then the (even) number $2^{n - 1} (2^{n} - 1)$ is perfect.

🔗

Proof.

Euclid's proof (in the link) of this is worth looking at.

🔗

Many centuries later, Euler proved the converse; we will prove them together. (See also Chapter 1 of Dunham's Euler: The Master of Us All [E.5.6].)

🔗

Theorem 19.4.3. Characterization of Even Perfect Numbers.

If $N$ is an even number, it is perfect if and only if it is the product of a power $2^{n - 1}$ and a prime of the form $2^{n} - 1$ (for the same $n$ ).

🔗

Proof.

First, assume that $2^n-1$ is prime. Then the factors of $N = 2^{n-1}\left(2^n-1\right)$ are coprime, so

\begin{equation*} \sigma\left(2^{n-1}\left(2^n-1\right)\right)=\sigma\left(2^{n-1}\right)\sigma\left(2^n-1\right)=\left(2^n-1\right)\left(2^n-1+1\right) \end{equation*}

The steps are because of multiplicativity and the formulas we had earlier (see Theorem 19.2.5) for $\sigma$ of powers of two and primes. But then

\begin{equation*} \left(2^n-1\right)\left(2^n-1+1\right)=2^n\left(2^n-1\right)=2\left[2^{n-1}\left(2^n-1\right)\right] \end{equation*}

so that the sum of divisors is exactly twice the original number.

Now for the converse, which is somewhat longer. Let us start with an even perfect number $N\text{,}$ which is perforce divisible by some power of two.

Looking ahead, call this power the $(n-1)$th power! Then our even perfect number may be written as $N = 2^{n-1}q\text{,}$ where $q$ is the (odd) quotient.

Let's divide the rest of the proof into several pieces. First, two facts.

We know that this number is perfect, so

\begin{equation*} \sigma\left(2^{n-1}q\right)=2\cdot 2^{n-1}q=2^nq \end{equation*}
We also know how to compute $\sigma\text{,}$ so

\begin{equation*} \sigma\left(2^{n-1}q\right)=\sigma\left(2^{n-1}\right)\sigma(q)=\left(2^n-1\right)\sigma(q) \end{equation*}

We can combine these observations to see that

\begin{equation*} 2^nq=\left(2^n-1\right)\sigma(q) \end{equation*}

Note that this means $2^n-1\mid q\text{,}$ since $q$ is the only odd part of the left-hand side (implicitly using some of Theorem 6.3.2). Let's write

\begin{equation*} \left(2^n-1\right)m=q\text{.} \end{equation*}

Substituting, we have

\begin{equation*} 2^n\left(2^n-1\right)m=\left(2^n-1\right)\sigma(q)\Rightarrow 2^nm=\sigma(q) \end{equation*}

Since $m$ and $q$ both divide $q\text{,}$ by the definition of $\sigma$ we have

\begin{equation*} \sigma(q)\geq q+m=\left(2^n-1\right)m+m=2^nm \end{equation*}

Since these two divisors ($q$ and $m$) alone add up to $\sigma(q)\text{,}$ it must be true that $q$ has exactly these two divisors, so it is prime. That means $m=1\text{,}$ and $q=2^n-1\text{,}$ and so the perfect number $N$ equals $2^{n-1}\left(2^n-1\right)\text{.}$ Great!

🔗

We will leave the question about whether there are odd perfect numbers to Section 19.5.

🔗

Subsection 19.4.2 Speculation and more terminology

🔗

There are many things people have claimed about numbers of this type. A Hellenistic Roman in the first century in Gerasa² named Nichomachus claimed that the

n

th perfect number had

n

decimal digits. Nicomachus was more concerned with mystical claims about perfect numbers (which many repeated, see [E.4.5, Chapter 3]), but this mathematical assertion continued to be made for over a thousand years by most commentators. However, knowing what we do about Mersenne primes (recall Definition 12.1.6), we see that the fifth possible

n

is

13,

so that the next perfect number,

(2^{13} - 1) \cdot 2^{12},

🔗

was very large and so lay mysterious for a long time. It was apparently discovered in the fifteenth century.

Interestingly, this is the same place as one setting of the Biblical story of the demons called “Legion” who went into swine.

xxxxxxxxxx
 
(2^13-1)*2^12

🔗

Until the early modern period, such numbers were basically inaccessible.

🔗

Number theorists (often of the amateur variety, but certainly not always) have come up with all kinds of other names for various concepts related to

σ (n) / n .

🔗

Definition 19.4.4.

Recall that if $σ (n) = 2 n,$ then $n$ is perfect.

If $σ (n) = k n$ for some integer $k,$ then we say that $n$ is $k$ -perfect.
Or, if $σ (n) > 2 n,$ then $n$ is abundant.
If $σ (n) < 2 n,$ we say $n$ is deficient.

🔗

As it will turn out, these things are not really good characterizations of what it means to have “too many” or “too few” divisors. However, in recognition of the Greeks' contributions we keep this allusive and fairly standard terminology. (Nichomachus is responsible for the two latter names, and they seem to have stuck, since medieval commentators such as Boethius waxed rhapsodic over them – see [E.4.5, Section 2.1].) As examples, Exercise 19.6.7 asks for a 3-perfect number, if one exists, and Exercise 19.6.17 asks for a 4-perfect number.

🔗

Definition 19.4.5.

Here are some less well-known, but nonetheless interesting, terms.

A number is pseudoperfect if it is the sum of some of its divisors (other than itself).
A number $n$ is superabundant if the ratio $σ (n) / n$ for $n$ is bigger than the value of the ratio for all smaller $m < n .$
A number is weird if it is abundant but not pseudoperfect. (There is a famous paper of Erdős on this topic.)

🔗

There are many questions one can ask about these and other definitions; see Exercise Group 19.6.15–21. One cheeky such question is this.

🔗

Question 19.4.6.

Is a perfect number pseudoperfect?

🔗

Subsection 19.4.3 The abundancy index

🔗

It's time to give a name to the mysterious ratio at the core of this section.

🔗

Definition 19.4.7.

The ratio $\frac{σ (n)}{n}$ may be called the abundancy index of $n .$

🔗

A beautiful thing is that once you name a concept, you can ask questions about it. Here's another largely open question which seems like it should be easy…

🔗

Question 19.4.8.

Rather than asking which integers can be gotten, which rational numbers can be gotten as $\frac{σ (n)}{n} ?$

xxxxxxxxxx
 
@interact
def _(n=(20,[1..200])):
    cols = ceil(n/10)
    T = [cols*['$n$',r'$\sigma(n)/n$']]
    list = [[i,(sigma(i)/i)] for i in range(1,n+1)]
    list.extend((10-(len(list)%10))*['',''])
    for k in range(10):
        t = [item for j in range(cols) for item in list[k+10*j]]
        T.append(t)
    pretty_print(html(table(T,header_row = True, frame = True)))

🔗

There are some interesting theorems about this already known. For one thing, the abundancy index is the same thing as

σ_{- 1} (n) .

🔗

Fact 19.4.9.

σ_{- 1} (n) = \frac{σ (n)}{n}

🔗

Proof.

We have that

\begin{equation*} \sigma(n)/n=\left(\sum_{d\mid n}d\right)/n \end{equation*}

Now note that for every $d\mid n\text{,}$ the quotient is also an integer divisor $d'$ of $n\text{.}$ So

\begin{equation*} \sigma(n)/n=\sum_{d\mid n}\frac{1}{d'} \end{equation*}

This is the same list as the original divisor list, so reordering gives

\begin{equation*} \sigma(n)/n=\sum_{d\mid n}\frac{1}{d}=\sigma_{-1}(n) \end{equation*}

🔗

Fact 19.4.10.

Clearly all such numbers are in the interval $[1, \infty) .$ Here are some more known facts about the abundancy index.

If $m ∣ n,$ then $σ_{- 1} (n) \geq σ_{- 1} (m) .$
If $σ_{- 1} (n) = \frac{a}{b}$ in lowest terms, then $b ∣ n .$
If $r$ is “caught” between $σ (n)$ and $n$ (such that $n < r < σ (n)$ ) and is relatively prime to $n,$ then $r / n$ is not an abundancy index.

🔗

Proof.

We skip the proof, but proving the first two facts is left as Exercise 19.6.22.

🔗

Holdener and Stanton picturesquely call rational numbers which are not abundancies abundancy outlaws. The end of this hyper-linked paper [E.7.11] has a nice list of which numbers thus far have been found, and which have not.

🔗

Subsection 19.4.4 Amicable Numbers

🔗

Another interesting idea of summing divisors is still of ancient provenance, though not quite as old as Euclid.

🔗

Definition 19.4.11.

A pair of positive integers $m, n$ such that $σ (n) = σ (m) = m + n$ is called a pair of amicable numbers.

🔗

Clearly any perfect number is amicable (or ‘friendly’) with itself. As with perfect numbers, we can characterize them as pairs of numbers whose proper divisors add to each other.

🔗

The smallest pair of unequal amicable numbers is

(220, 284) .

This was known by the time of late Greek antiquity, where Iamblichus' commentary on Nichomachus seems to be the first reference; the connection was already a somewhat mystical one in terms of friendship, based on the mutual summation to each other. Similarly to perfect numbers, some Islamic writers likewise cherished these in a mystical sense (see for instance [E.5.3, Section 5-3]).

🔗

Eventually early modern European commentators mentioned them, or at least this pair, in related contexts. See if you can find it in the following image³ from an appendix of sorts to the Harmonie Universelle, Mersenne's monumental compendium of practical and theoretical music.

Courtesy of the French National Library and its online repository, Gallica. The license does not allow for commercial use of these images. This image is actually a pastiche of parts of observation 13, in order not to give away the answers to some exercises!

🔗
Figure 19.4.12. Excerpts from *Nouvelle Observationes* regarding amicable numbers

🔗

Strictly mathematical advances on this topic came from work in the Islamic world inspired by the Greek sources. Thabit ibn Qurra worked on many questions related to

σ

(see Exercise 19.6.29); just as Theorem 19.4.2 is a formula of sorts, dependent upon the existence of certain types of primes, his Algorithm 19.4.14 may also be judged thusly.

🔗

Historical remark 19.4.13. Thabit ibn Qurra.

The ninth-century Arab doctor and mathematician Thabit ibn Qurra was probably responsible for a number of Arabic translations of Greek mathematics in his time in the “House of Wisdom” of the Caliphs of Baghdad. Interestingly, he did not include a single example of either perfect numbers or amicable numbers, despite clearly being in control of effective information about them. He made important contributions to the question of the parallel postulate in geometry.

🔗

Algorithm 19.4.14. Get Amicable Numbers.

Here is one way to get amicable numbers.

Make a list of numbers of the form $p_{n} = 3 \cdot 2^{n} - 1$ and $q_{n} = 9 \cdot 2^{2 n - 1} - 1 .$
Then check if $p_{n - 1},$ $p_{n},$ and $q_{n}$ are all prime.
If so, then $2^{n} p_{n - 1} p_{n}$ and $2^{n} q_{n}$ are an amicable pair.

🔗

Proof.

Since only primes and powers of two are involved, it's easy to calculate $\sigma$ in this case, so proving it is left as an exercise (see Exercise 19.6.21).

🔗

Several centuries later, al-Farisi and ibn al-Banna seem to have independently used Thabit's formula to exhibit the second known amicable pair,

18416

and

17296 .

Even more impressively, at the beginning of the seventeenth century the otherwise obscure Persian mathematician Muhammad Baqir Yazdi used this same formula to obtain the pair

9363584

and

9437056,

where

n = 7 .

See [E.5.11, Section 2.6] for many more details of this era. You can try the formula yourself in the following Sage cell.

xxxxxxxxxx
 
@interact
def _(n=[2..20]):
    pretty_print(html("We have $p_{%s}=%s$ and $p_{%s}=%s$"%(n-1,3*2^(n-1)-1,n,3*2^(n)-1)))
    pretty_print(html("And $q_{%s}=%s$ as well."%(n,9*2^(2*n-1)-1)))
    if is_prime(3*2^n-1) and is_prime(3*2^(n-1)-1) and is_prime(9*2^(2*n-1)-1):
        pretty_print(html("Then the pair $%s$ and $%s$ is amicable!"%(2^n*(3*2^(n-1)-1)*(3*2^(n)-1), 2^n*(9*2^(2*n-1)-1))))
    else:
        pretty_print(html("Doesn't give an amicable pair"))

🔗

At about the same time as Yazdi, Fermat and Descartes both worked on this question (which is where Mersenne learned of it), and independently rediscovered both the formula and these pairs (see [E.5.8, II.IV]). Later, Euler expanded the Thabit/Fermat formula significantly and found several dozen new pairs. But it turns out that the next smallest pair, one everyone had missed by attempting to find a formula, was found by a sixteen-year old Italian boy in 1860!

xxxxxxxxxx
 
sigma(1184),sigma(1210),1184+1210

🔗

Apparently he came up with this by trial and error, though no one knows for sure. The internet can provide some of the most current data on these pairs, though sadly the best website is now out of service. The hope is that there are infinitely many such pairs, but there is currently no proof of this conjecture. At any rate, it can't be too infinite; Nguyen and Pomerance have shown that, however many there are, the sum of their reciprocals is no greater than 215.

Number Theory: In Context and Interactive

Section 19.4 Perfect Numbers

Subsection 19.4.1 A perfect definition and theorem

Definition 19.4.1.

Theorem 19.4.2.

Proof.

Theorem 19.4.3. Characterization of Even Perfect Numbers.

Proof.

Subsection 19.4.2 Speculation and more terminology

Definition 19.4.4.

Definition 19.4.5.

Question 19.4.6.

Subsection 19.4.3 The abundancy index

Definition 19.4.7.

Question 19.4.8.

Fact 19.4.9.

Proof.

Fact 19.4.10.

Proof.

Subsection 19.4.4 Amicable Numbers

Definition 19.4.11.

Historical remark 19.4.13. Thabit ibn Qurra.

Algorithm 19.4.14. Get Amicable Numbers.

Proof.