Un entero compuesto n tal que para todo entero a coprimo con n se cumple a^{n−1} ≡ 1 (mod n); por tanto n se comporta como primo en la congruencia de Fermat para todas las bases coprimas con él.

Principio

Reúne los módulos compuestos que pasan la prueba de primalidad de Fermat para cualquier base coprima; se caracteriza equivalemente por condiciones tipo Korselt (sin cuadrados y cada primo divisor p satisface p−1 | n−1).

Demostración

El ejemplo más pequeño es 561 = 3·11·17; para cualquier a coprimo con 561 se tiene a^{560} ≡ 1 (mod 561), por lo que 561 es un número de Carmichael y engañaría consistentemente una prueba de Fermat simple.

Aplicación incorrecta

Referirse a cualquier pseudoprimo de Fermat (que puede satisfacer la congruencia para algunas bases pero no para todas) como Carmichael, o suponer que un número que verifica la congruencia para varias bases pequeñas es Carmichael sin comprobar todas las bases coprimas.

Consecuencia

Demuestra las limitaciones de las pruebas de primalidad ingenuas: la existencia de números de Carmichael obliga a usar pruebas deterministas o probabilísticas más fuertes; su distribución afecta la fiabilidad de las pruebas basadas en bases fijas.

Inversión

Los primos son la inversión: satisfacen la misma congruencia pero son genuinamente primos; otra inversión son compuestos que fallan la congruencia para algunas bases coprimas y por tanto son fácilmente distinguidos por pruebas de Fermat.

Límite

Se define solo para enteros compuestos; exige que la congruencia se cumpla para todo entero coprimo con n. Excluye pseudoprimos de Fermat que verifican la congruencia sólo para un subconjunto de bases y excluye los primos.

Tensión semántica

En tensión con nociones como pseudoprimo de Fermat, pseudoprimo de Euler y pseudoprimo fuerte; la tensión está entre el engaño universal respecto a todas las bases (Carmichael) y el engaño respecto a bases particulares (pseudoprimos).

Síntesis

Un número de Carmichael es un entero compuesto y sin cuadrados cuya estructura multiplicativa fuerza la congruencia de Fermat para toda base coprima: un pseudoprimo universal que revela los límites de las pruebas de primalidad sencillas.