Fermat's Little Theorem Converse

The converse of Fermat's Little Theorem is also known as Lehmer's Theorem. It states that, if an Integer $x$ is Prime to $m$ and $x^{m-1}\equiv 1\ \left({{\rm mod\ } {m}}\right)$ and there is no Integer $e<m-1$ for which $x^e\equiv 1\ \left({{\rm mod\ } {m}}\right)$, then $m$ is Prime. Here, $x$ is called a Witness to the primality of $m$. This theorem is the basis for the Pratt Primality Certificate.

See also Fermat's Little Theorem, Pratt Certificate, Primality Certificate, Witness

References

Riesel, H. Prime Numbers and Computer Methods for Factorization, 2nd ed. Boston, MA: Birkhäuser, p. 96, 1994.

Wagon, S. Mathematica in Action. New York: W. H. Freeman, pp. 278-279, 1991.