Most of the material presented here can be found in the wonderful and very readable book

Joseph H. Silverman, *A Friendly Introduction to Number Theory, *Prentice-Hall,* 1997.*

* Definition:* A positive integer is called a

7 is prime, since 1 and 7 are the only divisors of 7.

15 is composite (not prime), since 15=3×5.

1 is not a prime number.

Here is a list of the first 100 prime numbers:

**Theorem (Euclid):** There are infinitely many prime numbers.

**Proof.**

Suppose is a complete list of all prime numbers.

Consider Clearly is not divisible by any of the primes .

Either is a prime number itself (a contradiction; is not on the list . Why?), or is divisible by a number other than one of the listed primes, and thus divisible by a prime number not on the list , a contradiction as well.

Actually, both possibilities can occur. Here is the list of the first ten prime numbers:

Multiplying them and adding 1 yields a composite number, whose prime factors are not on the list:

This means 6469693231=331 × 571 × 34231.

The list of the first 11 prime numbers yields a prime number:

How rare are prime numbers?

More precisely, one can ask about the behavior of the function π(x), the number of prime numbers less than or equal to x.

Here is a plot of this function:

Gauss and Legendre both conjectured the following:

**Prime Number Theorem (Hadamard and Vallee-Poussin, 1896):**

For large , behaves asymptotically like the function .

Here is a plot of their quotient .

Here is a curious fact. If we consider small primes , -1 turns out to be prime, too:

What's wrong with this list? 11 is missing!

__Definition:__ A prime number of the form -1 is called a **Mersenne prime**.

In this case, is called a **Mersenne exponent**.

Why are these numbers called Mersenne primes? Marin Mersenne boldly claimed in 1644 that a complete list of Mersenne exponents less than 258 is given by

Two of his conjectured exponents don't work; moreover he missed 89 and 107. Here is the correct list:

The fact that -1 is indeed prime, was proved by Lucas in 1876. The next Mersenne exponents were only found with the help of a computer by Robinson in 1952.

Let me list is a result we have already , at least partially, tacitly assumed:

**Theorem:** If -1 is prime, then =2 and is prime.

**Proof.**I will only prove that

Assume that is not prime, then , with .

So -1 = -1.

Do you remember how to factor -1? -1 "works" the same way:

-1 = -1) × ++ +1).

End of the story! -1 is divisible by -1), and hence not prime.

__Definition:__ A number is called **perfect**, if it equals the sum of its proper divisors.

6 and 28 are the smallest perfect numbers:

Now notice that × -1), and that 28 = × (-1). Is there a connection to Mersenne primes? You bet! Let's try this for the Mersenne prime -1:

It is in fact true, that every Mersenne prime yields a perfect number:

**Theorem (Euclid):** If -1 is prime, then -1) is perfect.

**Proof.**Let's set

All we have to do is to sum up the proper divisors of × .

Here is a complete list of the proper divisors:

.

The geometric series formula tells us their sums:

= -1, and .

Thus the sum of the proper divisors of × is given by

-1) + -1) = -1) × is a perfect number.

What about the converse? It is "half" true:

**Theorem (Euler): **If is an **even** perfect number, then -1) for some Mersenne prime

So, searching for even perfect numbers is equivalent to searching for Mersenne primes.

It is not known whether there are odd perfect numbers; there are none less than

How many Mersenne primes are known? As of this date (March 1999) there are 37 known Mersenne primes.Their **exponents** are listed below:

1 |
2 |

2 |
3 |

3 |
5 |

4 |
7 |

5 |
13 |

6 |
17 |

7 |
19 |

8 |
31 |

9 |
61 |

10 |
89 |

11 |
107 |

12 |
127 |

13 |
521 |

14 |
607 |

15 |
1279 |

16 |
2203 |

17 |
2281 |

18 |
3217 |

19 |
4253 |

20 |
4423 |

21 |
9689 |

22 |
9941 |

23 |
11213 |

24 |
19937 |

25 |
21701 |

26 |
23209 |

27 |
44497 |

28 |
86243 |

29 |
110503 |

30 |
132049 |

31 |
216091 |

32 |
756839 |

33 |
859433 |

34 |
1257787 |

35 |
1398269 |

36 |
2976221 |

37 |
3021377 |

Why do people hunt for Mersenne primes?

- Mersenne primes are usually the biggest primes known.

- Deciding whether -1 is a Mersenne prime, is relatively easy. In fact, Lehmer refined the procedure Lucas had used to determine whether 127 was a Mersenne exponent into what is known as the **Lucas-Lehmer test** for Mersenne numbers. It takes "only a few days" on a Pentium PC to test one exponent in the current range of interest.

- Everyone with spare computer time can join!

**Welcome to **GIMPS**, the "***reat*** ****I***nternet*** ****M***ersenne*** ****P***rime*** ****S***earch***"!**

**The** GIMPS status** page.**

Converted by