A prime number is a positive integer greater than 1 for which the only divisors are 1 and the number itself. For example, 17 is a prime number because the only divisors of 17 are 1 and 17, while 18 is not prime because 2, 3, 6, and 9 all divide 18 in addition to 1 and 18. About 2300 years ago, Euclid gave one of the first known proofs using the method of contradiction when he proved in the Elements that there are infinitely many prime numbers. Suppose that there are only a finite number of primes. Let p be the largest prime number. Multiply together all the prime numbers and add 1. This number cannot be prime because it is bigger than p, so it must have a prime divisor. But that prime divisor would then have to divide the number 1, which is impossible. Therefore there cannot be a finite number of primes. Euclid also gave a proof that every integer can be written as the product of primes in essentially one way.
Eratosthenes of Cyrene (276 b.c.-197 b.c.) described a systematic algorithm, now called the sieve of Eratosthenes, for finding prime numbers that is still occasionally used in modern computer programs. First write down the positive integers in numerical order. Strike out the number 1 since it is not prime. Two is the first prime. Now strike out every second number following 2. Strike out every third number following the number 3, every fifth number following 5, and continue in this manner to strike out every nth number following the number n. The numbers with no strikes through them are prime numbers.
One problem with the sieve of Eratosthenes is that it does not produce a formula for computing prime numbers directly. The French mathematician Pierre de Fermat (1601-1665) thought he had discovered such a formula when he conjectured that the numbers 2n+1 were always prime if n is a power of 2. He verified his conjecture for n = 1, 2, 4, 8 and 16. In 1732, however, Euler showed that for n = 32, the resulting number 429,467,297 is divisible by 641 and hence is not a prime.
One of the most important theorems of analytic number theory is the prime number theorem. This result asserts that for large values of n, the number of primes less than n is approximately n/log(n). Here the logarithm refers to the natural logarithm using the base e. This result was observed by Gauss around 1800 on the basis of extensive numerical evidence, but was not proved until 1896 by Jacques Hadamard and, independently, by Charles Jean de la Vallée-Poussin. Many important results and techniques of analysis and analytic number theory owe their existence to attempts to prove the prime number theorem and other problems about prime numbers.
Numbers of the form 2p-1 are called Mersenne numbers in honor of the French monk Marin Marsenne (1588-1648). It is not difficult to prove that if the number n = 2p-1 is prime, then p must also be prime. In 1644 Mersenne made a claim about the converse statement. He asserted that for 11 of the prime numbers p smaller than 257, the number n is prime, and that n is not prime for the other 44 prime values of p smaller than 257. It took over 300 years to establish that Mersenne was correct for all but five of his values of p. Mathematicians looking for large prime numbers continue to look at Mersenne numbers. The largest known prime as of February 1998 is the Mersenne number 23021377-1, which has 909,526 digits. This prime was discovered as part of the Great Internet Mersenne Prime Search conducted over a distributed network of almost 4,000 personal computers, using spare computer time that would otherwise have been wasted while the computer waited for input.
The search for large prime numbers is not an idle exercise for mathematicians. Searching for Mersenne primes has been used as a test for computer hardware. The software programs used for testing prime numbers are also used by manufacturers to find defects in computer chips. The public-key cryptography method invented by Ronald Rivest, Adi Shamir, and Leonard Adleman in 1977 uses a pair of complementary keys to encode and decode messages. The secret key, which is based on two large prime numbers typically of length between 100 and 200 digits, is used to decipher messages. The public key is the product of these two prime numbers and is used to encrypt the information. The security of RSA encryption depends on the fact that it is easy to find large prime numbers but very difficult to find the prime factors of a large composite number.
This is the complete article, containing 782 words
(approx. 3 pages at 300 words per page).
