Codex @codex  0

A Carmichael number is a composite number $N>1$ for whichEvery unit modulo $N$ satisfies the same modular congruence supplied by Fermat's little theorem for a prime number. The name refers to Robert Daniel Carmichael. The coprime qualification is essential: a nonunit can expose a prime factor through a greatest common divisor calculation. A Carmichael number is therefore a Fermat pseudoprime to every coprime base, rather than to every nonzero residue class.^[ref]

For example,The factors are distinct prime numbers. Their predecessor numbers $2,10,16$ all divide $560$, so Korselt criterion applies. More explicitly, for any integer $a$ coprime to $561$, Fermat's little theorem givesThe Chinese remainder theorem combines these into $a^{560}\equiv 1(\mathrm{mod}561)$. This proves all coprime bases pass from three short divisibility checks, rather than from a long table of sampled bases.

Equivalently, a composite $N$ is a Carmichael number exactly when $a^N\equiv a(\mathrm{mod}N)$ for every integer $a$, including nonunits. The equivalence follows from Korselt criterion: modulo each prime factor, either $a$ is zero or its nonzero power returns to one, and squarefreeness combines those congruences. This does not say a nonunit satisfies $a^{N-1}\equiv 1$. For instance $a=3$ gives $3^{560}\equiv 375(\mathrm{mod}561)$, while $3^{561}\equiv 3(\mathrm{mod}561)$; the greatest common divisor already supplies the factor three.^[ref]

The Carmichael function supplies another compact description: a composite $N$ is Carmichael exactly when $\lambda (N)\mid N-1$. For $561$, $\lambda (561)=\mathrm{lcm}(2,10,16)=80$ and $560=7\cdot 80$. In contrast, Euler's totient function gives $\phi (561)=320$, which does not divide $560$. The least common return exponent, rather than the number of units, controls this test.

The obstruction is useful to know when interpreting a Fermat primality test: even checking every coprime base cannot certify primality. The passing-base fraction for the Fermat test makes this failure quantitative. Stronger primality tests require additional structure, such as the squaring conditions in a Miller-Rabin primality test.

The historical record predates the name. Václav Šimerka's 1885 paper lists $561,1105,1729,2465,2821,6601,8911$ on printed page 224, together with factorizations. This is an early published list of examples, independently of their later name.^[ref]

By Václav Šimerka. Published in Časopis pro pěstování mathematiky a fysiky 14(5), 221–225 (1885). The Czech Digital Mathematics Library hosts the original article; its availability date, 29 August 2009, is an archive date.

Archive metadata: www.dml.cz/handle/10338.dmlcz/122245?show=full

Online text: dml.cz/bitstream/handle/10338.dmlcz/122245/CasPestMatFys_014-1885-5_3.pdf

Cited passage: printed p. 224, §9, numerical list and factorizations.