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

### Prime Number Tests

```
Date: 11/12/98 at 10:50:06
From: Natalie
Subject: Prime Number

Is the number 55409243 prime?  Also, how can you test to see if a
number is prime or not?
```

```
Date: 11/12/98 at 12:39:03
From: Doctor Rob
Subject: Re: Prime Number

No, 55409243 is not prime.

You ask a very good question about testing for primality.  There are
quite a few ways to do that.  They range from the very simple, yet
time-consuming, to the very sophisticated and quite fast.

The simplest way is to use Trial Division.  Let N be the number in
question to be tested. Divide by all prime numbers less than or equal
to sqrt(N). If none go in evenly, then N is prime. In your case, you
would divide by all the prime numbers less than 7443.73, of which there
are more than 900.

Here is a slightly more complicated way.

1) Pick any a with 1 < a < N-1.
2) Find the greatest common divisor d of a and N.
If d > 1, then N is composite, and d is a factor.
If d = 1, then compute the remainder of a^(N-1) when divided by N.
If this is not 1, then N is composite.
If this is 1, you can't tell if N is prime or not.

Most composite numbers will be revealed to be composite by this method,
however. This method is called the Fermat Test.

In your case, I picked a = 3, and found that a^(N-1) left a remainder
of 4483955 when divided by N, so N cannot be prime. This computation
involved 26 squarings of 8-digit numbers, 15 multiplications by 3, and
26 divisions by N. This is slightly less work than 900-odd divisions of
N by small primes.

Some other ways involve trying to factor the number by various
factoring algorithms, like Trial Division above, and either succeeding
or failing. Still other ways depend on properties of prime numbers, and
seeing whether N does or doesn't have those properties, like the Fermat
Test above. If it doesn't, N is not prime. If it does, you cannot be
sure. The fastest algorithms for very large numbers are also the most
difficult to describe and use the most sophisticated mathematics.

- Doctor Rob, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Number Theory
Middle School Prime Numbers

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search