*(Continues this post.)*

So we have this integer $n$, and we would like to know whether it is prime or not. We have used the Rabin-Miller compositeness test on it a couple times and it has always turned negative, so the probability that $n$ is not prime is excruciatingly small. Still, we have not *proved* that $n$ is prime; in order to do that, we need a real *primality* test. Basically, we are looking for a converse to Fermat’s theorem. Such a converse was found by Pocklington and improved by Lehmer. Essentially, it is based on the fact that an integer $a$ of multiplicative order $n-1$ modulo $n$ (*i.e.*, such that $a^{n-1} \equiv 1 \pmod n$ and $a^e \not \equiv 1 \pmod n$ for all positive $e < n-1$) exists if and only if $n$ is prime. More precisely: