Número de Carmichael

En teoría de números, los números de Carmichael son los números compuestos n que satisfacen la congruencia

$a^{n-1}\equiv 1{\pmod {n}}$ para todo entero $\ a$ primo relativo con $\ n$.

Los números de Carmichael reciben su nombre por el matemático Robert Daniel Carmichael que los estudió.

Relevancia

El Teorema de Fermat establece que si p es un número primo, entonces la congruencia

$a^{p-1}\equiv 1{\pmod {p}}$

es válida para cualquier número $\ a$ no divisible por $\ p$.

Dicho de otra manera, si a no es divisible por p entonces p divide a a^p-1-1:

$\ p|a^{p-1}-1$.

Para determinar si un número n es primo o no, se escoge un número a que sea primo relativo con n y se calcula $\ a^{n-1}{\pmod {n}}$. Si el resultado es diferente a 1, el número es compuesto con toda certeza.

Desafortunadamente si el resultado es 1 no es posible asegurar a ciencia cierta que el número n es primo, ya que el inverso del teorema de Fermat no es válido: existen números compuestos a tales que $a^{n-1}\equiv 1{\pmod {n}}$. Estos números se denominan pseudoprimos en la base a, por lo que la prueba propuesta no es en realidad una verdadera prueba de primalidad.

Los números de Carmichael son entonces números pseudoprimos en cualquier base: son los números para los que la prueba anterior falla para cualquier elección de base que sea primo relativo con el número dado.

Ejemplos

Los primeros números de Carmichael son

$561,1105,1729,2465,2821,6601,8911,10585,15841,29341,41041,46657,52633,62745,63973,75361\ldots$

El primer número de Carmichael es

$n=561=3\times 11\times 17$,

por lo que no es primo. Sin embargo

$\ a^{560}-1$ es divisible por 561 para cualquier $\ a$ coprimo con 561.

Véase también

• Pseudoprimo
• Introducción a la Matemática Discreta (Universidad de Sevilla)

Referencias

• Carmichael, R. D. (1912) On composite numbers P which satisfy the Fermat congruence $a^{P-1}\equiv 1{\bmod {P}}$. Am. Math. Month. 19 22–27.
• Erdős, Paul (1956). On pseudoprimes and Carmichael numbers, Publ. Math. Debrecen 4, 201 –206.
• Alford, Granville and Pomerance (1994). There are infinitely many Carmichael numbers, Ann. of Math. 140(3), 703–722.

Enlaces externos

• Hazewinkel, Michiel, ed. (2001), «Número de Carmichael», Encyclopaedia of Mathematics (en inglés), Springer, ISBN 978-1556080104 .
• Weisstein, Eric W. «Carmichael Number». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 

• Datos: Q849530