The converse of Fermat's little theorem is also known as Lehmer's theorem. It states that, if 
is an integer, 
is an integer relatively
prime to 
, 
, and there is no integer 
with 
for which 
,
then 
is prime. Here, 
is called a witness to the primality
of 
.
This theorem is the basis for the Pratt certificate.
Fermat's Little Theorem Converse
See also
Fermat's Little Theorem, Pratt Certificate, Primality Certificate, WitnessExplore with Wolfram|Alpha
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.Referenced on Wolfram|Alpha
Fermat's Little Theorem ConverseCite this as:
Weisstein, Eric W. "Fermat's Little Theorem Converse." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/FermatsLittleTheoremConverse.html