Mathematicians have tried in vain to this day to discover some order in the sequence of prime numbers, and we have reason to believe that it is a mystery into which the mind will never penetrate.
The probability that a random integer N is prime is roughly 1/ln(N), where ln(N) is the natural logarithm (base e) of N. This is a formulation of a more general statement known as the prime number theorem.
The Prime Numbers
The smallest prime numbers are 2, 3, 5, 7, 11, 13... . An example of a composite number is 6, which is evenly divisible by both 2 and 3.
It is easy to prove that there are an infinite number of primes using Euclid's second theorem. If there were a finite number of primes, you could multiply them all together and add 1. The resulting number would show the existence of a new prime, since it would not be divisible by any smaller prime (it would always have a remainder of 1).
To construct a table of all prime numbers less than n, you would use a method called the Sieve of Eratosthenes. Simply write down an ordered list of all counting numbers greater than 1. Beginning with 2*2 = 4, cross out every second number:
- 2 3
45 67 89 1011 ...
then beginning with 3*3 = 9 cross out every third number:
- 2 3
45 67 8 9 1011 ...
Beginning with 5*5 = 25, cross out every fifth number, then repeat for the primes 7, 11, 13, etc. until .
To determine whether a number is prime, you can use the trial division method, provided the number you are testing is not too large. Let N be the number being tested and s be its square root. Divide N by each number in the prime table, beginning with 2. If there is no remainder, stop--N is composite. Otherwise, test again with the next largest prime in the table. If the next largest prime is greater than s, stop--N is prime.
For larger values of N, a method based on Fermat's theorem can be used, though it usually requires a computer. Start with the number 1, and double it N-1 times. Divide this number by N, keeping only the remainder. If the remainder is greater than 1, N is composite. Unfortunately, the converse is not true--if the remainder is 1, N is probably prime, but not necessarily. Algorithms which improve on this method exist, and primality testing is today an active subject of mathematical research.
The Largest Known Prime
A Mersenne prime is a prime number M that is of the form M = 2n − 1, where n is some prime number. As of April, 2007, only 44 Mersenne Primes have been found. The largest known prime 232582657-1, is a Mersenne Prime. The concept of a Mersenne Prime was discovered by the French theologian, philosopher and mathematician Marin Mersenne.
Most mathematicians believe a proof of the Riemann hypothesis is the best hope for discovering some pattern in the distribution of prime numbers. The Clay Mathematics Institute has offered a one million dollar prize for a proof of the Riemann hypothesis.
The security of public-key cryptography schemes such as RSA depend on the difficulty of prime factorization, if a pattern in the distribution of prime numbers is discovered, then such cryptographic schemes could become vulnerable to attack.
- Mersenne Prime from Wolfram