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

Fermat's little theorem

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

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

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

Because ${\binom {n}{k}}={\frac {n!}{k!\cdot (n-k)!}}$$\binom nk = \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}}$$a^p+1 \equiv a+1\pmod{p}$ so $a^{p}\equiv a{\pmod {p}}$$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}}$$(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.