Perfect numbers and Mersenne primes

It is remarkable that even at this ``elementary'' level there are many problems which are still unsolved. In this section, we mention one of the oldest unsolved problems in mathematics.

Let $n>0$ be an integer and let

$$\sigma(n) = \sum_{d\vert n}d.$$

For example, $\sigma(12)=1+2+3+4+6+12=28$.

Definition 1.6.13   A perfect number is an integer $n>1$ such that $\sigma(n)=2n$, in other words, $n$ is the sum of its proper divisors.

No odd perfect numbers are known. The following conjuecture may be the oldest unsolved problem in mathematics!

Conjecture 1.6.14   Odd perfect numbers don't exist.

It is known if an odd perfect number exists then it must be at least $10^{300}$.

Lemma 1.6.15   An integer $n$ is an even perfect number if and only if $n=2^{p-1}(2^p-1)$, where $2^p-1$ is a prime.

Though this result is often quoted as being due to Euler, it may have been known to Euclid.

proof: We leave the ``if'' direction as an exercise.

``Only if'': Since $n$ is an even number, we can write $n=2^s\,t$, where $t$ is odd and $s \geq 1$. We know that $\sigma (t) >t$, so let $\sigma (t)=t+r$, with $r>0$. Since $2\,n=\sigma (n)$, we have:

$$2^{s+1}\,t=(2^{s+1}-1)\,(t+r)=2^{s+1}\,t-t+(2^{s+1}-1)r$$

which gives us:

$$t=(2^{s+1}-1)\,r.$$

Therefore, $r$ is a divisor of $t$ and $r <t$. But $\sigma (t)=t+r$ implies that $r$ is the sum of all of the divisors of $t$ which are less than $t$ (i.e. $r$ is the sum of a group of numbers which include $r$). This is possible only if the group consists of one number, and that number must be one. Therefore, $\sigma(t)=t+1=2^{s+1}-1$, which implies that both $t=2^{s+1}-1$ and $s+1$ are prime. Letting $p=s+1$ gives the conclusion. $\Box$

A prime number of the form $2^p-1$ is called a Mersenne prime. As we've seen already, it is unknown whether or not there are infinitely many Mersenne primes.

For further details on perfect numbers, see for example Ball and Coxeter [BC], page 66, or Hardy and Wright [HW], §16.8.

Exercise 1.6.16   Find all solutions to $\phi(n)=4$.

Exercise 1.6.17   Show that there are no solutions to $\phi(n)=14$.

Exercise 1.6.18   Show that if $f(n)$ is multiplicative then so is $f(n)/n$.

Exercise 1.6.19   Show that if $f(n)$, $g(n)$ are multiplicative then so is $f(n)g(n)$.

Exercise 1.6.20   Find all $n$ such that $\phi (2n)=\phi(n)$.

Exercise 1.6.21   Show that $d(n)$ is odd if and only if $n$ is a square.

Exercise 1.6.22   Find all $n$ such that $\phi(n)$ is odd.

Exercise 1.6.23   Show that no perfect number is a square.

Exercise 1.6.24   Show that if $gcd(m,n)=2$ then $\phi(mn)=2\phi(m)\phi(n)$.