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.