What are Carmichael numbers / absolute pseudoprimes?

Posted on by

Fermat’s little theorem states that if p is a prime number, then

\begin{aligned} a^p \equiv a \ (\textrm{mod} \ p) \quad \text{for all integers } a. \end{aligned}

Fermat’s little theorem is not a foolproof test for primality: there are composite numbers n for which a^n \equiv a \ (\textrm{mod}\ n) for some integer a. If a^n \equiv a \ (\textrm{mod}\ n) for a given value of a, n is said to be a (Fermat) pseudoprime to base a. For example, the smallest pseudoprime to base 2 is 341.

Despite the presence of these pseudoprimes, the condition in Fermat’s little theorem is still a widely used test for primality since (i) pseudoprimes to a particular base are pretty rare, and (ii) even if a number is a pseudoprime for some base a, it might not be a pseudoprime for another base b. (Click here for a list of pseudoprimes to different bases.)

The question remains: are there numbers which satisfy the condition of Fermat’s little theorem for all integers a, but yet are not prime? (In other words, is the converse of Fermat’s little theorem true?) It turns out that the converse is not true: there are composite numbers n for which a^n \equiv a \ (\textrm{mod}\ n) for all integers a. These numbers are called Carmichael numbers (or absolute pseudoprimes).

The smallest Carmichael number is 561. I always thought that the proof for this was complicated, but it turns out to be pretty elementary! The proof below is from Reference 1 and hinges on the identity a^k - 1 = (a-1)(a^{k-1} + a^{k-2} + \dots + 1). Since 561 = 3 \cdot 11 \cdot 17, we need to show that a^{561} - a is divisible by 3, 11 and 17. (These together would imply that a^{561} - a is divisible by 561.)

\begin{aligned} a^{561} - a &= a [(a^2)^{280} - 1^{280}] \\ &= a(a^2 - 1) (\dots) \\ &= (a^3 - a) (\dots) \\ &\equiv 0 \qquad  (\textrm{mod}\ 3), \end{aligned}

where the last implication is due to applying Fermat’s little theorem with p = 3. Similarly,

\begin{aligned} a^{561} - a &= a [(a^{10})^{56} - 1^{56}] = a(a^{10} - 1) (\dots) = (a^{11} - a) (\dots) \\ &\equiv 0 \qquad  (\textrm{mod}\ 11), \\ a^{561} - a &= a [(a^{16})^{35} - 1^{35}] = a(a^{16} - 1)(\dots) = (a^{17} - a) (\dots) \\ &\equiv 0 \qquad  (\textrm{mod}\ 17).  \end{aligned}

At the time when Reference 1 was published (1974), it was not known whether there are an infinite number of Carmichael numbers. In 1994, Alford et. al. (Reference 2) proved that there are infinitely many Carmichael numbers.

References:

  1. Honsberger, R. (1974). Mathematical Gems I.
  2. Alford, W. R., Granville, A., and Pomerance, C. (1994). There are infinitely many Carmichael numbers.

Leave a comment