2 minute read

# Prime Numbers

## Finding Prime Numbers

Any discussion on the location process for prime numbers must begin with the statement of one fact: there is an infinite number of prime numbers. All facts in mathematics must be backed by a proof, and this one is no exception. Assume all prime numbers can be listed like this: p1, p2, p3,...pN, with p1 = 2, p2 = 3, p3 = 5, and pN = the largest of the prime numbers (remember, we are assuming there are a finite, or limited, number of primes). Now, form the equation p1p2p3...pN + 1 = X. That means that X is equal to the product of all the primes plus 1. The number produced will not be divisible by any prime number evenly (there will always be a remainder of 1), which indicates primacy. This contradicts the original assumption, proving that there really are an infinite number of primes. Although this may seem odd, the fact remains that the supply of prime numbers is unlimited.

This fact leads to an obvious question-how can all the prime numbers be located? The answer is simple—they cannot, at least not yet. Two facts contribute to the slippery quality of prime numbers, that there are so many and they do not occur in any particular order. Mathematicians may never know how to locate all the prime numbers.

Several methods to find some prime numbers do exist. The most notable of these methods is Erasthenes's Seive, which dates back to ancient Greek arithmetic. Named for the man who created it, it can be used to locate all the prime numbers between 2 and N, where N is any number chosen. The process begins by writing all the numbers between 2 and N. Eliminate every second number after 2. Then eliminate every third number, starting with the very next integer of 3. Start again with the next integer of 5 and eliminate every fifth number. Continue this process until the next integer is larger than the square root of N. The numbers remaining are prime. Aside from the complexity of this process, it is obviously impractical when N is a large 100 digit number.

Another question involving the location of prime numbers is determining whether or not a given number N is prime. A simple way of checking this is dividing the number N by every number between 2 and the square root of N. If all the divisors leave a remainder, then N is prime. This is not a difficult task if N is a small number, but once again a 100 digit number would be a monumental task.

A shortcut to this method was discovered in 1640 by a mathematician named Pierre de Fermat. He determined that if a number (X) is prime it divides evenly into bx - b. Any number can be used in the place of b. A non-prime, or composite, used in the place of b leaves a remainder. Later it was determined that numbers exist that foil this method. Known as Carmichael numbers, they leave no remainder but are not prime. Although extremely rare, their existence draws attention to the elusive quality of prime numbers.

One final mysterious quality of prime numbers is the existence of twin primes, or prime pairs. Occasionally, two consecutive odd numbers are prime, such as 11 and 13 or 17 and 19. The problem is no theory exists to find all of them or predict when they occur.