Carmichael Number — Definition, Formula & Examples

A Carmichael number is a composite (non-prime) number that behaves like a prime in Fermat's Little Theorem — it satisfies

a^n \equiv a \pmod{n}

for every integer

a

, even though it is not actually prime.

A composite positive integer $n$ is a Carmichael number if and only if $a^n \equiv a \pmod{n}$ for all integers $a$ . Equivalently, by Korselt's criterion, $n$ is a Carmichael number if and only if $n$ is square-free and, for every prime $p$ dividing $n$ , the quantity $(p - 1)$ divides $(n - 1)$ .

Key Formula

a^n \equiv a \pmod{n} \quad \text{for all integers } a

Where:

$n$ = A composite positive integer (the candidate Carmichael number)
$a$ = Any integer

How It Works

Fermat's Little Theorem says that if

p

is prime, then

a^p \equiv a \pmod{p}

for every integer

a

. This fact is used as a quick test: if a number fails this condition for some

a

, it cannot be prime. Carmichael numbers are the "impostors" — composite numbers that pass this test for every base

a

. To verify that a number is Carmichael, you can use Korselt's criterion: factor the number, confirm it is square-free, and check that

(p-1)

divides

(n-1)

for each prime factor

p

Worked Example

Problem: Verify that 561 is a Carmichael number using Korselt's criterion.

Factor 561: Find the prime factorization of 561.

561 = 3 \times 11 \times 17

Check square-free: No prime factor is repeated, so 561 is square-free.

Check divisibility condition: Compute

n - 1 = 560

. For each prime factor

p

, verify

(p-1) \mid 560

560 \div 2 = 280 \checkmark, \quad 560 \div 10 = 56 \checkmark, \quad 560 \div 16 = 35 \checkmark

Answer: Since 561 is composite, square-free, and

(p-1)

divides 560 for each prime factor

p \in \{3, 11, 17\}

, the number 561 is a Carmichael number — the smallest one, in fact.

Why It Matters

Carmichael numbers reveal a fundamental limitation of Fermat's primality test, which is why modern cryptographic systems like RSA rely on stronger tests such as Miller-Rabin. Understanding these "pseudoprimes" is essential in any course covering computational number theory or cryptography.

Common Mistakes

Mistake: Assuming Fermat's Little Theorem can definitively prove a number is prime.

Correction: Passing the Fermat test for all bases only means the number is either prime or a Carmichael number. Carmichael numbers are composite yet satisfy the test, so a different primality test is needed for certainty.