Euclid, perfect numbers and Mersenne primes

If as many numbers as we please beginning from a unit be set out continuously in double proportion, until the sum of all becomes prime, and if the sum multiplied into the last make some number, the product will be perfect.
~~+++++~~– Euclid, Elements, Book IX.36 (about 300BC)

A perfect number is equal to the sum of its proper divisors, (“proper” means here “not including itself”.) e.g. $6=1+2+3$ .

In modern terms, he’s describing the series $1+2+4+\dots+2^{k-1}=\dfrac{2^k-1}{2-1}=2^k-1$ , and multiplying that by its last term $2^{k-1}$ when $2^k-1$ is prime. i.e.

$\text{If } 2{k}-1 \text{ is prime then } 2^{k-1}(2^k-1) \text{ is a perfect number.}$

Proof. Let $p=2^k-1$ be the prime in question. By unique factorization, the proper divisors of $N = 2^{k-1}(2^k-1)=2^{k-1}p$ must contain only $2$ and $p$ . So, they can be listed and summed:

$\begin{align*} \text{Sum of divisors of } N&=1+2+4+\dots+2^{k-1}+p+2p+4p+\dots+2^{k-2}p \\ &=(1+2+4+\dots+2^{k-1})+p(1+2+4+\dots+2^{k-2}) \\ &=(2^k-1)+p(2^{k-1}-1)=p+p2^{k-1}-p\\ &=p2^{k-1}=N. \end{align*}$

Q.E.D.

Primes of the form $2^k-1$ are now known as Mersenne primes, after their 17th C popularizer.

If $k$ is composite, so is $2^k-1$ . If $k=ab$ :

$\begin{align*} 2^k -1&=(2^a)^b-1 \\ &=(2^a-1)\big( (2^a)^{b-1}+(2^a)^{b-2}+(2^a)^{b-3}+\dots+2^a+1\big) \end{align*}$

of which $2^a-1$ is obviously a factor.
e.g. $2^6-1=(2^2)^3-1=(2^2-1)((2^2)^2+2^2+1)=3\times 31=63.$
But if $k$ is prime, $2^k-1$ isn’t always also prime.
e.g. $2^{11}-1=2047=23\times 89$ .

Euler proved that all even perfect numbers are of the form $2^{k-1}(2^k-1)$ . (No odd perfect numbers have yet been found.)

Every even perfect number is represented in binary as $k$ ones followed by $k-1$ zeros:

$\begin{align*} 6 &= 110_2 \\ 28 &= 11100_2 \\ 496 &= 111110000_2 \\ 8128 &= 1111111000000_2 \\ 33550336 &= 1111111111111000000000000_2 \end{align*}$

48 perfect numbers are now known; the most recently found (in 2013) has 34,850,340 digits, and $k$ =57,885,161. (see wiki )

references

William Dunham – Euler: The Master of Us All

adamponting.com

Euclid, perfect numbers and Mersenne primes

Leave a Reply Cancel reply