Primality Tests

Now we know what prime numbers are the next natural step is to try to recognize prime numbers.

Problem: Given a natural number n we want to determine whether it is prime

There are very simple methods to do this. The first would be to make a list of all prime numbers up to a certain limit and look whether n is in the list. The second is trial division by any prime less or equal to . Both methods are very inefficient, slow to compute.

Fermat's little theorem[edit | edit source]

Definition of : This means a-b divides c.

Fermat's little theorem states that for a prime p and a natural number a:

This is proven by induction. It is obvious for case a=1: . Now we prove the case a+1:

Because we know the middle terms divide p. They therefore cancel out.

so which was the induction hypothesis.

We have to remember if a number n does not satisfy we know it is composite. However, if it does satisfy the expression we are not sure it is a prime number. A composite n that satisfies the equation is called a Fermat pseudoprime to base a.