Prime Numbers
A prime number is a number that has just two factors (divisors): itself and the number 1. For example, 7 is prime, since its only divisors are 7 and 1. The number 6 is not prime, since it is divisible by 2 and 3. Numbers that have more than two divisors are called composite numbers.
Prime numbers have fascinated mathematicians since the age of Pythagoras. By Euclid's time, mathematicians knew the fundamental theorem of arithmetic: every whole number can be written as the product of prime numbers, in a unique way (up to reordering of the factors). For example, 60 can be written as 2 x 2 x 3 x 5. Thus, prime numbers can be looked upon as the building blocks for the whole numbers.
Among small numbers, many are prime: 2, 3, 5, 7, 11, 13 and so forth. Among larger numbers, however, the number of primes thins out greatly, raising an important question for the ancients: is there a finite or infinite number of primes? The answer to this question was known to Euclid; in his Elements, he proves that there is an infinite collection of primes. His proof, which is remarkably simple and elegant, is one of the first recorded proofs to use the method called reductio ad absurdum, which works by assuming the opposite of the desired statement, and then following a logical train of reasoning until an absurdity is reached.
Thus, Euclid starts out by assuming the opposite of what he wants to prove: he assumes that there are only finitely many primes. If that is the case, he reasons, we can make a list of all the primes; let's suppose they are denoted p1, p2, p3, ... , pn. Let's consider a new number: N=p1p2p3 ... pn+1. What kind of number is N? It is not a prime number, because it is larger than all of the prime numbers on the list. But neither is N a composite number: by the Fundamental Theorem of Algebra, any composite number can be broken down into a product of primes, but N is not divisible by any primes (p1 divides into N with a remainder of 1; p2 divides into N with a remainder of 1; and so forth). There is only one number that is neither prime nor composite: the number 1. But N is certainly larger than 1. So N is a number that is neither 1, nor prime, nor composite. This is an absurdity. Hence our original assumption, that there is a finite collection of primes, must be wrong; we have proven that the number of primes is infinite.
In around 200 BC, the Greek mathematician Eratosthenes came up with an algorithm for finding prime numbers, now known as the Sieve of Eratosthenes. It works in the following way. Suppose you want to find all the prime numbers less than 100; start with a list of all the numbers from 1 to 100. The number 2 is prime, so circle it. Now anything that is divisible by 2 is not prime, so cross out every number divisible by 2. The first uncrossed number on the list is 3. Since 3 has not been crossed out, it is not divisible by any smaller numbers, hence it is prime; circle it, and cross out all the numbers divisible by 3. Four is crossed out, so proceed to 5, circle it, and continue in this way. The circled numbers will be a complete list of the primes less than 100.
Beginning in the 17th century, prime numbers played an important role in the growing field of number theory, the branch of mathematics that seeks patterns in the number system. The great mathematician Pierre de Fermat, now most famous for his recently proven last theorem (see Fermat's last theorem), proved that every prime number of the form 4n + 1 can be written as the sum of 2 squares, in a unique way. He also conjectured that when n is a power of 2, the number 2n+1 is prime. This is true when n=1, 2, 4, 8, and 16. But a century after Fermat, Leonhard Euler showed that it is false when n=32: 232+1 is not prime.
The field of number theory abounds with open questions about prime numbers. One of the most famous is Goldbach's Conjecture, formulated in 1742 in an exchange of letters between Christian Goldbach and Euler. It states that every even number greater than 2 can be written as the sum of two primes. Goldbach's conjecture has been verified for all numbers smaller than 4 x 1014, but so far no one has come up with a proof, and it remains possible that there is some tremendously large number for which the conjecture is false. Another important open problem is the Twin Primes Conjecture, which hypothesizes that there are infinitely many "twin primes," pairs of primes only 2 apart.
Although the prime numbers seem to be distributed in a very uneven way, in the large scale their thinning out follows a definite pattern. In the 19th century, mathematicians proved the Prime Number Theorem, which states that when n is a large number, the density of primes near n is 1/log(n). They also showed that when n is large, the number of primes less than n is roughly n/log(n).
The problem of factoring large numbers is extremely difficult, so even though it is known that there are infinitely many primes, finding them is not easy. The largest known prime to this day is the number 26972593 - 1, which has 209860 digits.
This is the complete article, containing 921 words
(approx. 3 pages at 300 words per page).
