Posted by Jason Polak on 26. November 2017 · Write a comment · Categories: number-theory · Tags: ,

Since the days of antiquity, we’ve always been looking for ways to determine whether a natural number is prime. Trial division up to the square root of a number quickly becomes tedious, thought it is worth noting that even on my fairly old laptop a slightly optimised trial-division algorithm will list all the primes under 10^7 in just under seven seconds.

Another method that sometimes works is Fermat’s little theorem:

Theorem. If $n$ is a prime number then for every $a$,
$$a^n\equiv_n a.$$

Here, I’m using the notation to mean $a^n – n$ is divisible by $n$. Let’s do some examples: 4^11 – 4 = 4194300, which is divisible by 11 (you can see this directly by using the alternating sum digit test: 4 – 1 + 9 – 4 + 3 = 11). On the other hand, $2^{69} – 2 = 590295810358705651710 \equiv_{69} 6$. Of course, from the nature of the theorem, if $a^n\equiv_n a$ is not true then $n$ is composite, so it can tell you for sure if a number is composite but not if a number is prime.
More »