Fermat's Little Theorem

Let p be a prime, Our basis is that $1^p\equiv 1 \pmod{p}$ and our induction hypothesis is that $a^p \equiv a \pmod{p}$. We see that $(a+1)^p$ $=$ $a^p$ $+$ $\left\{\sum_{i=1}^{i=p-1}\binom{p}{i}a^{p-i}\right\}$ $+$ $1^p$. Each of the indicated binomial coefficients are divisible by $p$ because none of the factors of the denominator divides the numerator's factor of $p$. Hence $(a+1)^p$ $\equiv$ $a^p$ $+$ $1^p$ $\equiv$ $a+1$ $\pmod{p}$ and by pure mathematical induction $a^p$ $\equiv$ $a$ $\pmod{p}$ for all $a$. This is theorem is known as Fermat's Little Theorem.

If $\gcd(a,n)$ $=$ $1$, then we can divide the above expression by $a$ and get $a^{p-1}$ $\equiv$ $1$ $\pmod{p}$.

We can now take a square root to give $a^{\frac{p-1}{2}}$ $\equiv$ $\pm 1$ $\pmod{p}$. Using this to test a number $n$ in generally is slightly stronger than Fermat's Little Theorem.

Furthermore, let $n$ $=$ $2^ds$ $+$ $1$, where $s$ is odd. If the square root is 1 and we are allowed to take a further square root, it will be $\pm 1$ if $n$ was prime. We might be able to take as many as $d$ square roots in this way. Either the iterated square root is $-1$ or if it is $1$ and maybe allowed for another square root. Such a test is a "strong probable prime test" and is the basis of the Miller-Rabin (M-R) test.