Fermat's little theorem states that if p is prime and , then
If we want to test if n is prime, then we can pick random a's in the interval and see if the equation above holds. If the equality does not hold for a value of a, then n is composite (not prime). If the equality does hold for many values of a, then we can say that n is probably prime, or a
It may be in our tests that we do not pick any value for a such that the equality fails. Any a such that
when n is composite is known as a Fermat liar. If we do pick an a such that
then a is known as a Fermat witness for the compositeness of n.
is the modulo operation. Its result is what remains, if p is divided by n. As an example,