Maths in a minute: Pretend primes

Suppose you have a prime number $p$ and some other natural number $x$. Then, no matter what the value of $x$ is, as long as it's a natural number, you will find that $$x^p - x$$ is a multiple of $p.$

This result is known as Fermat's little theorem, not to be confused with Fermat's last theorem.

Let's try the little theorem with a few examples. For $p=2$ and $x=5$ we have $$5^2 - 5 = 25 -5 = 20 = 10 \times 2.$$ For $p = 3$ and $x = 2$ we have $$2^3 - 2 = 8 - 2 = 6 = 2 \times 3.$$ And for $p = 7$ and $x =11$ we have $$11^7 - 11 = 19,487,171 - 11 = 19,487,160 = 2,783,880 \times 7.$$ You can try it out for other values of $p$ and $x$ yourself.

Fermat first mentioned a version of this theorem in a letter in 1640. As with his last theorem, he was a little cryptic about the proof:

"...the proof of which I would send to you, if I were not afraid to be too long."

But unlike with Fermat's last theorem, a proof was published relatively soon; in 1736 by Leonhard Euler.

But does Fermat's little theorem work the other way around? If you have a natural number $n$ so that for all other natural numbers $x$ $x^n - x$ is a multiple of $n,$ does this imply that $n$ is a prime? If this were true, then we could use Fermat's little theorem to check whether a given number $n$ is prime: pick a bunch of other numbers $x$ at random, and for each of them check whether $$x^n - x$$ is a multiple of $n.$ If you find an $x$ for which this isn't true, then you know for sure that $n$ isn't prime. If you don't find one, then provided you have checked sufficiently many $x,$ you can be pretty sure that $n$ is prime. This method is called Fermat's primality test.
Alas, it doesn't quite work as well as it could. In 1885 the Czech mathematician Václav Šimerka discovered non-prime numbers that masquerade as primes when it comes to Fermat's little theorem. The number $561$ is the smallest of them. It's not prime, but for all other natural numbers $x$ we have that $$x^{561} - x$$ is a multiple of $561.$

Šimerka also discovered that $1105, 1729, 2465, 2821, 6601$ and $8911$ behave in the same way. Natural numbers that aren't primes but satisfy the relationship stated in Fermat's little theorem are sometimes called pseudoprimes, because they make such a good job of behaving like primes, or Carmichael numbers, after the American Robert Carmichael, who independently found the first one, 561, in 1910.

You can see from the first seven named above that Carmichael numbers aren't too abundant. There are infinitely many of them, a fact that wasn't proved until 1994, but they are very sparse. In fact, they get sparser as you move up the number line: if you count the Carmichael numbers between 1 and $10^{21}$, you'll find that there are only around one in 50 trillion.

Carmichael numbers do hamper Fermat's primality test somewhat, but not so badly as to make it totally unusable. And there are modified versions of the test that work very well. As cans of worms opened by Fermat go, the one involving Carmichael numbers definitely wasn't the worst.