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

### Fermat's little theorem

Definition of ${\displaystyle 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: ${\displaystyle a^{p}\equiv a{\pmod {p}}}$

This is proven by induction. It is obvious for case a=1: ${\displaystyle 1^{p}\equiv 1{\pmod {p}}}$. Now we prove the case a+1: ${\displaystyle (a+1)^{p}\equiv a+1{\pmod {p}}}$

${\displaystyle \sum _{i=0}^{p}{\binom {p}{i}}a^{i}\equiv a+1{\pmod {p}}}$

Because ${\displaystyle {\binom {n}{k}}={\frac {n!}{k!\cdot (n-k)!}}}$ we know the middle terms divide p. They therefore cancel out.

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

We have to remember if a number n does not satisfy ${\displaystyle (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.