Prime Numbers

Finding prime numbers

Prime numbers in modern life

Resources

A prime number is any number greater than 1 that is divisible only by itself and 1. The only even prime number is 2, since all other even numbers are at least divisible by themselves, 1, and 2.

The idea of primacy dates back hundreds of years. Mathematicians began putting forth ideas concerning prime numbers as early as 400 BC, but Greek mathematician Euclid is largely credited with publishing the first concrete theories involving prime numbers in his work Elements (c. 300 BC). Since then, prime numbers have proved to be elusive mysteries in the world of mathematics.

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: p₁, p ₂, p ₃,. . .p _N, with p ₁ =2,p ₂ =3, p ₃ = 5, and p _N = the largest of the prime numbers (remember, we are assuming there are a finite, or limited, number of primes). Now, form the equation p₁p₂p₃...p_N + 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 b^x - 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.

KEY TERMS

Carmichael numbers— Some numbers that have qualities of primes, but are not prime.

Euclid— Greek scientist credited with the first theories of prime numbers.

Factors— Numbers that when multiplied equal the number to which they are factors.

Sieve of Eratosthenes— One method for locating primes.

Twin primes— Prime numbers that appear as consecutive odd integers.

Prime numbers in modern life

A question one might ask at this point is “How is any of this important?” Believe it or not, theories about prime numbers play an important role in big money banking around the world.

Computers use large numbers to protect money transfers between bank accounts. Cryptographers, people who specialize in creating and cracking codes, who can factor one of those large numbers are able to transfer money around without the consent of the bank. This results in computerized bank robbery at the international level.

Knowing how to protect these accounts relies on prime numbers, as well as other theories involving factoring. As more and more of the world uses this method of protecting its money, the value of facts concerning primes grows every day.

Resources

BOOKS

Karush, William. Dictionary of Mathematics. Webster’s New World Printing, 1989.

Weisstein, Eric W. The CRC Concise Encyclopedia of Mathematics. New York: CRC Press, 1998.

Prime numbers

A prime number is any number greater than 1 that is divisible only by itself and 1. The only even prime number is 2, since all other even numbers are at least divisible by themselves, 1, and 2.

The idea of primacy dates back hundreds of years. Mathematicians began putting forth ideas concerning prime numbers as early as 400 b.c., but Greek mathematician Euclid is largely credited with publishing the first concrete theories involving prime numbers in his work Elements (est. 300 b.c.). Since then, prime numbers have proved to be elusive mysteries in the world of mathematics .

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.

Prime numbers in modern life

A question one might ask at this point is "How is any of this important?" Believe it or not, theories about prime numbers play an important role in big money banking around the world.

Computers use large numbers to protect money transfers between bank accounts. Cryptographers, people who specialize in creating and cracking codes, who can factor one of those large numbers are able to transfer money around without the consent of the bank. This results in computerized bank robbery at the international level.

Knowing how to protect these accounts relies on prime numbers, as well as other theories involving factoring. As more and more of the world uses this method of protecting its money, the value of facts concerning primes grows every day.

Resources

books

Karush, William. Dictionary of Mathematics. Webster's New World Printing, 1989.

Weisstein, Eric W. The CRC Concise Encyclopedia of Mathematics. New York: CRC Press, 1998.

KEY TERMS

Carmichael numbers

—Some numbers that have qualities of primes, but are not prime.

Euclid

—Greek scientist credited with the first theories of prime numbers.

Factors

—Numbers that when multiplied equal the number to which they are factors.

Sieve of Eratosthenes

—One method for locating primes.

Twin primes

—Prime numbers that appear as consecutive odd integers.

prime numbers These are whole numbers that have only two factors ― the number itself and the number one. The only even prime number is two: all other prime numbers are odd. These are the prime numbers below 100.

prime number Positive or negative integer, excluding one and zero, that has no factors other than itself or one. Examples are 2, 3, 5, 7, 11, 13, and 17. The integers 4, 6, 8, … are not prime numbers since they can be expressed as the product of two or more primes.