What is the greatest prime number of them all?

One of the greatest mathematical challenges and brain twisters of our time is the search for the greatest prime.

Euclid proved that there are an infinite number of prime numbers in his book, The Elements. One might think that people would be satisfied with knowing that the set of prime numbers is not finite and therefore cease their search. However, the hunt lives on today.

The Great Internet Mersenne Prime Search (GIMPS) is an organization seeking out the next larger prime number. To this end, the individuals involved use powerful computers and efficient algorithms to try and calculate it. When a new prime is discovered as a result of the stringent, tough, and interminable process, thorough testing must be done by several sources in order to make sure that it wasn't a fluke find. For instance, there could be a memory leak or some other issue on the computer involved that causes a miscalculation. If something like this happens, it could cause the outputted number to be incorrect. The people who are responsible for contributing to this effort need to be sure that they aren't making non-prime numbers famous.

The equation/proof commonly used in the calculation of Mersenne primes is called the Lucas-Lehmer Test and can be expressed as follows:

For p an odd prime, the Mersenne number 2p-1 is prime if and only if 2p-1 divides S(p-1) where S(n+1) = S(n)2-2, and S(1) = 4

The GIMPS is very similar to another numbers crunching computational process that I actually mentioned in this prior post. Folding@Home hopes to crunch its way to a cure for serious illnesses and diseases.

* The Elements of Euclid
* Mersenne
* Great Internet Mersenne Prime Search