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.
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 Web Resource. https://mathworld.wolfram.com/FermatsLittleTheoremConverse.html