Artículos

La distribución de números primos y tamiz de Eratóstenes


Sabemos que hay un número infinito de números primos y que cada número entero distinto de cero se expresa como un producto de números primos. El número 12 se expresa como 2.2.3, el producto de los primos 2, 2 y 3. ¿Cómo podemos saber si un número es primo? ¿Existe un algoritmo, es decir, un proceso con un número finito de pasos para decidir si un número es primo o compuesto como 12?

Esta pregunta ya estaba en la mente de los matemáticos griegos de la antigüedad clásica y la respuesta es positiva. Si queremos saber si el entero positivo no > 1 es primo, solo asegúrate no es divisible por enteros m más pequeño que no. Sin embargo, esta idea se puede refinar porque se demuestra que es suficiente para verificar la divisibilidad de no primos menores o iguales a Ön. Es decir, afirmamos que si no es no es un número primo por lo que hay un primo p tal que p dividir no y p <= Ön. De hecho, como estamos asumiendo que no no es un número primo no es entonces un número compuesto y, por lo tanto, puede descomponerse como no = ab. Si el > Öno y b > Önoentonces no = ab > (Öno) (Öno) = no, una contradicción Entonces tenemos el <= Öno y b <= Önoy cada primo p eso divide el satisfacer p <= el <= Öno. Entonces los enteros primos xtal que x <= Öno, son los únicos que necesitamos probar para encontrar los divisores de no. Es decir, solo divide no por 2, 3, 5, ..., hasta que encontremos el entero más grande más pequeño que Öno.

Por ejemplo, nos gustaría saber si el número 107 es primo. La raíz cuadrada de 107 está entre 10 y 11, es decir, 10 <Ö107 <11. Así que probamos si 107 es divisible por 2, 3, 5, 7. Pero 107 no es divisible por estos primos. Concluimos que el número 107 es primo. Por otro lado, el mismo proceso nos permite determinar los factores primos de un número compuesto. Como otro ejemplo, si no = 319, entonces su raíz cuadrada Ö319 está entre 17 y 18 y, por lo tanto, probamos su divisibilidad por primos menores o iguales a 17. Encontramos que 319 = 11.29, es decir, 319 es el producto de 11 por 29. Para dividir 29 en factores primos, probamos su divisibilidad por primos menores o iguales a 5, porque la raíz cuadrada de 29 está entre 5 y 6. Dado que 29 no es divisible por 2, 3 y 5, concluimos que 29 es primo y, por lo tanto, 319 = 11.29 es la descomposición de 319 en factores primos.

Tenga en cuenta que este algoritmo se basa en la división, y aunque el algoritmo funciona, si consideramos números altos tendremos que realizar una gran cantidad de divisiones, lo que llevaría mucho tiempo. El matemático Eratóstenes de Cirene, contemporáneo de Arquímedes y Aristarco, autor de la antigüedad más famosa para el radio de la tierra, desarrolló un método sistemático para obtener primos más pequeños que un número dado, utilizando la operación de multiplicación en lugar de división. lo que hace que el algoritmo sea más fácil de implementar. Este algoritmo se conoce como el tamiz de Eratóstenes, o método de tamizado. Eratóstenes nació en el 276 a. C., murió en el 196 a. C., estudió filosofía en Atenas y fue director de la famosa biblioteca de Alejandría, y un eminente matemático, geógrafo, historiador, filólogo y poeta. El tamiz de Eratóstenes determina todos los números primos menores que cierto número x dado. Por lo tanto, determina los factores primos de los números compuestos menores que x.

Tenga en cuenta que cada número compuesto no tiene un divisor menor o igual a su raíz cuadrada Öno. Esto sugiere un procedimiento para construir una lista de todos los números primos que no excedan un número entero. xsi primos más pequeños que Öx Ya se conocen. Considere los enteros del 2 al x, enumerados en orden ascendente. Mantengamos a los primos de 2, 3, 5, ..., hasta Öx, y descartar todos sus múltiplos.

En general, ¿cómo eliminamos los múltiplos de algún primo? pr de esta lista, el primer entero restante mayor que pr, también es un número primo, digamos pr +1. De hecho, de lo contrario sería divisible por algún primo más pequeño (en realidad más pequeño que su raíz cuadrada) y ya se habría eliminado. También tenga en cuenta que no debemos preocuparnos por los enteros más pequeños que (pr +1)2porque los números compuestos son menores que (pr +1)2 ya se han eliminado porque todos tenían un factor primo menor que pr +1. Por lo tanto, es suficiente comenzar cada paso eliminando los múltiplos de pr +1 y descartando (pr + 1)2.

Como ejemplo, determinemos todos los números primos menores que 23 usando el método de tamizado. En la lista a continuación, la representación del número en negrita significa que se eliminó en un paso del algoritmo. Por ejemplo, 6 se descarta porque es un múltiplo de primo 2.

Tenemos: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23. Por lo tanto, 2, 3, 5, 7, 11, 13, 17,19 son enteros primos menores que 23.

El método de tamizado es eficiente para obtener una lista de primos más pequeños que un número entero no muy grande, y desde la época de Eratóstenes, el método se ha utilizado para estimar el número de primos en un rango. Sin embargo, si intentamos obtener una lista de enteros que se han descartado, obtenemos una fórmula para el número exacto o aproximado de números primos p xTendremos serias dificultades. El método de tamizado ha sufrido una serie de mejoras con el tiempo. Los matemáticos Brun, Rademacher, Meissel y especialmente Selberg generalizaron el método Sieve y, por lo tanto, muchos problemas clásicos de la teoría de números se volvieron a estudiar con éxito.

Dos números primos dicen primos gemelos si la diferencia entre ellos es 2. Algunos ejemplos de pares primos gemelos son: 3 y 5, 5 y 7, 11 y 13, 17 y 29, 29 y 31, 41 y 43. Académicos de la conjetura de la teoría de números, pero no puede demostrar que hay infinitos primos gemelos. El matemático noruego Brun, en 1919, desarrolló el método de doble tamiz e hizo algunas estimaciones del número de primos gemelos.

En 1950, el matemático noruego A. Selberg ganó la Medalla Fields (la máxima distinción para un matemático) por desarrollar un método extraordinariamente eficiente para estimar la distribución de números primos. Este premio representa un hito, ya que fue la primera vez que un matemático ganó una Medalla Fields por un trabajo sobre Teoría de números. Selberg obtuvo estimaciones mucho más precisas utilizando su refinamiento del método de tamizado y así resolvió muchos problemas clásicos en la teoría de números. Selberg dio una demostración elemental de la ley asintótica de la distribución de números primos, es decir, el teorema de los números primos. Los matemáticos Hadamard y de la Vallée-Poussin dieron, en 1897, la primera demostración de este teorema utilizando análisis matemáticos, más precisamente, Teoría de funciones complejas. El Teorema de los números primos evalúa con qué frecuencia ocurren los números primos, en otras palabras, la tasa de crecimiento de los números primos en la secuencia de enteros positivos. Gracias a Atle Selberg y Paul Erdös, fue posible obtener una demostración del Teorema del número primo, completamente basado en estimaciones, sin el uso de Análisis complejo. Las investigaciones de Selberg sobre la teoría analítica de números facilitaron los avances en una serie de problemas espinosos y revelaron vínculos inusuales entre la teoría numérica y otras áreas de las matemáticas. Por ejemplo: teoría de grupos discretos y formas automórficas, representaciones de grupos de Lie semi-simples, teoría de la función Zeta de Riemann y muchos otros.

Volver a las columnas

<