ermat's Little Theorem:

For any prime pp and integer aa$,$ ap$11$modpap$11$modp.

It happens that the converse to FLT is often but not always true.

That is$,$ if nn is composite and aa is an integer, then more often than not an$11$modnan$11$modn.

We can use this as the basis of a simple primality test, called the Fermat Test.

For a in Zna in Zn we make the following definitions.

$1)$ We call aa a Fermat Liar for nn if an$11$modnan$11$modn, where a$(0,1,$n$1)$a$(0,1,$n$1).$

$2)$ We call aa a Fermat Witness for nn if an$11$modnan$11$modn, where a$(0,1,$n$1)$a$(0,1,$n$1).$

If a number is composite, then $2$ is very often a Fermat Witness.

What is the smallest composite integer nn greater than $38743874$ for which $2$ is not a Fermat Witness?