Suppose you have a prime number and some other natural number . Then, no matter what the value of is, as long as it’s a natural number, you will find that
is a multiple of
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 and we have
For and we have
And for and we have
You can try it out for other values of and 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 so that for all other natural numbers
is a multiple of does this imply that is a prime?
If this were true, then we could use Fermat’s little theorem to check whether a given number is prime: pick a bunch of other numbers at random, and for each of them check whether
is a multiple of If you find an for which this isn’t true, then you know for sure that isn’t prime. If you don’t find one, then provided you have checked sufficiently many you can be pretty sure that 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 is the smallest of them. It’s not prime, but for all other natural numbers we have that
is a multiple of
Šimerka also discovered that and 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 , 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.