Números de Carmichael

Son números compuestos que pasan la prueba del PTFermat (en todas las bases). Hay infinitos de ellos. Ejemplo: 561.

Nota:

El PTF dice: si p primo entonces $a^{p-1}=1(mod p)$, para cualquier $a$ primo con $p$. Como se sabe el converso de Fermat es falso, es decir, un número $p$ puede cumplir la condición necesaria de Fermat (de primalidad) y no ser primo, es decir, puede cumplir $a^{p-1}=1(mod p)$ pero ser compuesto.

Y, sin embargo, la condición de Fermat se usa --en el mundo de la criptografía-- para descartar rápidamente los no primos y se le llama "test de pseudoprimalidad". Por ser condición necesaria, si no pasa la prueba con una base entonces no es primo; pero si la pasa, nada se concluye y el número debe ser sometido a otras pruebas de primalidad. Un ejemplo: $341$ pasa la prueba con la base $a=2$, pero no la pasa con $a=3$; por lo tanto $341$ es compuesto. Pero hay números que pasan la prueba en todas las bases; esos son los números de Carmichael.