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 prime number, if it has exactly 2 divisors (1 and itself).
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.
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.
I will only prove that -1 prime implies that is prime.
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.
Let's set -1. Note that is prime.
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:
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 Internet Mersenne Prime Search"!
The GIMPS status page.