Mersenne Primes

Mersenne primes deserve a special section on them, since they are the focus of a huge internet project that I am involved with. Remember that Mersenne primes are of the form: 2n-1, where n is prime. The project is GIMPS, Great Internet Mersenne Prime Search. Here you can sign up for an exponent, n, to test. If your exponent creates a Mersenne prime, you will be famous, among the mathematicians and other prime number enthusiasts anyway. I am testing exponent 5,364,329. This exponent has a 1 in 43,969 chance of being a correct Mersenne exponent. I've got my fingers crossed. Laugh. But anyway, here is some information on Mersenne primes, beyond that which was in the Glossary.

Early mathematicians thought that all numbers of the form 2n-1 were prime, where n was prime. This is an easy mistake to understand when you consider that 2, 3, 5, 7 are, and 11 was basically beyond their calculating abilities until Hudalricus Regius showed that 2-1=2047 wasn't in 1536 (23×89), By 1603 Pietro Cataldi had shown that 2-1 and 2-1 were both prime, but then incorrectly stated that 2n-1 was prime for n=23, 29, 31, 37. In 1640 Fermat showed that Cataldi was wrong about 23 and 37; then Euler in 1738 showed Catladi was also wrong for 29. Euler later stated that Cataldi was correct for n=31.

Then comes the french monk Marin Mersenne (1588-1648). Mersenne stated that all n=2, 3, 5, 7, 13, 17, 19, , , , and were prime, all other n < 257 were composite. Although Mersenne stated nothing that wasn't already known, nothing correct anyway, he still got his name attached to prime numbers of the form 2n-1. Actually the correct list for n? is: n=2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127.

Now we move to perfect numbers for a second. Ancient mathematicians found that some numbers equalled the sum of their divisors. These numbers are called perfect numbers. Six is the first perfect number, 6=1+2+3 and the next is 28=1+2+4+7+14. The next two are 496 and 8128. Here is where they relate to Mersenne primes, look at these numbers in their factored form:

All of these are of the form 2n-1×(2n-1) for n=2, 3, 5, and 7 respectively. Thus the following theorems follow:

Theorem:

k is an even perfect number if and only if it has the form 2n-1×(2n-1) and 2n-1 is prime.

Theorem:

If 2n-1 is prime, then so is n.

Thus the when a new Mersenne prime is found, so is a new perfect number. Also as you may have noticed, each perfect number alternates its last digit with 6 or 8, they however, do not continue to alternate in this fashion, but it is easy to prove that a perfect number must end in either 6 or 8, [proof], before looking at my version, you give it a try. But also look at the first four in binary form:

This is a consequence of the first theorem. Also, we do not know whether or not there is an odd perfect number, but it would have to be big if it existed.

When checking to see if a Mersenne number is prime, we usually first look for any small divisors. The following theorem of Euler and Fermat helps us.

Theorem:

Let p and q be primes. If q divides Mp=2p-1, then q=±1 (mod 8) and q=2kp+1 for some integer k.

Here are some other helpful theorems:

Theorem:

Let p=3 (mod 4) be prime. 2p+1 divides Mp.

Theorem:

If you sum the digits of any even perfect number except 6, then sum the digits of the resulting number, and repeat this process until you get a single digit, that digit will be one.

If you want proofs of these theorems go to http://www.utm.edu/research/primes/mersenne.shtml, look around for a while, and you will find what you desire. I'll acknowledge here and again later that this part of my website, the prime number part is mostly the above website, reworded. And sometimes not even that. I attempted to make a similar website, but lower down some of the math talk. I hope I have been at least somewhat succesfull, but I realize that for a more complete discourse on primes one should go to the above mentioned website.

Here is a table of the as-of-yet known Mersenne primes:

#

Exponent

Digits in Mp

Digits in Pp

Year

1

2

1

1

-----

2

3

1

2

-----

3

5

1

2

-----

4

7

3

4

-----

5

13

4

8

1456

6

17

6

10

1588

7

19

6

12

1588

8

31

10

19

1772

9

61

19

37

1883

10

89

28

54

1911

11

107

33

65

1914

12

127

39

77

1876

13

521

157

314

1952

14

617

183

366

1952

16

2203

664

1327

1952

17

2281

687

1373

1952

18

3217

969

1937

1957

19

4253

1281

2561

1961

20

4423

1332

2663

1961

21

9689

2917

5836

1963

22

9941

2993

5985

1963

25

11213

3376

6751

1963

24

19937

6002

12003

1971

25

21701

6533

13066

1978

26

23209

6987

13973

1979

27

44497

13395

26790

1979

28

86243

25962

51924

1982

29

110503

33265

66530

1988

30

132049

39751

79502

1983

31

216091

65050

130100

1985

32

756839

227832

455663

1992

33

859433

258716

517430

1994

34

1257787

378632

757263

1996

35

1398269

420921

841842

1996 (GIMPS)

36

2976221

895932

1791864

1997 (GIMPS)

37

3021377

909526

1819050

1998 (GIMPS)

38?

5364329?

    

1998 (GIMPS)?

 

Mersenne primes (and perfect numbers) are found using this theorem:

Lucas Lehmer Test:

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

Here is the psuedocode for this test:

Lucas_Lehmer_Test(p):

S :=4;

For d from 3 to p do s :=s-2 mod 2p-1;

If s ==0 then

p-1 is prime

else

p-1 is composite;

endif

[PREVIOUS][NEXT]