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

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.

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.