📂Number Theory

Carmichael Numbers

Definition ¹

An integer $n$ is called a Carmichael number if for all $1 \le a \le n$, it satisfies $a^{n} \equiv a \pmod{n}$.

Theorem

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

Description

Carmichael numbers are composite numbers that pass the Fermat’s Little Theorem, meaning they appear to be prime. For example, $561=3 \cdot 11 \cdot 17$ is a composite number, but $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 $n$ is a Carmichael number.

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

Part 2. Suppose $n$ is represented by $n = p_{1}^{r_{1} + 1} \cdots p_{m}^{r_{m} + 1}$ for primes $p_{1}, \cdots , p_{m}$ excluding $2$. Let’s set $\displaystyle r : = \max \left\{ r_{1}, \cdots , r_{m} \right\}$ and show that $r=0$. Let’s denote the prime corresponding to $r$ as $p$.

Since $n$ is a Carmichael number, we have $p^{rn} \equiv p^{r} \pmod{n}$, and $n$ must divide $\left( p^{rn} - p^{r} \right)$. Also, since one of the divisors of $n$ was $p^{r+1}$, $p^{r+1}$ must divide $\left( p^{rn} - p^{r} \right)$. Thus, $$ {{ 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 $0$ in the numerator makes $r=0$.

■