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»).

Juan Luis VaronaAsí 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 E > 1 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 E.

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, E-2, seguido de E-4, 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 E es primo. Si hubiese alguna marca del primer tramo coincidente con una marca del segundo tramo, el número E es compuesto.

Como ejemplo presentamos los números E=11, primo, y E=15, compuesto. Se ve que en el número 11 no hay ninguna marca que coincida, por lo que el método nos confirma que 11 es primo:

Mientras tanto, en el caso del 15 hay dos marcas que coinciden (destacadas en rojo). Por tanto, el método nos asegura que 15 es compuesto:

Justificación del método

Vamos a ver por qué funciona el método antes descrito. Como E es un número natural impar, pongamos E=2N+1, con N\ge 1.

Dos marcas coinciden si y sólo si existen enteros a, b, necesariamente 0\le b < a < N y a-b > 1, tales que

\displaystyle{\sum_{i=a}^N (2i+1) = \sum_{i=b}^{N-1} (2i+1)} \qquad (1)

Esas dos cantidades representan, respectivamente, las longitudes del primer y segundo tramo de la cuerda desde la coincidencia hasta el doblez; así mismo, a y b 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 E=15, lo que tenemos es N=7, a=4 y b=1, y los sumandos de los términos derecho e izquierdo de (1) se corresponden con las longitudes de los trozos de cuerda abarcados por las llaves \overbrace{\rule{40pt}{0pt}} y \underbrace{\rule{40pt}{0pt}}, respectivamente:

Volviendo a la justificación del método, (1) se puede escribir, sin más que simplificar sumandos, como

\displaystyle{2N+1 = \sum_{i=b}^{a-1} (2i+1)}

En el lado izquierdo, 2N+1=E; en el lado derecho, recordemos que la suma de los elementos de una progresión aritmética es

\cfrac{\mbox{primer t\'ermino} + \mbox{\'ultimo t\'ermino}}{2} \cdot \mbox{(n\'umero de t\'erminos)},

así que

\displaystyle{\sum_{i=b}^{a-1} (2i+1) = \cfrac{(2b+1)+(2a-1)}{2} \cdot (a-b) = (a+b) (a-b)}

En consecuencia,

E = (a+b) \cdot (a-b)

y hemos encontrado una descomposición de E en dos factores (ninguno de los cuales es 1 o E), así que no es primo.

Algún comentario adicional

Obsérvese que para cada coincidencia de nudos se obtiene una factorización de E, así que fácilmente podemos conocer todos sus divisores.

El método también detecta los cuadrados perfectos:

Un número E 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 b=0.

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 E = 2N+1 es primo con una cuerda real, la longitud del tramo superior de dicha cuerda debería ser

\displaystyle{\sum_{i=0}^N (2i+1) = \cfrac{1+(2N+1)}{2} \cdot (N+1) = (N+1)^2 = \cfrac{(E+1)^2}{4}}

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.

Print Friendly, PDF & Email
0 0 votes
Article Rating

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


Comparte: