Page 9

Mersenne Primes and Fermat numbers

Mersenne primes

Mersenne prime numbers are in the form 2^p - 1 where p is prime. The biggest one found so far is

2^25964951 - 1 . A very big number indeed. It has 7816230 digits. If we space these digits one millimeter apart, we will have a line full of numbers 7.81 km long. It can be proven that any number in the form of 2^p -1 where p not prime, must be composite. If p prime then the number may or may not be prime. There is currently a big search for Mersenne prime numbers. Only 42 has been found so far. If you found one you will be famous. A very nice method of testing if a number is Mersenne prime has been divised. It is called the Lukas Lehmer test.

Let S(1) = 4 , S(n+1) = [S(n^2) - 2] mod (2^p - 1) . If S(p-1) = 0 then 2^p -1 is prime.

Lets demonstrate with p=5 . So M = 2^5 -1 = 31  and p-1 = 4.

So we have  S(1) = 4

S(2) = 4^2  -2 = 14 mod 31 = 14         S(3) = 14^2 - 2 = 194 mod 31 = 8   S(4) = 8^2 -2 = 62 mod 31 = 0

So 31 is prime and it is a Mersenne prime. We see we only had to do p-2 calculations.

If we test 2^13 - 1 = 8191 we will have to do p-1= 12 calculations. If we decide using the prime sieve we will have to divide 3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,61 and so on. A lot more work. 

See how Lucas Lehmer  works with this little applet below.

The applet uses the big integers in the java class.