Primality Testing

Date: 04/22/98 at 00:50:50
From: Matthew
Subject: prime numbers

Is there any fomula to find if a number is a prime? For example, is 
there a formula to find out if 1642749328584902 is a prime number?

Matthew

Date: 04/22/98 at 10:26:29
From: Doctor Wilkinson
Subject: Re: prime numbers

An excellent question! Of course your example is not prime, because 
it ends in 2 and all numbers that end in 2 are divisible by 2.

There is no simple way to check whether a number is prime, but there 
are methods that work much better for large numbers than just trying 
all possible divisors. These methods are too complicated to describe 
in a short note, but I can give you an idea of how they work.

If a number is prime and you take any number that is bigger than one 
but less than the prime, then it turns out that if you keep 
multiplying by that number, dividing by the prime and taking the 
remainder, if you do this one less times than the prime, the result is 
always 1. For example, 7 is a prime. Start with 3 and call that 
step 1. Multiply by 3 you get 9. Divide by 7 and take the remainder 
and you get 2. That's Step 2. Now multiply by 3 and you get 6. Divide 
by 7 and take the remainder and you still get 6. That's step 3. 
Continuing:

     step 4:  6 * 3 = 18; divide by 7, remainder is 4
     step 5:  4 * 3 = 12; divide by 7, remainder is 5
     step 6:  5 * 3 = 15; divide by 7, remainder is 1

So after 7 - 1 steps you get 1.

Now look at it the other way around. Start with a number and suppose 
you don't know whether it's prime or not. Take a number between 1 and 
the number and go through the steps I've described. Suppose you don't 
get a 1. Then you know the number ISN'T a prime.

Unfortunately, if you do end up with a 1, you can't say for sure that 
the number is a prime. But there are fancier versions of this basic 
idea that will tell you a number is almost certainly a prime if it 
passes the test.

Also, in the version I've described you have to do an awful lot of
multiplying and dividing to do the test. But it turns out you can do 
the test much faster than the way I've described.

You may have heard of very large prime numbers being discovered using
personal computers.  For these numbers, which are a particular kind of
number called a "Mersenne number," tests similar to the one I've 
described will tell you for sure whether the number is prime or not.

For more about prime numbers, see the Dr. Math FAQ:

  http://mathforum.org/dr.math/faq/faq.prime.num.html   

-Doctors Wilkinson and Sarah,  The Math Forum
Check out our web site! http://mathforum.org/dr.math/