# 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 ${\sqrt {n}}$ . Both methods are very inefficient, slow to compute.

### Fermat's little theorem

Definition of $a\equiv b{\pmod {c}}$ : This means a-b divides c.

Fermat's little theorem states that for a prime p and a natural number a: $a^{p}\equiv a{\pmod {p}}$ This is proven by induction. It is obvious for case a=1: $1^{p}\equiv 1{\pmod {p}}$ . Now we prove the case a+1: $(a+1)^{p}\equiv a+1{\pmod {p}}$ $\sum _{i=0}^{p}{\binom {p}{i}}a^{i}\equiv a+1{\pmod {p}}$ Because ${\binom {n}{k}}={\frac {n!}{k!\cdot (n-k)!}}$ we know the middle terms divide p. They therefore cancel out.

$a^{p}+1\equiv a+1{\pmod {p}}$ so $a^{p}\equiv a{\pmod {p}}$ which was the induction hypothesis.

We have to remember if a number n does not satisfy $(a+1)^{n}\equiv a+1{\pmod {n}}$ 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.