logo

Carmichael Numbers 📂Number Theory

Carmichael Numbers

Definition 1

An integer nn is called a Carmichael number if for all 1an1 \le a \le n, it satisfies ana(modn)a^{n} \equiv a \pmod{n}.

Theorem

Every Carmichael number is a product of distinct primes, except for 22.

Description

Carmichael numbers are composite numbers that pass the Fermat’s Little Theorem, meaning they appear to be prime. For example, 561=31117561=3 \cdot 11 \cdot 17 is a composite number, but a561a(mod561)a^{561} \equiv a \pmod{561} always holds.

Meanwhile, the Miller-Rabin primality test is available to catch such Carmichael numbers.

Proof

Let’s say nn is a Carmichael number.

Part 1. If we set a=n1a = n-1, then because of n11(modn)n-1 \equiv -1 \pmod{n}, we have (n1)n(1)n1(modn) (n-1)^{n} \equiv (-1)^{n} \equiv -1 \pmod{n} The above congruence holds only when nn is odd.

Part 2. Suppose nn is represented by n=p1r1+1pmrm+1n = p_{1}^{r_{1} + 1} \cdots p_{m}^{r_{m} + 1} for primes p1,,pmp_{1}, \cdots , p_{m} excluding 22. Let’s set r:=max{r1,,rm}\displaystyle r : = \max \left\{ r_{1}, \cdots , r_{m} \right\} and show that r=0r=0. Let’s denote the prime corresponding to rr as pp.

Since nn is a Carmichael number, we have prnpr(modn)p^{rn} \equiv p^{r} \pmod{n}, and nn must divide (prnpr)\left( p^{rn} - p^{r} \right). Also, since one of the divisors of nn was pr+1p^{r+1}, pr+1p^{r+1} must divide (prnpr)\left( p^{rn} - p^{r} \right). Thus, prnprpr+1=prnr1p {{ p^{rn} - p^{r} } \over { p^{r+1} }} = {{ p^{rn - r} - 1 } \over { p }} This implies that it is an integer, which is only possible when 00 in the numerator makes r=0r=0.


  1. Silverman. (2012). A Friendly Introduction to Number Theory (4th Edition): p133. ↩︎