Hola
El pequeño Teorema de Fermat en una de sus formulaciones dice. Si p es primo y 1<a<p, entonces:
\( a^p\equiv a \) (mod p).
Uno podría pensar si es cierto el recíproco, ¿todo número p verficando que para 1<a<p,
\( a^p\equiv a \) (mod p).
es primo?.
Esto es FALSO en general, y a los números verificando esta propiedad, pero que no son primos, se les llama números de Carmichael.
Ahora sea n un número de Carmichael, sea p un factor primo de n. Entonces:
\( p^n\equiv p \) (mod n)
o equivalentemente:
\( p(p^{n-1}-1)=kn \)
Si \( p^d \) divide a n, con d>1 entonces \( p^d \) debería de dividir a \( p(p^{n-1}-1), \) pero eso es falso.
Una caracterización más completa de los número de Carmichael, viene dada por el criterio de Korselt. Puedes verlo con una prueba aquí:
http://www.mat.ufmg.br/~elaine/OBMEP/criptografia.pdfSaludos.