Los números de Carmichael

La aventura de buscar qué números enteros positivos son primos es tan antigua como las propias matemáticas. Desde siempre los números primos han fascinado a los matemáticos. Los números primos, los átomos a partir de los cuales se pueden obtener todos los números naturales. Para no fascinar al personal.

Esto conlleva que desde siempre se hayan intentado desarrollar métodos para la búsqueda de los números primos. Quizás el más antiguo de los que se conocen sea la Criba de Eratóstenes, que consiste en lo siguiente:

Criba de EratóstenesEscribimos todos los números naturales desde el 2 hasta un cierto n, por ejemplo hasta 120 (como aparece en la figura, tomada de la Wikipedia en español). Nos quedamos con el 2, que es primo, y tachamos todos los múltiplos de 2. Nos quedamos con el siguiente número no tachado, que en este caso es el 3, y lo declaramos como primo, tachando después todos los múltiplos de 3. Seguimos de esta forma, quedándonos con el primer número no tachado como primo y tachando sus múltiplos. Conseguimos así descartar todos los compuestos y localizar todos los primos.

Interesante método, pero con un gran inconveniente: el proceso es larguísimo si n es muy grande. Por ello no serviría para localizar primos grandes, ya que costaría demasiado aplicar el método hasta el final. Imaginaos que quisiéramos determinar si un número de ocho cifras es primo…las dimensiones del cuadro y el tiempo que tardaríamos en terminar no son ni mucho menos asumibles.

Por suerte tenemos más métodos. Voy a comentar en este artículo uno de ellos que aunque no es ni mucho menos infalible sí que es interesante. Además nos va a servir de ayuda para introducir los números que titulan la entrada.

El método en cuestión es el llamado test de primalidad de Fermat. Dicho test utiliza el pequeño teorema de Fermat para descartar que cierto número sea primo o para alcanzar cierta certeza de que un número es primo, según el caso.

Comencemos recordando el pequeño teorema de Fermat (una versión equivalente al original):

Si p es un número primo, entonces para todo a menor que p que sea primo relativo con el propio p se cumple que:

a^{p-1} \equiv 1 \; (mod \; p)

Es decir, si p es primo entonces a^{p-1} es congruente con 1 módulo p. Esto significa que si nosotros tenemos un número p que sabemos que es primo y tomamos un número cualquiera a que no tenga ningún divisor común con p, al dividir el resultado de la operación a^{p-1} entre p el resto es 1 (o equivalentemente: al dividir a^{p-1}-1 entre p el resto es 0).

Vamos con el primer uso del teorema: si tomamos un número n y otro a primo relativo con él y el resto de dividir a^{n-1} entre n no es 1, entonces el número n es compuesto. Es sencillo darse cuenta de esto simplemente tomando el contrarrecíproco del teorema: si la congruencia no se cumple, entonces el número n no es primo, por lo que necesariamente debe ser compuesto.

El segundo uso que se le puede dar a este teorema es el que más nos interesa. Imaginemos que tomamos un número, por ejemplo p=11, que en principio no sabemos si es primo o compuesto. Para aplicar el teorema debemos tomar un número a primo relativo con 11. Sea, por ejemplo, a=4. Tenemos que:

a^{p-1}=4^{11-1}=1048576

Si dividimos este número entre 11 el resto es 1. ¿Nos dice algo esto? Pues no mucho: simplemente que no podemos descartar que 11 sea primo. Si seguimos probando con todos los primos relativo con 11 menores que el propio 11 obtenemos siempre resto 1 al realizar las operaciones anteriores. Al pasar con todos, ¿podemos asegurar algo? Pues por desgracia tampoco. La razón es muy sencilla: todo número primo p cumple que para cualquier a primo relativo con él el resto de dividir a^{p-1} entre p es 1 (es lo que dice el pequeño teorema de Fermat), pero también hay número compuesto que tienen la misma propiedad. Por ello el hecho de que un número cualquiera pase el test de Fermat no nos asegura que el propio número sea primo.

Vamos a poner nombre a las cosas: un número que pase el test de Fermat para un cierto a se denomina pseudoprimo en base a. Por tanto, en el caso anterior al probar con a=4 tendríamos que 11 es un número pseudoprimo en base 4. La denominación pseudoprimo se debe a que el número cumple una propiedad que también cumplen todos los números primos, pero no podemos asegurar que él también lo sea.

Pero continuando con la prueba hemos dicho que 11 pasa el test de Fermat para cualquier a menor que 11 y primo relativo con él. Aunque se ha comentado que eso no nos asegura nada, sabíamos de antemano que 11 es primo. Podría ser que los únicos números que pasan el test de Fermat en cualquier base fueran los números primos…pero no es así. Los números naturales que pasan el test de Fermat en cualquier base pero resultan ser compuesto son los denominados números de Carmichael (también se les llama pseudoprimos absolutos). Es decir, son números n para los cuales sea cual sea a menor que n y primo relativo con él se verifica que a^{n-1} \equiv 1 \; (mod \; n), pero no son primos. Vamos, los culpables de que el test de Fermat no sea infalible.

El primer número de Carmichael es el 561. Es decir, a^{560}-1 es divisible por 561 para cualquier a menor que 561 y primo relativo con él, pero 561 no es primo. De hecho, 561=3 \cdot 11 \cdot 17.

