We saw that Fermat’s little theorem tells us that if is prime and is not divisible by then . Could we use this as a test for primality? Wilson’s theorem gave us a criterion for a number to be prime ( is prime if and only if ), although it doesn’t give us a practical way to test whether a number is prime. Could we get something similar from Fermat’s little theorem?
Well, how might this work? Let’s stick to odd values of (since it’s pretty easy to check whether an even number is prime!). We might hope that if there’s a number (not 1) so that then must be prime. If there is such a number , we say that is a pseudoprime to the base . But does the existence of a base to which is a pseudoprime mean that must be prime?
No. Simple example: , so 15 is a pseudoprime to the base 4 (but certainly isn’t prime).
OK, so that didn’t work. But if is prime then we know that for all numbers coprime to . Suppose we know that is a pseudoprime to all bases with coprime to . Does that mean that is prime?
This seems much more plausible. We try some examples with small values of , and it seems to work. For example, this test would tell us that 15 is not prime, because .
But that’s not a proof…
Unfortunately (perhaps), it turns out that there are composite numbers that are nonetheless pseudoprime to every base. Such numbers are called Carmichael numbers; Carmichael found the first, 561, which is the smallest Carmichael number. So the converse of Fermat’s little theorem is not true.
How could one check that 561 is indeed a Carmichael number? Well, is certainly composite. But there are going to be lots of numbers coprime to 561 where we’d need to check that . Fortunately, one can be more efficient about it than just checking each value in turn.
In fact, there are several useful facts that one can prove about Carmichael numbers. I’m not going to prove them here, but they’re not too difficult so I’ll leave them as exercises! You might want to remember the Fermat-Euler theorem (the generalisation of Fermat’s little theorem to composite numbers).
- If is a Carmichael number then it is not divisible by the square of any prime.
- If is a Carmichael number and is a prime divisor of , then divides .
- If is a Carmichael number then it is not the product of two distinct primes.
- If is the product of at least three distinct odd primes, and divides for each prime dividing , then is a Carmichael number.
We can then use this to check that 561 is a Carmichael number. You might be amused to learn that 1729 is the third Carmichael number, although it is more famous for other reasons.
Does this mean that we can’t use this approach to check whether a number is prime? Well, perhaps there aren’t very many Carmichael numbers. If there were only finitely many, perhaps we could just write them in a big list, and then all we’d need to do is check whether is a pseudoprime to every base coprime to , and then check whether is on our list. If it passes the test, and isn’t a Carmichael number, then it’s prime.
This does not really come as a huge blow, because this would have been a very inefficient way to try to check whether a number is prime anyway! But the idea of a pseudoprime can be used in primality testing, using a probabilistic approach. You can read about this (and find links to more sophisticated but related ideas) on the Wikipedia page. Of course, there are also Wikipedia pages about Carmichael numbers and pseudoprimes. There’s also a nice book by Koblitz (A course in number theory and cryptography) that discusses these ideas (including the proofs of those facts I mentioned above).