Why does Fermat’s little theorem not provide a complete test for prime numbers?

Fermat’s Little Theorem, proposed by the French mathematician Pierre de Fermat, states that for any prime number $p$ and any integer $a$ not divisible by $p$, $p$ must divide $a^p-a$. While this condition is necessary for a number to be prime, it is not sufficient, meaning the theorem does not provide a complete test for primality.12

The test fails to be definitive because of the existence of pseudoprimes—composite numbers that satisfy the theorem's condition for specific bases. For example, the number 341 is composite ($11\times 31$), yet it divides $2^{341}-2$ evenly, causing it to pass the test for the base $a=2$. Furthermore, there are Carmichael numbers, such as 561, which satisfy the theorem for all bases with which they are relatively prime, despite being composite. Because these composite numbers mimic the behavior of primes under the theorem, it cannot be used as a standalone proof of primality.12