= Carmichael number
{c}
{title2=$a^{N-1}\equiv1\pmod N$}
{wiki}
A Carmichael number is a <composite number> $N>1$ for which
$$
a^{N-1}\equiv1\pmod N\qquad\text{whenever }\gcd(a,N)=1.
$$
Every <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>.<Carmichael Numbers and Korselt's Criterion by Keith Conrad>[Definition 1, printed p. 1: composite input and coprime bases]{ref}
For example,
$$
\boxed{561=3\cdot11\cdot17\text{ is a Carmichael number}.}
$$
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> gives
$$
a^{560}\equiv1\pmod3,\qquad a^{560}\equiv1\pmod{11},\qquad a^{560}\equiv1\pmod{17}.
$$
The <Chinese remainder theorem> combines these into $a^{560}\equiv1\pmod{561}$. This proves all coprime bases pass from three short divisibility checks, rather than from a long table of sampled bases.
\Image[/carmichael-prime-factor-exponent-certificate.png]
{title=Three <prime factors> certify that every <unit> passes the Fermat congruence modulo 561}
{description=Original arithmetic certificate for $561=3\cdot11\cdot17$. Exponents $2,10,16$ divide $560$ with quotients $280,56,35$; the <Chinese remainder theorem> combines the three prime-modulus conclusions.}
Equivalently, a composite $N$ is a <Carmichael number> exactly when $a^N\equiv a\pmod 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}\equiv1$. For instance $a=3$ gives $3^{560}\equiv375\pmod{561}$, while $3^{561}\equiv3\pmod{561}$; the <greatest common divisor> already supplies the factor three.<Carmichael Numbers and Korselt's Criterion by Keith Conrad>[Corollary 4 and proof, printed p. 3]{ref}
The <Carmichael function> supplies another compact description: a composite $N$ is Carmichael exactly when $\lambda(N)\mid N-1$. For $561$, $\lambda(561)=\operatorname{lcm}(2,10,16)=80$ and $560=7\cdot80$. In contrast, <Euler's totient function> gives $\varphi(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>: \b[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.<Zbytky z arithmetické posloupnosti by Václav Šimerka>[Zbytky z arithmetické posloupnosti, printed p. 224, §9: list beginning with 561 and 1105; archive title sheet identifies Václav Šimerka and 1885]{ref}
Back to article page
