Carmichael numbers¶

A Carmichael number is a composite \(n\) such that

\[ a^{n-1} \equiv 1 \pmod{n} \]

for every integer \(a\) coprime to \(n\). They are absolute Fermat pseudoprimes, so they defeat the naive Fermat primality test. [Prime Pages (UTM), 2025, Wikipedia contributors, 2025]

Key facts¶

Korselt’s criterion (1899): \(n\) is Carmichael iff (i) \(n\) is squarefree and (ii) for every prime \(p\mid n\), we have \((p-1)\mid (n-1)\). [Conrad, 2004, Wikipedia contributors, 2025]
At least three prime factors: No Carmichael number is the product of only two primes. [Wikipedia contributors, 2025]
Infinitely many: Alford–Granville–Pomerance proved there are infinitely many Carmichael numbers. [Alford et al., 1994]
Historical origin: Carmichael studied these numbers in the early 20th century. [Carmichael, 1912]

Counterexample search: Find Carmichael numbers by generating squarefree products and testing Korselt’s criterion.
“Fermat test is not enough”: Show that all bases \(a\) with \(\gcd(a,n)=1\) pass Fermat for a Carmichael \(n\), while a Miller–Rabin test quickly finds witnesses.
Distribution experiments: Count Carmichael numbers up to \(X\) and compare growth to simple heuristics.
Construction families: Implement Chernick-style constructions and see when factors are prime.

See Alford et al. [1994], Conrad [2004], The OEIS Foundation Inc. [2025], Wikipedia contributors [2025].