Primes, Puzzles of

Many number puzzles involve prime numbers. Understanding the distribution of prime numbers is hence an important part of understanding the number system.

Generating Primes

A prime number is a number evenly divisible only by itself and by one. Seventeen is a prime number because there is no positive integer that can be divided into seventeen without a remainder except for one and 17. The smaller primes are well known: 1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, and so on. (Some mathematicians leave out 1.)

A straightforward method for generating primes was proposed by the Greek mathematician Eratosthenes (276 b.c.e.–194 b.c.e.). To begin this procedure, write down all the integers as high as you wish to go. Starting with 2, cross out every second number. Then, starting with 3, cross out every third number. Find the next uncrossed number, 5, and then cross out every fifth number. The next uncrossed number is 7, so cross out every seventh number. This procedure can be repeated indefinitely.

The scheme just described is sometimes called the sieve of Eratosthenes. The procedure will produce every prime number up to whatever value one chooses, but the process is time-consuming and labor-intensive. Different methods are used to generate larger prime numbers.

Predicting Primes

There are many unsolved questions about prime numbers. One of the most famous of all unsolved mathematical problems is predicting the occurrence of prime numbers. If the primes are numbered consecutively, is there a relation between a prime and its number? No one has ever discovered one. If the n th prime is known, can the (n + 1)th prime always be calculated? No one has figured out how.

One direct method of determining if a number is prime is by attempting to factor it. Factoring a number involves dividing it by all the prime numbers smaller than the number's square root. For example, suppose we wish to determine if 221 is a prime number. The square root of 221 is less than 15 (since 15² = 225), so we must test each prime number smaller than15. The number is odd, so 2 is ruled out as a factor. Likewise, 3 can be ruled out since the digits do not add up to a multiple of 3. The number does not end in 0 or 5, so 5 cannot be a factor. Long division shows that 7 and 11 are not factors. However, 13 is a factor, so 221 is not prime.

The process just described was easy to use for determining if 221 is a prime number, but it would be a very difficult procedure to use for a very large number.

Considering the Largest Prime

Is there a largest prime number? Euclid proved there was not, so at least that question about primes has been answered. Euclid's proof is fairly easy to follow. Assume that there is a largest prime number and call it p. Let N = 2 × 3 × 5 × 7 ×…× p. Thus, N is a number divisible by all the prime numbers up to p. N + 1 is clearly not divisible by any of the prime numbers up to and including p, because division by p or any smaller prime would leave a remainder. So there are only two possibilities for N + 1:

1. N + 1 is divisible by some prime number larger than p.
2. N + 1 is prime.

Either of these possibilities contradicts the original assumption that p is the largest prime number. When an assumption leads to a contradiction, the assumption must be false. Thus Euclid proved there is no largest prime number.

Prime Twin Pairs

One of the first things noticeable about tables of primes is that there are many instances of pairs of prime numbers with the form n and n + 2. Examples are 11 and 13, 17 and 19, 29 and 31, 101 and 103, 881 and 883, and so on. These are sometimes called prime twin pairs. No one has ever determined if this is an interesting property of numbers or just a curious coincidence. The instances of pairs of prime numbers decrease for ever larger numbers. This leads to the question: Is there a largest prime twin pair? Like most questions about primes, this one has yet to be answered. No such simple proof as Euclid's exists for prime twin pairs.

Distribution of Primes

Another pattern that mathematicians try to understand is the distribution of primes. While prime numbers generally get less frequent as they get larger, there is so much variation in this behavior that it cannot be used to predict the next prime. The interval between primes also tends to get larger with larger numbers, but with so much variation that prediction is difficult. For example, between 100,001 and 100,100, there are six primes. In the next 100-number interval—100,101 to 100,200—there are nine prime numbers. Between 299,901 and 300,000 there are also nine prime numbers.

Approximating Primes

While there is no formula that can be used to predict the occurrence of primes, there are several formulas that come close. One of the best is a formula developed by the mathematician Georg Riemann: . This formula is exactly correct nineteen times between 1 and 9,000,000 and quite close the rest of the time. While the formula can be used to suggest a candidate large prime, the number must still be tested to see if it is actually prime.

Goldbach's Conjecture

An interesting unsolved problem concerning primes is known as Goldbach's Conjecture, which states that every even number greater than 2 can be written as the sum of two primes. Thus 12 = 5 + 7, 18 = 7 + 11, and so on.

Goldbach's Conjecture was first stated in 1742 in a letter written by Prussian historian and mathematician Christian Goldbach (1690–1764) to the Swiss mathematician Leonhard Euler (1707–1783). Although Euler spent much time trying to prove it, he never succeeded. For the next 250 years, other mathematicians would struggle in similar fashion.

While it seems obvious and deceptively simple, as of this writing no one has proved Goldbach's Conjecture. Supercomputers have proved Gold-bach's Conjecture for every even number up to 400,000,000,000,000, and most mathematicians believe it to be true, yet the search for an abstract proof goes on. In 2000 a British publishing company offered a $1 million prize for proof of Goldbach's Conjecture by the year 2002 if it is accepted and published by 2004.

Palindromic Primes

One of the more curious prime number puzzles that mathematicians have examined is the occurrence of palindromic primes. A palindrome is a word or phrase that reads the same forward or backward. Some examples of palindromic primes are 101, 131, 151, 181, 313, 353, 727, 757, 787, 79997, 91019, 1818181, 7878787, 7272727, and 3535353. There is an infinite number of palindromic primes.

see also Number Sets.

Elliot Richmond

Bibliography

Beiler, Albert H. Recreations in the Theory of Numbers—The Queen of Mathematics Entertains. New York: Dover Publications, 1964.

Tietze, Heinrich. Famous Problems of Mathematics. Baltimore: Graylock Press, 1965.

STUDENTS, COMPUTERS, AND LARGE PRIME NUMBERS

In 1998, college student Roland Clarkson discovered the largest prime number known at that time. It was so large it could fill several books. In fact, college students are finding some of the largest prime numbers today by using networks of cooperating personal computers and software downloadable from the Internet.