Monday, February 1, 2010

Unsolved: Perfect Numbers and Mersenne Primes

In an earlier post I talked about perfect numbers, and how it was still unknown whether there are any odd perfect numbers. There's another unsolved problem surrounding the perfect numbers, and this one intersects with a special set of numbers that you may have heard of, the Mersenne primes.

Mersenne numbers and Mersenne primes

Mersenne numbers take their name from the French monk and mathematician Father Marin Mersenne, even though they were studied as long ago as the times of Euclid. You construct Mersenne numbers by subtracting 1 from a power of 2.

Mn = 2n - 1

The following table details the construction of the first sixteen Mersenne numbers.

n 2n 2n - 1

If you look closely at the highlighted fields you may notice what mathematicians have known for centuries. A Mersenne number (2n - 1) cannot be prime unless the exponent n is prime. This is often expressed with a slightly different notation.

Mp = 2p - 1

What wasn't known in the time of the ancient Greeks was whether or not the exponent being prime meant that Mp would always be prime. It wasn't until the 16th century, when it was discovered that 211 - 1 = 2047 is not prime, that this question was finally settled (2047 = 23 * 89). In order for Mp to be prime, it is necessary but not sufficient for the exponent p to also be prime.

Constructing Perfect Numbers

Perfect numbers have also been studied since the times of the early Greek mathematicians. It was Euclid who first discovered that the first four perfect numbers are given by the formula

P = 2p-1 * (2p - 1)

6 = 21 * (22 - 1)
28 = 22 * (23 - 1)
496 = 24 * (25 - 1)
8128 = 26 * (27 - 1)

It wasn't until 1849 that it was shown by Euler (in a paper published after his death) that all even perfect numbers are of the form 2p-1 * (2p - 1), where (2p - 1) is a Mersenne prime.

Since every even perfect number corresponds to a Mersenne prime (and vice versa), searching for perfect numbers is the same as searching for Mersenne primes. This leads us to two unsolved problems.

It isn't known if there are infinitely many even perfect numbers.

It isn't known if there are infinitely many Mersenne primes.

(In fact, given the 1-to-1 correspondence between even perfect numbers and Mersenne primes, it really wouldn't be incorrect to say that either one of these problems is just a restatement of the other.)

The largest prime number yet discovered as of this writing is the Mersenne prime 243,112,609 - 1, which has a starggering 12,978,189 digits. The corresponding perfect number, 243,112,608 * (243,112,609 - 1), has 25,956,377 digits.

Additional reading

In this article I've barely scratched the surface of prime number research. There is a very large network of people and computers dedicated to the search for Mersenne primes. For more information (and to possibly join in the search) have a look at the Great Internet Mersenne Prime Search (GIMPS).

No comments: