Maths Bite: Perfect Numbers

A perfect number is a positive integer that is equal to the sum of its proper divisors (positive divisors excluding the number itself). Equivalently, it is half the sum of all of its positive divisors.

An example of a perfect number is 6.

Source: Wikipedia

The definition of a perfect number dates back to Euclid’s Elements:

“If as many numbers as we please beginning from a unit be set out continuously in double proportion, until the sum of all becomes a prime, and if the sum multiplied into the last make some number, the product will be perfect.”

Euclid gave a rigorous proof of the connection between these numbers and Mersenne Primes, i.e. primes of the form 2n − 1. This is called the formation rules and started that {\displaystyle q(q+1)/2} is a perfect number whenever q is a prime of the form 2^{p}-1. Euler later proved that all even perfect numbers are of that form, which is now known as the Euclid-Euler theorem.

Proof of the Euclid-Euler Theorem: adapted from Wikipedia

The proof is short, and depends of the fact that the function of the sum of divisors is multiplicative, i.e. σ(ab) = σ(a)σ(b). For this to be valid, the divisors of a number must include the number itself, not just the proper divisors. As discussed above, a number is perfect if and only if its sum of divisors is twice its value.

Looking at the theorem in one direction: 

When 2p − 1 is prime,

σ(2p − 1(2p − 1)) = σ(2p − 1)σ(2p − 1) = (2p − 1)2p = 2(2p−1(2p − 1))

In the other direction:

Suppose that an even perfect number is given. Let us partially factor it as 2kx where x is odd. For 2kx to be perfect, its sum of divisors must be twice its value, thus 2k + 1x = σ(2kx) = (2k + 1 − 1)σ(x).

The odd factor 2k + 1 − 1 on the right hand side is at least three (as k is a positive integer), and it must divide or equal x.  So, y = x/(2k + 1 − 1) is a proper divisor of x. Dividing both sides of by the common factor 2k + 1− 1, and taking into account the known divisors x and of x, gives

2k + 1y = σ(x)
            = x + y + other divisors
            = 2k + 1y + other divisors.

For this equality to be true, there can be no other divisors. Therefore, y must be 1, and x must be a prime of the form 2k + 1 − 1.

Today 46 perfect numbers are known, 288(289– 1) being the last to be discovered by hand calculations in 1911 (all the other have been found using computers).

M x

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s