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.

Print Friendly, PDF & Email
5 1 vote
Article Rating

¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉


Comparte: