THE CARMICHAEL FUNCTION the true order, and the numbers that fool Fermat every time
The Carmichael functionλ(n) is the smallest exponent with a^λ(n) ≡ 1 for every a coprime to n — the true group exponent, dividing Euler’s φ(n). Its dark twin: a Carmichael number is a composite n with λ(n) ∣ n-1, so a^(n-1) ≡ 1 for every base — a composite that passes the Fermat test (182) no matter which witness you pick. The reason a single test is never enough.
THE TECHNIQUE lambda = lcm of the prime-power orders
561 = 3×11×17 is the smallest Carmichael number. Its λ = lcm(2,10,16) = 80, and 80 ∣ 560, so a^560 ≡ 1 (mod 561) for every coprime base. Watch Fermat pass for base after base on a composite: live demo
HISTORY & CREDIT Korselt 1899; Carmichael 1910
“Carmichael numbers are rare curiosities that run out.” — no. There are infinitely many (Alford, Granville & Pomerance, 1994), so no Fermat-style test is ever safe on its own — which is exactly why Miller-Rabin (032) checks a stronger condition that Carmichael numbers cannot dodge. cited
1899 · Alwin Korselt — states the criterion (n squarefree and p-1 ∣ n-1 for each prime p ∣ n) — but finds no example. 1910 · Robert Carmichael — finds the first, 561, and studies the function λ(n); the numbers take his name. 1994 · Alford, Granville & Pomerance — prove there are infinitely many.
λ(n) is the exponent of the multiplicative group, φ(n) its order; they differ exactly when the group is not cyclic — and Miller-Rabin exploits the gap the Fermat test cannot see. Korselt 1899 / Carmichael 1910
RECOMMEND FOR I-13 every base fooled, computed
On the canonical compiler, a^560 mod 561 = 1 for multiple bases — the composite 561 passes Fermat every time, and λ=80:
$ i13 run carmichael.i13 # 561 = 3x11x17
2^560 mod 561 = 1 5^560 mod 561 = 1 -- every coprime base passes Fermat
lambda = lcm(2,10,16) = 80 -- and 80 | 560, which is exactly why
Recommend: the Carmichael function is LIT and the honest limit of the Fermat test on I-13 — verified that 561 passes base 2 and base 5 (a^560 ≡ 1) and that λ(561)=lcm(2,10,16)=80 with 80 ∣ 560 — the arithmetic reason every witness fails, computed with gcd/lcm and the bitwise modexp. It is the corpus’s own honesty ethos in number theory: a test that says “probably prime” has a whole infinite family it cannot catch, so you either state the uncertainty or switch to Miller-Rabin’s stronger check (032). Names the exact gap between λ and φ that the stronger test lives in.