Theorem 28: there are infinitely many Carmichael numbers

This week’s theorem follows from my previous posts on Fermat’s little theorem and (to a lesser extent) Wilson’s theorem.

We saw that Fermat’s little theorem tells us that if $p$ is prime and $a$ is not divisible by $p$ then $a^{p-1} \equiv 1 \mod{p}$ . Could we use this as a test for primality? Wilson’s theorem gave us a criterion for a number to be prime ( $n$ is prime if and only if $(n-1)! \equiv -1 \mod{n}$ ), 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 $n$ (since it’s pretty easy to check whether an even number is prime!). We might hope that if there’s a number $b$ (not 1) so that $b^{n-1}\equiv 1 \mod{n}$ then $n$ must be prime. If there is such a number $b$ , we say that $n$ is a pseudoprime to the base $b$ . But does the existence of a base to which $n$ is a pseudoprime mean that $n$ must be prime?

No. Simple example: $4^{14} \equiv (4^2)^7 \equiv 1 \mod{15}$ , so 15 is a pseudoprime to the base 4 (but certainly isn’t prime).

OK, so that didn’t work. But if $p$ is prime then we know that $a^{p-1} \equiv 1 \mod{p}$ for all numbers $a$ coprime to $p$ . Suppose we know that $n$ is a pseudoprime to all bases $b$ with $b$ coprime to $n$ . Does that mean that $n$ is prime?

This seems much more plausible. We try some examples with small values of $n$ , and it seems to work. For example, this test would tell us that 15 is not prime, because $2^{14} \equiv 4^7 \equiv (4^2)^3 \times 4 \equiv 4 \mod{15}$ .

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, $561 = 3 \times 11 \times 17$ is certainly composite. But there are going to be lots of numbers $b$ coprime to 561 where we’d need to check that $b^{560} \equiv 1\mod{561}$ . 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 $n$ is a Carmichael number then it is not divisible by the square of any prime.
If $n$ is a Carmichael number and $p$ is a prime divisor of $n$ , then $p-1$ divides $n-1$ .
If $n$ is a Carmichael number then it is not the product of two distinct primes.
If $n$ is the product of at least three distinct odd primes, and $p-1$ divides $n-1$ for each prime $p$ dividing $n$ , then $n$ 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 $n$ is a pseudoprime to every base coprime to $n$ , and then check whether $n$ is on our list. If it passes the test, and isn’t a Carmichael number, then it’s prime.

But…

Theorem (Alford, Granville, Pomerance) There are infinitely many Carmichael numbers.

You can find the paper here (it appeared in the Annals of Mathematics in 1994); if you have access to MathSciNet you can read a review by Hugh Montgomery here (in which he outlines the approach).

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).

This entry was posted on June 3, 2010 at 11:37 am and is filed under Cambridge Maths Tripos, IA Numbers & Sets, II Number Theory, Theorem. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

2 Responses to “Theorem 28: there are infinitely many Carmichael numbers”

Luana Says:
September 22, 2011 at 3:44 pm
Good! =)
Theorem 39: Euler’s criterion « Theorem of the week Says:
February 4, 2012 at 9:32 pm
[…] test. This is very different from the situation for Fermat pseudoprimes, where there are Carmichael numbers (numbers that cannot be distinguished from primes just using this notion of a […]

Enter your comment here...

Fill in your details below or click an icon to log in:

Email (required) (Address never made public)

Name (required)

Website

You are commenting using your WordPress.com account. ( Log Out / Change )

You are commenting using your Facebook account. ( Log Out / Change )

Cancel

Connecting to %s

Theorem of the week

Theorem 28: there are infinitely many Carmichael numbers

Share this:

Like this:

Related

2 Responses to “Theorem 28: there are infinitely many Carmichael numbers”

Leave a Reply