Hay un teorema, debido a Korselt, que da condiciones para determinar si un número es de Carmichael. Dicho resultado es el siguiente:

Teorema: Un número natural n es de Carmichael si y sólo si es libre de cuadrados y para todo k factor primo de su descomposición se cumple que k-1 es un divisor de n-1.

El 561 que hemos nombrado antes cumple las condiciones:

  • 561 es libre de cuadrados (tiene tres factor primos impares que aparecen en la descomposición sólo una vez).
  • 3-1 es un divisor de 561-1.
  • 11-1 es un divisor de 561-1.
  • 17-1 es un divisor de 561-1.

Un detalle curioso: el teorema anterior de Korselt es anterior a la denominación de estos números (aunque en su enunciado se ha incluido dicha denominación). El propio Korselt estuvo buscando un ejemplo, pero no lo encontró. Fue el matemático estadounidense Robert Carmichael quien encontró el primer ejemplo, el citado 561, unos años después de la aparición del teorema. A partir de aquí estos números adquirieron el apellido de Carmichael como identificación.

¿Estos números? Sí, claro, hay más, aunque no demasiados. Los primeros son los siguientes:

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

Estos son todos los que tienen tres factores primos (que es el mínimo que debe tener un número para ser de Carmichael). En este enlace podéis ver una tabla bastante más extensa.

Para finalizar comentar que los números de Carmichael pueden generalizarse a los llamados números de Knödel. De hecho los números de Carmichael son los números de Knödel k_1.

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

18 Comentarios

  1. Como siempre que se habla de números primos la entrada es interesante.
    Por otro lado tienes un pequeño fallo de escritura cuando explicas que 561 es un número de Carmichael; creo que has escrito mal alguna letra en una fórmula de latex: “17-1 es un divisor de $latez 561-1$.”

    Publica una respuesta
  2. ^DiAmOnD^, un comentario sobre este post: en muchos sitios dices cosas como
    “Para aplicar el teorema debemos tomar un número a primo relativo con 11. Sea, por ejemplo, a=4. Tenemos que:

    a^{p-1}=4^{11-1}=1048576

    Si dividimos este número entre 11 el resultado es 1.”
    Pero esto no es así, la frase correcta seria: Si dividimos este número entre 11 el resto de la división es 1.
    ¿No es así?
    ¡El post genial!

    Publica una respuesta
  3. “congruente con q” dice por ahí, pero ese tal ‘q’ no ha sido presentado. Supongo que es “congruente con 1”.

    Publica una respuesta
  4. Ghibertti, no, no los hay. De hecho es sencillo demostrarlo:

    Supongamos que p es par. Tomemos a=2. Se tiene entonces que 2^{p-1} es par, por lo que 2^{p-1}-1 es impar. Para ser un número de Carmichael ese número debería dar resto cero al dividirlo entre p, pero p es par, y sabemos una división de un número impar entre un número par no puede dar resto cero.

    Por ello el test de Fermat acierta con todo número par, por lo que ninguno de ellos es un número de Carmichael.

    DEMOSTRACIÓN EN ESTE COMENTARIO.

    Hernan, gracias por comentarme el error. Lo cambio ahora mismo.

    Publica una respuesta
  5. Tengo una duda.
    Supongamos que encuentro un numero entero positivo m, donde (p-1), (q-1), (r-1),(s-1),… dividen a (m-1) con p,q,r,s,… divisore primos de m.
    Puedo deducir en consecuencia que m es un nùmero de carmichael? ò es necesario aplicar la prueba de fermat?
    Diho de otra manera,es vàlido el recìproco del teorema de los nùmeros de Carmichael que aparece en este post?

    Publica una respuesta
  6. Según el teorema, si encuentras un número con esa propiedad que además sea libre de cuadrados entonces tienes en tus manos un número de Carmichael.

    Publica una respuesta
  7. Maravilloso post. Robert Daniel Carmichael fue autor de varios libros de matemática y física. Uno que particularmente me agrado es “Diophantine Analysis”, donde analiza varios tipos de ecuaciones diofánticas, y que se puede descagar aquí: http://www.gutenberg.org/etext/20073.

    Publica una respuesta
  8. En tu prueba de que no hay números pares que sean de Carmichael… ¿No deberías tomar a coprimo con p para que el argumento funcione?

    Respetuosamente,

    J. H. S.

    Publica una respuesta
  9. Ups, error :(. Doy otra demostración y edito el comentario anterior:

    Si n es un número par compuesto y libre de cuadrados, debe tener al menos un factor primo impar (ya que el 2 sólo puede aparecer una vez), digamos p. Según el criterio de Korselt, para ser un número de Carmichael debe cumplirse que p-1 sea un divisor de n-1. Pero eso no puede ser ya que p-1 es par y n-1 es impar.

    Gracias por avisar del error J.H.S.

    Publica una respuesta
  10. Ya me llegó la nueva demostración al correo, DiAmOnD. Sin embargo, no la veo en la página. ¿Es un problema de mi navegador?

    Publica una respuesta
  11. ¿Cómo se demuestra que 561 es el primer número de Carmichael?

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - Información Bitacoras.com... Valora en Bitacoras.com: La aventura de buscar qué números enteros positivos son primos es tan antigua como…

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *