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  is prime to  and  and there is no integer  for which , then  is not prime. Here,  is called a witness to the primality of . This theorem is the basis for the Pratt primality certificate.

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.