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:
Escribimos todos los números naturales desde el 2 hasta un cierto
, 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 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
es un número primo, entonces para todo
menor que
que sea primo relativo con el propio
se cumple que:
Es decir, si es primo entonces
es congruente con 1 módulo
. Esto significa que si nosotros tenemos un número
que sabemos que es primo y tomamos un número cualquiera
que no tenga ningún divisor común con
, al dividir el resultado de la operación
entre
el resto es 1 (o equivalentemente: al dividir
entre
el resto es 0).
Vamos con el primer uso del teorema: si tomamos un número y otro
primo relativo con él y el resto de dividir
entre
no es 1, entonces el número
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
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 , que en principio no sabemos si es primo o compuesto. Para aplicar el teorema debemos tomar un número
primo relativo con
. Sea, por ejemplo,
. Tenemos que:
Si dividimos este número entre el resto es 1. ¿Nos dice algo esto? Pues no mucho: simplemente que no podemos descartar que
sea primo. Si seguimos probando con todos los primos relativo con
menores que el propio
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
cumple que para cualquier
primo relativo con él el resto de dividir
entre
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 se denomina pseudoprimo en base
. Por tanto, en el caso anterior al probar con
tendríamos que
es un número pseudoprimo en base
. 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 pasa el test de Fermat para cualquier
menor que
y primo relativo con él. Aunque se ha comentado que eso no nos asegura nada, sabíamos de antemano que
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
para los cuales sea cual sea
menor que
y primo relativo con él se verifica que
, pero no son primos. Vamos, los culpables de que el test de Fermat no sea infalible.
El primer número de Carmichael es el . Es decir,
es divisible por
para cualquier
menor que
y primo relativo con él, pero
no es primo. De hecho,
.
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
es de Carmichael si y sólo si es libre de cuadrados y para todo
factor primo de su descomposición se cumple que
es un divisor de
.
El que hemos nombrado antes cumple las condiciones:
es libre de cuadrados (tiene tres factor primos impares que aparecen en la descomposición sólo una vez).
es un divisor de
.
es un divisor de
.
es un divisor de
.
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 , 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:
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 .
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
Información Bitacoras.com…
Valora en Bitacoras.com: 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…
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$.»
^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!
¿Son infinitos los números de Carmichael?
Saludos
Sí, Toro Sentado: lo podemos leer en la frase que aparece debajo de la ecuación (3) en http://mathworld.wolfram.com/CarmichaelNumber.html
Cierto Mouri, lo cambio ahora mismo. También aprovecho para rectificar el error que comenta Gato.
«congruente con q» dice por ahí, pero ese tal ‘q’ no ha sido presentado. Supongo que es «congruente con 1».
¿No hay ningún número de Carmichael par?
Está comprobado o es que aún no se ha encontrado ninguno.
Ghibertti, no, no los hay. De hecho es sencillo demostrarlo:
Supongamos que
es par. Tomemos
. Se tiene entonces que
es par, por lo que
es impar. Para ser un número de Carmichael ese número debería dar resto cero al dividirlo entre
, pero
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.
Genial este blog. No sé si conoces estos:
http://simplementenumeros.blogspot.com/
http://26veintiseis.blogspot.com/
Os gustarán.
Saludos
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?
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.
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.
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.
Ups, error :(. Doy otra demostración y edito el comentario anterior:
Si
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
. Según el criterio de Korselt, para ser un número de Carmichael debe cumplirse que
sea un divisor de
. Pero eso no puede ser ya que
es par y
es impar.
Gracias por avisar del error J.H.S.
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?
Ya está. No sé por qué salía el comentario en blanco. La cuestión es que ya aparece.
¿Cómo se demuestra que 561 es el primer número de Carmichael?
Interesante avance sobe el tema en http://www.elperiodico.com/es/noticias/sociedad/mensajero-chino-genio-matematicas-formula-identificacion-numeros-carmichael-5286289
Si hablamos de tramas de Terror, pues me encantan todas… Y por estos libros de este fabuloso sitio podríamos empezar… Me gustaron todos.
Lo mejor de estos dias es el Genero de Terror sin duda alguna…