## Maths in a minute: Pretend primes

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.