Fermat's theorem gives a fast way to show a number is composite without finding a factor. That is how computers screen the huge numbers used in cryptography. But the test has a blind spot, and knowing exactly what it proves is the lesson here.
The Fermat test. To test $n$, pick a base $a$ with $1 < a < n - 1$ and compute $a^{n-1} \bmod n$ by repeated squaring.
- If $a^{n-1} \not\equiv 1 \pmod{n}$, then $n$ is certainly composite.
- If $a^{n-1} \equiv 1 \pmod{n}$, then $n$ passes: it is probably prime, but not proven prime.
Why it works
Worked example: Caught by the test
- $90 = 64 + 16 + 8 + 2$. Squares mod 91: $2^{2} = 4$, $2^{4} = 16$, $2^{8} = 256 \equiv 74$, $2^{16} \equiv 74^{2} = 5476 \equiv 16$, $2^{32} \equiv 74$, $2^{64} \equiv 16$.
- $2^{90} \equiv 16 \cdot 16 \cdot 74 \cdot 4$: $16 \cdot 16 = 256 \equiv 74$, then $74 \cdot 74 \equiv 16$, then $16 \cdot 4 = 64$.
- $2^{90} \equiv 64 \not\equiv 1$, so $91$ is composite. (Indeed $91 = 7 \cdot 13$, but the test never needed that.)
Answer: Composite.
Worked example: A pseudoprime
- $2^{10} = 1024 = 3 \cdot 341 + 1$, so $2^{10} \equiv 1 \pmod{341}$.
- $340 = 10 \cdot 34$, so $2^{340} = (2^{10})^{34} \equiv 1 \pmod{341}$.
- $341$ passes, yet it is composite: it is the smallest pseudoprime to base 2.
Answer: $2^{340} \equiv 1 \pmod{341}$.
Changing the base often exposes a pseudoprime: $3^{340} \bmod 341 = 56$, so base 3 catches 341. But $91$ fools base 3 ($3^{6} = 729 = 8 \cdot 91 + 1$, so $3^{90} \equiv 1$), and some composites fool every base coprime to them. These are the Carmichael numbers.
Worked example: A Carmichael number
- $561$ is squarefree, and $n - 1 = 560$.
- $2 \mid 560$, $10 \mid 560$ and $16 \mid 560$ (since $560 = 16 \cdot 35$).
- So $561$ passes the Fermat test for every base coprime to it, though it is composite.
Answer: Yes, $561$ is a Carmichael number (the smallest).
Common mistake
Key idea