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 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.

© 1996-9

1999-05-26