El método más conocido para encontrar números primos es la criba de Eratóstenes. Es un algoritmo que permite hallar todos los primos menores o iguales que un número natural dado; lo propuso el matemático griego Eratóstenes alrededor del año 200 a.C.
Que los números primos son infinitos estaba demostrado con rigor desde, al menos, un siglo antes, pues es una de las proposiciones del libro 9 de los Elementos de Euclides. Estas cosas se estudian en la escuela, y si alguno las ha olvidado podrá localizarlas fácilmente, bien en internet o en muchísimos textos (por ejemplo, en el primer tema de Recorridos por la teoría de numeros, de Electolibris y la Real Sociedad Matemática Española: el lector observará que, con la excusa, me las he ingeniado para citar «mi libro»).
Así comienza una nueva colaboración de un matemático español para Gaussianos. En este caso se trata de Juan Luis Varona, Catedrático de Universidad en el Departamento de Matemáticas y Computación de la Universidad de La Rioja. Juan Luis se licenció en Matemáticas en la Universidad de Zaragoza en 1985 y defendió su tesis doctoral en la Universidad de Cantabria en 1988. Tiene una amplia experiencia docente en Análisis Matemático, Ecuaciones Diferenciales, Métodos Numéricos y Teoría de Números, así como en los lenguajes de programación habituales en Matemáticas. Ha publicado más de 50 artículos de investigación sobre Análisis Armónico, Análisis Numérico y Teoría de Números y ha participado en diversos proyectos de investigación financiados por el Gobierno Español. Además, es director de La Gaceta de la Real Sociedad Matemática Española.
Juan Luis nos habla en esta entrada de un artículo que Javier Díaz Aspe envió a La Gaceta de la RSME (y que, por cierto, fue publicado en dicho medio). Muchas gracias a los dos por la predisposición a colaborar con Gaussianos.
Sin más dilación, os dejo con esta búsqueda de primos con una cuerda. Espero que esta entrada os guste tanto como me ha gustado a mí.
Realmente, hay bastantes métodos de ver si un número natural es o no primo, así como de encontrar descomposiciones en factores, y no todos ellos son elementales sino que, por el contrario, pueden ser bastante sofisticados, tanto en las matemáticas que se usan para aplicarlos como en las que se necesitan para explicar por qué funcionan (quizás la criba de la parábola sea uno de ésos que sorprenden tanto visualmente como por estar al alcance de cualquiera). Por si acaso, conviene aclarar que existen procedimientos para analizar si un número es o no primo (tests de primalidad) sin que sea preciso buscar un factor que lo divida; en general, factorizar un número puede ser bastante más complicado que estudiar su primalidad. De hecho, este tipo de métodos son los que se aplican en la práctica para encontrar primos de los que actualmente se usan en criptografía, que pueden tener varios centenares de cifras.
Hace unos meses, Javier Díaz Aspe envió a La Gaceta de la Real Sociedad Matemática Española (revista de la que soy uno de sus directores) un precioso método para detectar si un número impar es o no primo con ayuda de una cuerda con nudos. Sólo necesita matemáticas elementales y, además, cuando un número no es primo, permite encontrar sus factores. En lo que sigue, lo explicaré de manera bastante literal a como lo publicamos en Cómo detectar primos usando una cuerda con nudos (La Gaceta de la RSME 22 , 2019, pág. 80), aunque con más detalles.
Sea un número natural impar. Se toma una cuerda suficientemente larga. A una distancia arbitraria del origen marcaremos un punto (o haremos un nudo); a esta distancia la llamaremos distancia o espacio unidad. A continuación marcamos un nuevo punto a una distancia igual a tres espacios unidad. Y así procederemos sucesivamente añadiendo y marcando tramos de una longitud igual a la precedente más dos espacios unidad hasta añadir un tramo de longitud
.
A partir de este punto se dobla la cuerda 180 grados y se siguen añadiendo y marcando tramos de una longitud igual al tramo precedente menos dos espacios unidad (es decir, , seguido de
, etc.) hasta añadir un espacio igual a un espacio unidad.
Si no hubiese ninguna marca del primer tramo de la cuerda coincidente con una marca del segundo tramo de la misma, el número es primo. Si hubiese alguna marca del primer tramo coincidente con una marca del segundo tramo, el número
es compuesto.
Como ejemplo presentamos los números , primo, y
, compuesto. Se ve que en el número
no hay ninguna marca que coincida, por lo que el método nos confirma que
es primo:
Mientras tanto, en el caso del hay dos marcas que coinciden (destacadas en rojo). Por tanto, el método nos asegura que
es compuesto:
Justificación del método
Vamos a ver por qué funciona el método antes descrito. Como es un número natural impar, pongamos
, con
.
Dos marcas coinciden si y sólo si existen enteros , necesariamente
y
, tales que
Esas dos cantidades representan, respectivamente, las longitudes del primer y segundo tramo de la cuerda desde la coincidencia hasta el doblez; así mismo, y
son, respectivamente, el número de trozos de cuerda desde el principio hasta la coincidencia y desde la coincidencia hasta el final.
En el ejemplo correspondiente a , lo que tenemos es
,
y
, y los sumandos de los términos derecho e izquierdo de
se corresponden con las longitudes de los trozos de cuerda abarcados por las llaves
y
, respectivamente:
Volviendo a la justificación del método, se puede escribir, sin más que simplificar sumandos, como
En el lado izquierdo, ; en el lado derecho, recordemos que la suma de los elementos de una progresión aritmética es
así que
En consecuencia,
y hemos encontrado una descomposición de en dos factores (ninguno de los cuales es
o
), así que no es primo.
Algún comentario adicional
Obsérvese que para cada coincidencia de nudos se obtiene una factorización de , así que fácilmente podemos conocer todos sus divisores.
El método también detecta los cuadrados perfectos:
Un número
es un cuadrado perfecto si y sólo si el último nudo que hemos hecho coincide con uno anterior al doblez de la cuerda, condición equivalente a
.
Para finalizar, posiblemente conviene reflexionar un poco sobre la belleza y la utilidad de las matemáticas. Ambos aspectos son importantes (y no están reñidos), pero, a veces, nos podemos contentar con observar su belleza sin pretender una aplicabilidad inmediata (en Gaussianos se habló de algo parecido a esto en Sobre la utilidad directa de las matemáticas).
Lo que aquí hemos presentado es, claramente, un resultado bonito, pero no parece que pueda tener una aplicación práctica. Si quisiéramos analizar si el número es primo con una cuerda real, la longitud del tramo superior de dicha cuerda debería ser
Así que el tamaño de la cuerda que habría que emplear crece de manera desmesurada. Por muy apretados que estuviesen los nudos, si quisiéramos analizar la primalidad de los números que se usan en criptografía tendríamos que usar una cuerda mayor que el tamaño del universo; supongo que sería muy cara… Afortunadamente, los matemáticos podemos usar cuerdas ideales con nudos ideales, y el precio de tales cuerdas no es ningún problema.
Sobre la infinitud de los números primos en Gaussianos hemos publicado bastante. Además, de la demostración del propio Euclides, tenemos también una relacionada con los números de Fermat, una desarrollada por Juan Pablo Pinasco (que además nos lleva a una nueva demostración de la divergencia de la serie armónica) y ¡una demostración basada en topología!. Os recomiendo que le echéis un vistazo a todas ellas.
Este artículo es mi segunda aportación a la Edición X.5 del Carnaval de Matemáticas, que organizo yo mismo.
La imagen principal de este artículo es una creación del propio Juan Luis Varona.
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
Al encontrar divisores de los números me he fijado que, después de un número con «muchos» divisores, siempre hay un primo. Ejemplo: el 36 tiene 9 divisores, incluido el 1 y el 36, su sucesor, 37, es primo; 60 tiene 12 divisores, 61 es primo. Hay una secuencia.
Pero, para poder hablar de eso con un poco de propiedad, tenías que definir de alguna manera rigurosa qué entiendes por «muchos». Para números menores que mil, y si entiendes por «muchos» tener más de 20 divisores, lo que dices falla para estos números: 360, 480, 504, 720, 780, 792, 840, 864, 900, 924, 960.
Propongo el siguiente ejercicio:
Demostrar que todo primo de la forma p=6n+1 puede expresarse de forma única como p=x^2+y^2+xy (donde x, y son enteros positivos)
Un comentario: la hipótesis de que el primo p sea de la forma 6n+1 es superflua, pues los números de la forma 6n, 6n+2, 6n+3, 6n+4 no pueden ser primos si n>0, y ningún x^2+y^2+xy puede tener la forma 6n+5 (por congruencias módulo 6, basta analizar x=0,…,5 e y=x,…,5, que son muy pocos casos).
Esto no resuelve el ejercicio, claro.
Otra observación. El número 3 es una especie de «singularidad», pues puede descomponerse en la forma x^2+y^2+xy (1^2+1^2+1*1) sin ser de la forma 6n+1. Curiosamente, desempeña el mismo papel que el número 2 -también singular- en la descomposición de un entero en suma de dos cuadrados: 2=1^2+1^2 ya que es el único primo que la cumple y que no es de la forma 4n+1.
Bastante interesante el articulo, me sorprendió.Muchas gracias a gaussianos por compartirlo.
Me alegro de que te haya parecido interesante. Muchas gracias por comentar 🙂
El método de la cuerda para la detección de números primos es una versión de la criba de la parábola. Los nudos de la cuerda se identifican con los puntos de la parábola x=y2 de la forma (n2,n) con n entero positivo. Es claro, podemos hacer la demostración por inducción, que los cuadrados perfectos n2 se obtienen como suma de impares consecutivos 2k+1, k=0,1,….,n-1. Si E es el número a testar, es equivalente doblar la cuerda y comparar nudos, con trasladar paralelamente al eje X la parábola x=y2 y comparar los puntos (n2,n) con sus trasladados. Un punto cae en… Lee más »
Dejo un enlace donde desarrollo un ALGORITMO que intenta resolver esta propuesta de hallar números primos impares. No es muyeficiente, pero ejemplifica la capacidad de resolver un problema de modo mas simple posible. LINK: https://es.quora.com/unanswered/C%C3%B3mo-encontrar-primos-con-una-cuerda Tambien note una curiosidad, que el DOBLEZ de la cuerda, cuando cambia de DIRECCIÓN es de 180º que en números discretos es D = 3, o el entero del numero pi, y que determina el MÁXIMO número que se pierde de la cuerda al cambiar de dirección, que para el algoritmo implica la eficiencia o no para generar números primos y que el algoritmo no… Lee más »