Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
High School Number Theory