How can Fermat’s little theorem help test whether a number is composite?

Fermat’s Little Theorem, proposed by the French mathematician Pierre de Fermat, provides a necessary condition for a number to be prime. It states that for any prime number $p$ and any integer $a$ that is not divisible by $p$, $p$ must divide exactly into $a^p-a$.12

This theorem functions as a primality test by establishing a simple rule: if a number $n$ does not divide evenly into $a^n-a$ for a chosen integer $a$, then $n$ is definitively a composite number.12

However, the test is not sufficient to prove primality because the converse is not always true. Some composite numbers, known as pseudoprimes, also satisfy the condition of dividing into $a^n-a$. For instance, 341 is a composite number ($11\times 31$), yet it divides evenly into $2^{341}-2$. Consequently, while the theorem is a powerful tool for identifying composite numbers, it cannot guarantee that a number is prime.12