Número primo

Los números compuestos se pueden organizar en rectángulos pero los números primos no pueden.

Un número primo (o un primo) es un número natural mayor que 1 que no es producto de dos números naturales menores. Un número natural mayor que 1 que no es primo se llama número compuesto. Por ejemplo, 5 es primo porque las únicas formas de escribirlo como un producto, 1 × 5 o 5 × 1, involucran 5 en sí. Sin embargo, 4 es compuesto porque es un producto (2 × 2) en el que ambos números son menores que 4. Los primos son fundamentales en la teoría de números debido al teorema fundamental de la aritmética: todo número natural mayor que 1 es un primo en sí mismo o se puede factorizar como un producto de primos que es único hasta su orden.

La propiedad de ser primo se llama primalidad. Un método simple pero lento de comprobar la primalidad de un número determinado ${displaystyle n}$, llamada división de juicio, prueba si ${displaystyle n}$ es un múltiple de cualquier entero entre 2 y ${displaystyle {sqrt {n}}$. Los algoritmos más rápidos incluyen la prueba de primalidad Miller–Rabin, que es rápida pero tiene una pequeña posibilidad de error, y la prueba de primalidad AKS, que siempre produce la respuesta correcta en el tiempo polinomio, pero es demasiado lento para ser práctico. Existen métodos especialmente rápidos para el número de formas especiales, como los números Mersenne. A diciembre de 2018 el mayor número conocido es un Mersenne primo con 24,862,048 dígitos decimales.

Hay infinitos números primos, como lo demostró Euclides alrededor del año 300 a. Ninguna fórmula simple conocida separa los números primos de los números compuestos. Sin embargo, la distribución de números primos dentro de los números naturales en los grandes se puede modelar estadísticamente. El primer resultado en esa dirección es el teorema de los números primos, probado a fines del siglo XIX, que dice que la probabilidad de que un número grande elegido al azar sea primo es inversamente proporcional a su número de dígitos, es decir, a su logaritmo.

Varias cuestiones históricas relacionadas con los números primos siguen sin resolverse. Estos incluyen la conjetura de Goldbach, de que todo número par mayor que 2 puede expresarse como la suma de dos números primos, y la conjetura de los primos gemelos, de que hay infinitos pares de números primos que tienen solo un número par entre ellos. Tales preguntas estimularon el desarrollo de varias ramas de la teoría de números, centrándose en los aspectos analíticos o algebraicos de los números. Los números primos se utilizan en varias rutinas de la tecnología de la información, como la criptografía de clave pública, que se basa en la dificultad de factorizar números grandes en sus factores primos. En álgebra abstracta, los objetos que se comportan de forma generalizada como números primos incluyen elementos primos e ideales primos.

Definición y ejemplos

Un número natural (1, 2, 3, 4, 5, 6, etc.) se llama un Número primo (o una primo) si es mayor de 1 y no puede ser escrito como el producto de dos números naturales más pequeños. Los números mayores de 1 que no son primos se llaman números compuestos. En otras palabras, ${displaystyle n}$ es primo si ${displaystyle n}$ los elementos no pueden dividirse en grupos de tamaño igual de menor tamaño de más de un artículo, o si no es posible organizar ${displaystyle n}$ puntos en una cuadrícula rectangular que es más de un punto ancho y más de un punto alto. Por ejemplo, entre los números 1 a 6, los números 2, 3 y 5 son los números principales, ya que no hay otros números que los dividen uniformemente (sin un resto). 1 no es primo, ya que está específicamente excluido en la definición. 4 = 2 × 2 y 6 = 2 × 3 ambos son compuestos.

Demostración, con varas Cuisenaire, que 7 es primo, porque ninguna de 2, 3, 4, 5 o 6 lo divide uniformemente

Los divisores de un número natural ${displaystyle n}$ son los números naturales que dividen ${displaystyle n}$ Incluso. Cada número natural tiene 1 y en sí mismo como divisor. Si tiene otro divisor, no puede ser primo. Esta idea conduce a una definición diferente pero equivalente de los primos: son los números con exactamente dos divisores positivos, 1 y el número mismo. Otra manera de expresar lo mismo es que un número ${displaystyle n}$ es primo si es mayor que uno y si ninguno de los números ${displaystyle 2,3,dotsn-1}$ divideciones ${displaystyle n}$ Incluso.

Los primeros 25 números primos (todos los números primos menores que 100) son:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 (secuencia A000040 en el OEIS).

Ni siquiera número ${displaystyle n}$ más grande que 2 es primo porque cualquier número de este puede ser expresado como el producto ${displaystyle 2times n/2}$. Por lo tanto, cada número primo distinto de 2 es un número extraño, y se llama un raro. Del mismo modo, cuando se escribe en el sistema decimal habitual, todos los números primos mayores de 5 extremos en 1, 3, 7, o 9. Los números que terminan con otros dígitos son todos compuestos: números decimales que terminan en 0, 2, 4, 6, o 8 son incluso, y los números decimales que terminan en 0 o 5 son divisibles por 5.

El conjunto de todos los primos es a veces denotado por ${displaystyle mathbf {P}$ (un capital audaz P) o por ${displaystyle mathbb {P}$ (un pizarrón negrita capital P).

Historia

El papiro matemático Rhind

El papiro matemático Rhind, de alrededor de 1550 a. C., tiene expansiones de fracciones egipcias de diferentes formas para números primos y compuestos. Sin embargo, los primeros registros sobrevivientes del estudio explícito de los números primos provienen de las matemáticas griegas antiguas. Los Elementos de Euclides (c. 300 a. C.) prueban la infinitud de los números primos y el teorema fundamental de la aritmética, y muestran cómo construir un número perfecto a partir de un número primo de Mersenne. Otro invento griego, la criba de Eratóstenes, todavía se usa para construir listas de primos.

Alrededor de 1000 dC, el matemático islámico Ibn al-Haytham (Alhazen) encontró el teorema de Wilson, caracterizando los números primos como los números ${displaystyle n}$ que divide ${displaystyle (n-1)!+1}$. También conjetura que todos los números perfectos provienen de la construcción de Euclides usando los primos de Mersenne, pero no pudo probarlo. Otro matemático islámico, Ibn al-Banna' al-Marrakushi, observó que el tamiz de Eratosthenes se puede levantar considerando sólo los divisores principales hasta la raíz cuadrada del límite superior. Fibonacci trajo las innovaciones de las matemáticas islámicas de vuelta a Europa. Su libro Liber Abaci (1202) fue el primero en describir la división de prueba para probar primalidad, de nuevo utilizando divisores sólo hasta la raíz cuadrada.

En 1640 Pierre de Fermat declaró (sin pruebas) el pequeño teorema de Fermat (más tarde probado por Leibniz y Euler). Fermat también investigó la primaidad de la Números de Fermat ${displaystyle 2^{2^{n}+1}$, y Marin Mersenne estudió los primos de Mersenne, números primos de la forma ${displaystyle 2^{p}-1}$ con ${displaystyle p}$ en sí mismo un primo. Christian Goldbach formuló la conjetura de Goldbach, que cada número es la suma de dos primos, en una carta de 1742 a Euler. Euler demostró la conjetura de Alhazen (ahora el teorema Euclid-Euler) que todos los números incluso perfectos pueden ser construidos de los primos de Mersenne. Introdujo métodos de análisis matemático a esta área en sus pruebas de la infinitud de los primos y la divergencia de la suma de los recíprocos de los primos ${displaystyle {tfrac}{2}+{tfrac} {1}{3}+{tfrac {1}{5}+{tfrac {1}{7}+{tfrac {1}{11}+cdots }$. A principios del siglo XIX, Legendre y Gauss conjeturaron que ${displaystyle x}$ tiende a infinito, el número de primos hasta ${displaystyle x}$ es asintotico a ${displaystyle x/log x}$, donde ${displaystyle log x}$ es el logaritmo natural de ${displaystyle x}$. Una consecuencia más débil de esta alta densidad de primos fue el postulado de Bertrand, que por cada ${displaystyle n confía1}$ hay una primera entre ${displaystyle n}$ y ${displaystyle 2n}$, probada en 1852 por Pafnuty Chebyshev. Ideas de Bernhard Riemann en su papel de 1859 sobre la función zeta bosquejó un esbozo para probar la conjetura de Legendre y Gauss. Aunque la hipótesis de Riemann estrechamente relacionada sigue sin ser probada, el esquema de Riemann fue completado en 1896 por Hadamard y de la Vallée Poussin, y el resultado ahora se conoce como el teorema número principal. Otro resultado importante del siglo XIX fue el teorema de Dirichlet sobre progresiones aritméticas, que ciertas progresiones aritméticas contienen infinitamente muchos primos.

Muchos matemáticos han trabajado en pruebas de primalidad para números más grandes que aquellos en los que la división de prueba es aplicable en la práctica. Los métodos que están restringidos a formas numéricas específicas incluyen la prueba de Pépin para números de Fermat (1877), el teorema de Proth (c. 1878), la prueba de primalidad de Lucas-Lehmer (originada en 1856) y la primalidad generalizada de Lucas. prueba.

Desde 1951, todos los números primos más grandes conocidos se han encontrado usando estas pruebas en computadoras. La búsqueda de números primos cada vez más grandes ha generado interés fuera de los círculos matemáticos, a través de Great Internet Mersenne Prime Search y otros proyectos de computación distribuida. La idea de que los números primos tenían pocas aplicaciones fuera de las matemáticas puras se hizo añicos en la década de 1970 cuando se inventaron la criptografía de clave pública y el sistema criptográfico RSA, utilizando los números primos como base.

La mayor importancia práctica de las pruebas de primalidad computarizadas y la factorización llevaron al desarrollo de métodos mejorados capaces de manejar grandes cantidades de formas sin restricciones. La teoría matemática de los números primos también avanzó con el teorema de Green-Tao (2004) de que existen progresiones aritméticas arbitrariamente largas de números primos, y la prueba de Yitang Zhang de 2013 de que existen infinitas brechas de primos de tamaño acotado.

Primalidad de una

La mayoría de los primeros griegos ni siquiera consideraban el 1 como un número, por lo que no podían considerar su primacía. Algunos estudiosos de la tradición griega y romana posterior, incluidos Nicómaco, Jámblico, Boecio y Casiodoro, también consideraban que los números primos eran una subdivisión de los números impares, por lo que tampoco consideraban que el 2 fuera primo. Sin embargo, Euclides y la mayoría de los demás matemáticos griegos consideraban el 2 como primo. Los matemáticos islámicos medievales siguieron en gran medida a los griegos al considerar que 1 no era un número. En la Edad Media y el Renacimiento, los matemáticos comenzaron a tratar el 1 como un número y algunos de ellos lo incluyeron como el primer número primo. A mediados del siglo XVIII, Christian Goldbach enumeró el 1 como principal en su correspondencia con Leonhard Euler; sin embargo, el propio Euler no consideró que 1 fuera primo. En el siglo XIX, muchos matemáticos todavía consideraban que 1 era primo, y las listas de primos que incluían 1 continuaron publicándose en 1956.

Si la definición de un número primo se cambiara para llamar a 1 un primo, muchas declaraciones que involucran números primos tendrían que reformularse de una manera más incómoda. Por ejemplo, sería necesario reformular el teorema fundamental de la aritmética en términos de factorizaciones en primos mayores que 1, porque cada número tendría múltiples factorizaciones con cualquier número de copias de 1. De manera similar, la criba de Eratóstenes no funcionaría correctamente si manejó 1 como un primo, porque eliminaría todos los múltiplos de 1 (es decir, todos los demás números) y generaría solo el número 1. Algunas otras propiedades más técnicas de los números primos tampoco se cumplen para el número 1: por ejemplo, las fórmulas para la función totient de Euler o para la función de suma de divisores son diferentes para los números primos que para el 1. A principios del siglo XX, los matemáticos comenzaron a acordar que el 1 no debería figurar como primo, sino en su propia categoría especial como "unidad".

Propiedades elementales

Factorización única

Escribir un número como producto de números primos se denomina descomposición en factores primos del número. Por ejemplo:

${displaystyle {begin{aligned}34866 ventaja=2times 3times 3times 13times 149\\fnMis 3^{2}times 13times 149.end{aligned}}}$

Los términos del producto se llaman factores principales. El mismo factor principal puede ocurrir más de una vez; este ejemplo tiene dos copias del factor principal ${displaystyle 3.}$ Cuando un primo ocurre varias veces, la exponenciación se puede utilizar para agrupar varias copias del mismo número primo: por ejemplo, en la segunda forma de escribir el producto arriba, ${displaystyle 3^{2}$ denota el cuadrado o segundo poder de ${displaystyle 3.}$

La importancia central de los números primos para la teoría de números y las matemáticas en general se deriva del teorema fundamental de la aritmética. Este teorema establece que todo número entero mayor que 1 se puede escribir como producto de uno o más números primos. Más fuertemente, este producto es único en el sentido de que dos factores primos cualesquiera del mismo número tendrán el mismo número de copias de los mismos números primos, aunque su orden puede diferir. Entonces, aunque hay muchas formas diferentes de encontrar una factorización usando un algoritmo de factorización de enteros, todas deben producir el mismo resultado. Por lo tanto, los primos pueden considerarse los "bloques de construcción básicos" de los números naturales.

Algunas pruebas de la singularidad de las principales factorizaciones se basan en la lema de Euclides: Si ${displaystyle p}$ es un número primo y ${displaystyle p}$ divide un producto ${displaystyle ab}$ de enteros ${displaystyle a}$ y ${displaystyle b,}$ entonces ${displaystyle p}$ divideciones ${displaystyle a}$ o ${displaystyle p}$ divideciones ${displaystyle b}$ (o ambas). Por el contrario, si un número ${displaystyle p}$ tiene la propiedad que cuando divide un producto siempre divide al menos un factor del producto, entonces ${displaystyle p}$ Debe ser la primera.

Infinitud

Hay infinitos números primos. Otra forma de decir esto es que la sucesión

2, 3, 5, 7, 11, 13,...

de números primos nunca termina. Este enunciado se conoce como teorema de Euclides en honor al antiguo matemático griego Euclides, ya que se le atribuye la primera demostración conocida de este enunciado. Se conocen muchas más pruebas de la infinitud de los números primos, incluida una prueba analítica de Euler, la prueba de Goldbach basada en números de Fermat, la prueba de Furstenberg usando topología general y la prueba elegante de Kummer.

La prueba de Euclid muestra que cada lista finita de primos es incompleta. La idea clave es multiplicar juntos los primeros en cualquier lista dada y añadir ${displaystyle 1.}$ Si la lista consta de los primeros ${displaystyle p_{1},p_{2},ldotsp_{n}$ esto da el número

${displaystyle N=1+p_{1}cdot p_{2}cdots P_{n}$

Por el teorema fundamental, ${displaystyle N}$ tiene una factorización principal

${displaystyle N=p'_{1}cdot p'_{2}cdots P'_{m}$

con uno o más factores principales. ${displaystyle N}$ es incluso divisible por cada uno de estos factores, pero ${displaystyle N}$ tiene un resto de uno cuando dividido por cualquiera de los números primos en la lista dada, así que ninguno de los factores principales ${displaystyle N}$ puede estar en la lista dada. Porque no hay lista finita de todos los primos, debe haber infinitamente muchos primos.

Los números formados al sumar uno a los productos de los primos más pequeños se llaman números de Euclides. Los primeros cinco de ellos son primos, pero el sexto,

${displaystyle 1+{big (}2cdot 3cdot 5cdot 7cdot 11cdot 13{big)}=30031=59cdot 509,}$

es un número compuesto.

Fórmulas para números primos

No existe una fórmula eficiente conocida para números primos. Por ejemplo, no existe un polinomio no constante, incluso en varias variables, que tome solo valores primos. Sin embargo, existen numerosas expresiones que codifican todos los primos, o solo los primos. Una fórmula posible se basa en el teorema de Wilson y genera el número 2 muchas veces y todos los demás números primos exactamente una vez. También existe un conjunto de ecuaciones diofánticas en nueve variables y un parámetro con la siguiente propiedad: el parámetro es primo si y solo si el sistema de ecuaciones resultante tiene solución sobre los números naturales. Esto se puede utilizar para obtener una sola fórmula con la propiedad de que todos sus valores positivos son primos.

Otros ejemplos de fórmulas de primera generación provienen del teorema de Mills y un teorema de Wright. Estos afirman que hay constantes reales ${displaystyle A confiado1}$ y ${displaystyle mu }$ tales que

${displaystyle leftlfloor A^{3^{n}rightrfloor {text{ and }leftlfloor 2^{cdots ^{2^{2^{mu Está bien.$

son ideales para cualquier número natural ${displaystyle n}$ en la primera fórmula, y cualquier número de exponentes en la segunda fórmula. Aquí. ${displaystyle lfloor {}cdot {}rfloor }$ representa la función del suelo, el entero más grande menos o igual al número en cuestión. Sin embargo, estos no son útiles para generar primos, ya que los primeros deben ser generados primero para calcular los valores de ${displaystyle A}$ o ${displaystyle mu.}$

Preguntas abiertas

Se han planteado muchas conjeturas que giran en torno a los primos. A menudo teniendo una formulación elemental, muchas de estas conjeturas han resistido la prueba durante décadas: los cuatro problemas de Landau de 1912 siguen sin resolverse. Uno de ellos es la conjetura de Goldbach, que afirma que cada entero incluso ${displaystyle n}$ mayor de 2 se puede escribir como una suma de dos primos. A partir de 2014, esta conjetura ha sido verificada para todos los números hasta ${displaystyle n=4cdot 10^{18}$ Declaraciones más raras de lo que se ha probado, por ejemplo, el teorema de Vinogradov dice que todo entero lo suficientemente grande puede ser escrito como una suma de tres primos. El teorema de Chen dice que cada número suficientemente grande incluso se puede expresar como la suma de un primo y un semiprime (el producto de dos primos). Además, cualquier entero mayor de 10 puede ser escrito como la suma de seis primos. La rama de la teoría del número estudiar tales preguntas se llama teoría del número aditivo.

Otro tipo de problema se refiere a las brechas principales, las diferencias entre los primos consecutivos. La existencia de lagunas primitivas arbitrariamente grandes se puede ver notando que la secuencia ${displaystyle n!+2,n!+3,dotsn!+n}$ consta de ${displaystyle n-1}$ números compuestos, para cualquier número natural ${displaystyle n.}$ Sin embargo, grandes brechas primas ocurren mucho antes de lo que muestra este argumento. Por ejemplo, la primera brecha de la longitud 8 es entre los principales 89 y 97, mucho más pequeña que ${displaystyle 8!=40320.}$ Se conjetura que hay infinitamente muchos primos gemelos, pares de primos con diferencia 2; esta es la conjetura principal gemelo. La conjetura del polignac dice más generalmente que por cada entero positivo ${displaystyle k,}$ hay infinitamente muchos pares de primos consecutivos que difieren por ${displaystyle 2k.}$La conjetura de Andrica, la conjetura de Brocard, la conjetura de Legendre y la conjetura de Oppermann sugieren que las mayores brechas entre primos de ${displaystyle 1}$ a ${displaystyle n}$ debe ser al menos aproximadamente ${displaystyle {sqrt {n}}$ a result that is known to follow from the Riemann hipothesis, while the much stronger Cramér conjecture sets the largest gap size at ${displaystyle O(log n)^{2}). }$ Se pueden generalizar las primeras lagunas primo ${displaystyle k}$-tuples, patrones en las diferencias entre más de dos números primos. Su infinitud y densidad son el tema de la primera conjetura de Hardy-Littlewood, que puede ser motivada por la heurística que los números primos se comportan de forma similar a una secuencia aleatoria de números con densidad dada por el teorema número primo.

Propiedades analíticas

La teoría analítica de números estudia la teoría de números a través de la lente de funciones continuas, límites, series infinitas y las matemáticas relacionadas de lo infinito y lo infinitesimal.

Este área de estudio comenzó con Leonhard Euler y su primer resultado importante, la solución al problema de Basilea. El problema pidió el valor de la suma infinita ${displaystyle 1+{}{4}+{tfrac} {1}{9}+{tfrac {1}{16}+dots}$que hoy se puede reconocer como el valor ${displaystyle zeta (2)}$ de la función Riemann zeta. Esta función está estrechamente relacionada con los números primos y con uno de los problemas no resueltos más significativos en las matemáticas, la hipótesis Riemann. Euler mostró que ${displaystyle zeta (2)=pi ^{2}/6}$. El recíproco de este número, ${displaystyle 6/pi ^{2}$, es la probabilidad limitante de que dos números aleatorios seleccionados uniformemente de una amplia gama son relativamente primos (no tienen factores en común).

La distribución de los primos en la grande, como la pregunta de cuántos primos son más pequeños que un determinado, gran umbral, es descrito por el teorema número primo, pero no eficiente fórmula para ${displaystyle n}$- la primera es conocido. El teorema de Dirichlet sobre progresiones aritméticas, en su forma básica, afirma que polinomios lineales

${displaystyle p(n)=a+bn}$

con números enteros relativamente primos ${displaystyle a}$ y ${displaystyle b}$ tomar infinitamente muchos valores primos. Formas más fuertes del teorema declaran que la suma de las reciprocas de estos valores primitivos se divierte, y que diferentes polinomios lineales con los mismos ${displaystyle b}$ tienen aproximadamente las mismas proporciones de primos. Aunque se han formulado conjeturas acerca de las proporciones de primos en polinomios de mayor grado, siguen sin ser probados, y se desconoce si existe un polinomio cuadrático que (para argumentos enteros) es principalmente infinitamente a menudo.

Demostración analítica del teorema de Euclides

La demostración de Euler de que hay infinitos números primos considera las sumas de los recíprocos de números primos,

${displaystyle {frac}{2}+{frac} {1}{3}+{frac} {1}{5}+{frac} {1}{7}+cdots +{frac {1}{p}.}$

Euler mostró que, por cualquier número real arbitrario ${displaystyle x}$, existe un primo ${displaystyle p}$ para lo cual esta suma es más grande que ${displaystyle x}$. Esto muestra que hay infinitamente muchos primos, porque si hubiera finitamente muchos primos la suma alcanzaría su máximo valor en el mayor primo en lugar de crecer más allá de cada ${displaystyle x}$. La tasa de crecimiento de esta suma se describe más precisamente por el segundo teorema de Mertens. Para comparación, la suma

${displaystyle {frac {1}{2}}}+{frac {1}{2^{2}}}}+{frac}}}}}{frac}}}}} {frac}} {f}}} {f}}} {f}}}} {f}}}}} {f}}}}}}}}}}} { {1}{3^{2}}+cdots {fn}}$

no crece al infinito como ${displaystyle n}$ va al infinito (ver el problema de Basilea). En este sentido, los números primos ocurren más a menudo que cuadrados de números naturales, aunque ambos sets son infinitos. El teorema de Brun afirma que la suma de las reciprocas de los primos gemelos,

${displaystyle left({frac {1}{3}}+{frac {1} {5}}}right)+left({frac {frac} {fc}}}}}}derecho)+left({fracfracfcfc} {1}{5}}+{frac {1} {7}}}right)+left({frac {frac} {fn}}}}}derecho) {1}{11}+{} {13}}derecha)+cdots}$

es finito. Debido al teorema de Brun, no es posible utilizar el método de Euler para resolver la conjetura de los primos gemelos, de que existen infinitos primos gemelos.

Número de números primos por debajo de un límite dado

El error relativo ${displaystyle {tfrac}{log}.$ y la integral logarítmica ${displaystyle operatorname {Li} (n)}$ como aproximaciones a la función de venta anticipada. Ambos errores relativos disminuyen a cero como ${displaystyle n}$ crece, pero la convergencia a cero es mucho más rápida para la integral logarítmica.

La función de venta anticipada ${displaystyle pi (n)}$ se define como el número de primos no mayor que ${displaystyle n}$. Por ejemplo, ${displaystyle pi (11)=5}$, ya que hay cinco primos menos o igual a 11. Métodos como el algoritmo Meissel-Lehmer pueden calcular valores exactos de ${displaystyle pi (n)}$ más rápido de lo que sería posible listar cada primo hasta ${displaystyle n}$. El teorema número primo declara que ${displaystyle pi (n)}$ es asintotico a ${displaystyle n/log n}$, que se denota como

${displaystyle pi (n)sim {frac {log n}}}$

y significa que la relación ${displaystyle pi (n)}$ en relación con la fracción de la mano derecha ${displaystyle n}$ crece al infinito. Esto implica la probabilidad de que un número elegido aleatoriamente menos que ${displaystyle n}$ es primo (aproximadamente) inversamente proporcional al número de dígitos en ${displaystyle n}$. También implica que ${displaystyle n}$t número primario es proporcional a ${displaystyle nlog n}$y por lo tanto que el tamaño promedio de una brecha principal es proporcional a ${displaystyle log n}$. Una estimación más precisa para ${displaystyle pi (n)}$ es dado por la integral logarítmica offset

${displaystyle pi (n)sim operatorname {Li} (n)=int _{2}^{n}{frac {dt}{log} }$

Progresiones aritméticas

Una progresión aritmética es una secuencia finita o infinita de números tal que los números consecutivos en la secuencia tienen todos la misma diferencia. Esta diferencia se llama módulo de progresión. Por ejemplo,

3, 12, 21, 30, 39,...

es una progresión aritmética infinita con módulo 9. En una progresión aritmética, todos los números tienen el mismo resto cuando se dividen por el módulo; en este ejemplo, el resto es 3. Debido a que tanto el módulo 9 como el resto 3 son múltiplos de 3, también lo son todos los elementos de la secuencia. Por lo tanto, esta progresión contiene solo un número primo, el 3 mismo. En general, la progresión infinita

${displaystyle a,a+q,a+2q,a+3q,dots }$

puede tener más de un primo solamente cuando su resto ${displaystyle a}$ y módulos ${displaystyle q}$ son relativamente primos. Si son relativamente primos, el teorema de Dirichlet sobre progresiones aritméticas afirma que la progresión contiene infinitamente muchos primos.

Primes in the arithmetic progressions modulo 9. Cada fila de la banda horizontal delgada muestra una de las nueve progresiones posibles mod 9, con números primos marcados en rojo. Las progresiones de números que son 0, 3 o 6 mod 9 contienen en la mayoría de un número primo (el número 3); las progresiones restantes de números que son 2, 4, 5, 7, y 8 mod 9 tienen infinitamente muchos números primos, con números similares de primos en cada progresión

El teorema de Green-Tao muestra que existen progresiones aritméticas finitas arbitrariamente largas que consisten solo en números primos.

Valores primos de polinomios cuadráticos

La espiral Ulam. Grupo de números primos (rojo) sobre algunas diagonales y no otros. Valores iniciales ${displaystyle 4n^{2}-2n+41}$ se muestran en azul.

Euler señaló que la función

${displaystyle No.$

rendimientos números primos para ${displaystyle 1leq nleq 40}$, aunque los números compuestos aparecen entre sus valores posteriores. La búsqueda de una explicación para este fenómeno llevó a la profunda teoría algebraica de números Heegner y el problema número de clase. La conjetura de Hardy-Littlewood F predice la densidad de primos entre los valores de polinomios cuadráticos con coeficientes enteros en términos de la integral logarítmica y los coeficientes polinomio. Ningún polinomio cuadrático ha demostrado tomar infinitamente muchos valores primos.

La espiral de Ulam organiza los números naturales en una cuadrícula bidimensional, formando espirales en cuadrados concéntricos que rodean el origen con los números primos resaltados. Visualmente, los primos parecen agruparse en ciertas diagonales y no en otras, lo que sugiere que algunos polinomios cuadráticos toman valores primos con más frecuencia que otros.

Función Zeta e hipótesis de Riemann

Parcela de los valores absolutos de la función zeta, mostrando algunas de sus características

Una de las preguntas más famosas sin resolver en matemáticas, que datan de 1859, y uno de los Problemas del Premio del Milenio, es la hipótesis Riemann, que pregunta dónde los ceros de la función Riemann zeta ${displaystyle zeta (s)}$ están ubicados. Esta función es una función analítica en los números complejos. Para números complejos ${displaystyle s}$ con la parte real superior a uno es igual a una suma infinita sobre todos los enteros, y un producto infinito sobre los números primos,

${displaystyle zeta (s)=sum _{n=1}{infty }{frac {1} {fn} {fn}} {fn} {fn}} {fn}} {fn}}} {fn}}}} {fn}}} {fn} {fn}}}}}}}}} {fn}}} {fn}}}}}}}} {p}}}}}} {p} {f}}}}}}}} {p}}}}}}}}}} {p}}}} {p}} {p}} {p} {f}}}}}}}}}}}}}} {f}}}}}}}}}}}}}}}} {f}}}}}}}}}} {f}}}}}}}}}}}}}} {p}}}}}}}}}}} {fn}}}}}}}}}}}}} {f}}}}}}}} {fnMicrosoft Sans Serif}} {fnMicroc} {1}{1-p^{-s}}}$

Esta igualdad entre una suma y un producto, descubierto por Euler, se llama un producto Euler. El producto Euler puede derivarse del teorema fundamental de la aritmética, y muestra la estrecha conexión entre la función zeta y los números primos. Lleva a otra prueba de que hay infinitamente muchos primos: si sólo había finitos muchos, entonces la igualdad suma-producto también sería válida ${displaystyle s=1}$, pero la suma se desvanecería (es la serie armónica ${displaystyle 1+{}{2}+{tfrac} {1}{3}+dots }$) mientras el producto sería finito, una contradicción.

La hipótesis Riemann indica que los ceros de la función zeta son todos números negativos incluso, o números complejos con parte real igual a 1/2. La prueba original del teorema número primo se basó en una forma débil de esta hipótesis, que no hay ceros con parte real igual a 1, aunque se han encontrado otras pruebas elementales. La función de venta anticipada puede ser expresada por la fórmula explícita de Riemann como una suma en la que cada término viene de uno de los ceros de la función zeta; el término principal de esta suma es la integral logarítmica, y los términos restantes hacen que la suma fluctúe por encima y por debajo del término principal. En este sentido, los ceros controlan cómo se distribuyen regularmente los números primos. Si la hipótesis Riemann es verdad, estas fluctuaciones serán pequeñas, y la distribución asintotica de primos dados por el número principal teorema también se mantendrá sobre intervalos mucho más cortos (de longitud alrededor de la raíz cuadrada de ${displaystyle x}$ para intervalos cerca de un número ${displaystyle x}$).

Álgebra abstracta

Aritmética modular y campos finitos

Aritmética modular modifica el aritmético habitual sólo utilizando los números ${displaystyle {0,1,2,dotsn-1}$, para un número natural ${displaystyle n}$ llamado el módulo. Cualquier otro número natural puede ser mapeado en este sistema sustituyéndolo por su resto después de división por ${displaystyle n}$. Las sumas, diferencias y productos modulares se calculan realizando el mismo reemplazo por el resto en el resultado de la suma, diferencia o producto habitual de enteros. La igualdad de los enteros corresponde a congruencia en aritmética modular: ${displaystyle x}$ y ${displaystyle y}$ son congruentes (escrito ${displaystyle xequiv y}$ mod ${displaystyle n}$) cuando tienen el mismo resto después de división por ${displaystyle n}$. Sin embargo, en este sistema de números, la división por todos los números no cero es posible si y sólo si el módulo es primario. Por ejemplo, con el número principal ${displaystyle 7}$ como módulo, división por ${displaystyle 3}$ es posible: ${displaystyle 2/3equiv 3{bmod {7}}$, porque los denominadores de limpieza multiplicando ambos lados por ${displaystyle 3}$ da la fórmula válida ${displaystyle 2equiv 9{bmod {7}}$. Sin embargo, con el módulo compuesto ${displaystyle 6}$, división por ${displaystyle 3}$ es imposible. No hay una solución válida ${displaystyle 2/3equiv x{bmod {6}}$: despejar denominadores multiplicando por ${displaystyle 3}$ hace que el lado izquierdo se convierta ${displaystyle 2}$ mientras que el lado derecho se convierte en ${displaystyle 0}$ o ${displaystyle 3}$. En la terminología del álgebra abstracta, la capacidad de realizar división significa que modulo aritmético modular un número primo forma un campo o, más específicamente, un campo finito, mientras que otros moduli sólo dan un anillo pero no un campo.

Varios teoremas sobre primos se pueden formular utilizando aritmética modular. Por ejemplo, el pequeño teorema de Fermat dice que si ${displaystyle anot equiv 0}$ (modelo) ${displaystyle p}$), entonces ${displaystyle a^{p-1}equiv 1}$ (modelo) ${displaystyle p}$). Resumiendo esto sobre todas las opciones ${displaystyle a}$ da la ecuación

${displaystyle sum ¿Por qué? - ¿Qué?$

siempre que sea válido ${displaystyle p}$ es primo. La conjetura de Giuga dice que esta ecuación es también una condición suficiente para ${displaystyle p}$ para ser primo. El teorema de Wilson dice que un entero ${displaystyle p título1}$ es primo si y sólo si el factorial ${displaystyle (p-1)}$ es congruente con ${displaystyle -1}$ mod ${displaystyle p}$. Para un composite Número ${displaystyle ;n=rcdot s;}$ esto no puede sostenerse, ya que uno de sus factores divide ambos n y ${displaystyle (n-1)}$, y así ${displaystyle (n-1)}equiv -1{pmod {n}}$ es imposible.

Números P-ádicos

El ${displaystyle p}$- orden adictivo ${displaystyle nu _{p}(n)}$ de un entero ${displaystyle n}$ es el número de copias de ${displaystyle p}$ en la factorización principal ${displaystyle n}$. El mismo concepto se puede ampliar de números enteros a números racionales definiendo el ${displaystyle p}$- orden adictivo de una fracción ${displaystyle m/n}$ para ser ${displaystyle nu _{p}(m)-nu _{p}(n)}$. El ${displaystyle p}$- valor absoluto adictivo ${displaystyle Silencio.$ de cualquier número racional ${displaystyle q}$ entonces se define como ${fnMicrosoft Sans Serif}$. Multiplicar un entero por su ${displaystyle p}$- el valor absoluto adictivo cancela los factores ${displaystyle p}$ en su factorización, dejando sólo los otros primos. Así como la distancia entre dos números reales se puede medir por el valor absoluto de su distancia, la distancia entre dos números racionales se puede medir por su ${displaystyle p}$- distancia adictiva, la ${displaystyle p}$- valor absoluto adictivo de su diferencia. Para esta definición de distancia, dos números están unidos (tienen una pequeña distancia) cuando su diferencia es divisible por un alto poder de ${displaystyle p}$. De la misma manera que los números reales se pueden formar de los números racionales y sus distancias, añadiendo valores de limitación extra para formar un campo completo, los números racionales con los ${displaystyle p}$-adic distancia se puede extender a un campo completo diferente, el ${displaystyle p}$- números adictivos.

Esta imagen de un orden, valor absoluto, y campo completo derivado de ellos puede ser generalizado a campos de número algebraico y sus valoraciones (ciertas cartografías del grupo multiplicativo del campo a un grupo aditivo totalmente ordenado, también llamados pedidos), valores absolutos (certificados mapas multiplicativos del campo a los números reales, también llamados normas), y lugares (extensiones a campos completos en los que el campo dado es un conjunto denso, también llamado terminación). La extensión de los números racionales a los números reales, por ejemplo, es un lugar en el que la distancia entre los números es el valor absoluto habitual de su diferencia. La asignación correspondiente a un grupo aditivo sería el logaritmo del valor absoluto, aunque esto no cumple todos los requisitos de una valoración. Según el teorema de Ostrowski, hasta una noción natural de equivalencia, los números reales y ${displaystyle p}$- los números adictivos, con sus órdenes y valores absolutos, son las únicas valoraciones, valores absolutos y lugares sobre los números racionales. El principio local-global permite que ciertos problemas sobre los números racionales sean resueltos mediante la búsqueda de soluciones conjuntas de cada uno de sus lugares, subrayando nuevamente la importancia de los principios a la teoría de números.

Elementos primos en anillos

Los primos gausianos con norma menos de 500

Un anillo conmutativo es una estructura algebraica donde se definen la adición, la resta y la multiplicación. Los enteros son un anillo, y los números primos de los enteros se han generalizado a los anillos de dos maneras diferentes, elementos principales y elementos irreducibles. Un elemento ${displaystyle p}$ de un anillo ${displaystyle R.$ se llama primo si no es cero, no tiene inverso multiplicativo (es decir, no es una unidad), y satisface el siguiente requisito: siempre que ${displaystyle p}$ divide el producto ${displaystyle xy}$ de dos elementos ${displaystyle R.$, también divide al menos uno de ${displaystyle x}$ o ${displaystyle y}$. Un elemento es irreducible si no es una unidad ni el producto de otros dos elementos no-unidad. En el anillo de los enteros, los elementos primos e irreducibles forman el mismo conjunto,

${displaystyle {dots-11,-7,-5,-3,-2,2,3,5,7,11,dots },}$

En un anillo arbitrario, todos los elementos primos son irreducibles. Lo contrario no se cumple en general, pero se cumple para dominios de factorización únicos.

El teorema fundamental de la aritmética sigue manteniendo (por definición) en dominios de factorización únicos. Un ejemplo de tal dominio es los enteros gausianos ${displaystyle mathbb {Z} [i]$, el anillo de números complejos de la forma ${displaystyle a+bi}$ Donde ${displaystyle i}$ denota la unidad imaginaria y ${displaystyle a}$ y ${displaystyle b}$ son enteros arbitrarios. Sus elementos principales son conocidos como primos gausianos. No todos los números que son primos entre los enteros siguen siendo primos en los enteros gausianos; por ejemplo, el número 2 puede ser escrito como un producto de los dos primos gaisianos ${displaystyle 1+i}$ y ${displaystyle 1-i}$. Los primos racionales (los elementos primos de los enteros) congruentes a 3 mod 4 son los primos gausianos, pero los primos racionales congruentes a 1 mod 4 no lo son. Esta es una consecuencia del teorema de Fermat en sumas de dos cuadrados, que declara que una prima extraña ${displaystyle p}$ es expresible como la suma de dos plazas, ${displaystyle p=x^{2}+y^{2}$, y por lo tanto factorable ${displaystyle p=(x+iy)(x-iy)}$, exactamente cuando ${displaystyle p}$ 1 mod 4.

Principales ideales

No cada anillo es un dominio de factorización único. Por ejemplo, en el anillo de números ${displaystyle a+b{sqrt {-5}}$ (para los enteros ${displaystyle a}$ y ${displaystyle b}$) el número ${displaystyle 21}$ tiene dos factores ${displaystyle 21=3cdot 7=(1+2{sqrt {-5})(1-2{sqrt) {-5}}}$, donde ninguno de los cuatro factores se puede reducir más, por lo que no tiene una factorización única. Para extender la factorización única a una clase más grande de anillos, la noción de un número puede ser reemplazada por la de un ideal, un subconjunto de los elementos de un anillo que contiene todas las sumas de pares de sus elementos, y todos los productos de sus elementos con elementos de anillo. Los primeros ideales, que generaliza elementos primos en el sentido de que el ideal principal generado por un elemento primario es un ideal primario, son una herramienta importante y objeto de estudio en álgebra comunitaria, teoría de números algebraicos y geometría algebraica. Los ideales principales del anillo de los enteros son los ideales (0), (2), (3), (5), (7), (11),... El teorema fundamental de la aritmética generaliza al teorema Lasker-Noether, que expresa cada ideal en un anillo conmutativo noetheriano como una intersección de ideales primarios, que son las generalizaciones apropiadas de los poderes primarios.

El espectro de un anillo es un espacio geométrico cuyos puntos son los ideales primos del anillo. La geometría aritmética también se beneficia de esta noción, y existen muchos conceptos tanto en geometría como en teoría de números. Por ejemplo, la factorización o ramificación de los ideales primos cuando se eleva a un campo de extensión, un problema básico de la teoría algebraica de números, guarda cierto parecido con la ramificación en geometría. Estos conceptos pueden incluso ayudar con preguntas de teoría de números que se relacionan únicamente con números enteros. Por ejemplo, los ideales primos en el anillo de números enteros de campos numéricos cuadráticos se pueden usar para probar la reciprocidad cuadrática, una declaración que se refiere a la existencia de números primos enteros módulo de raíces cuadradas. Los primeros intentos de probar el último teorema de Fermat llevaron a la introducción de Kummer de los números primos regulares, números primos enteros relacionados con el fracaso de la factorización única en los enteros ciclotómicos. La cuestión de cuántos números primos enteros se factorizan en un producto de múltiples ideales primos en un campo numérico algebraico se aborda mediante el teorema de densidad de Chebotarev, que (cuando se aplica a los enteros ciclotómicos) tiene el teorema de Dirichlet sobre los números primos. en progresiones aritméticas como un caso especial.

Teoría de grupos

En la teoría de grupos finitos los teoremas Sylow implican que, si un poder de un número primo ${displaystyle p^{n}$ divide el orden de un grupo, luego el grupo tiene un subgrupo de orden ${displaystyle p^{n}$. Por el teorema de Lagrange, cualquier grupo de primer orden es un grupo cíclico, y por el teorema de Burnside cualquier grupo cuyo orden es divisible por sólo dos primos es solvable.

Métodos computacionales

El pequeño engranaje en este pedazo de equipo de granja tiene 13 dientes, un número primo, y el engranaje medio tiene 21, relativamente primo a 13

Durante mucho tiempo, la teoría de números en general, y el estudio de los números primos en particular, se consideró el ejemplo canónico de las matemáticas puras, sin aplicaciones fuera de las matemáticas más que el uso de dientes de engranajes con números primos para distribuir el desgaste. igualmente. En particular, los teóricos de números como el matemático británico G. H. Hardy se enorgullecían de hacer un trabajo que no tenía ningún significado militar.

Esta visión de la pureza de la teoría de los números se hizo añicos en la década de 1970, cuando se anunció públicamente que los números primos podían utilizarse como base para la creación de algoritmos criptográficos de clave pública. Estas aplicaciones han dado lugar a importantes estudios de algoritmos para computar con números primos y, en particular, de pruebas de primalidad, métodos para determinar si un número determinado es primo. La rutina de prueba de primalidad más básica, la división de prueba, es demasiado lenta para ser útil para grandes números. Un grupo de pruebas modernas de primalidad es aplicable a números arbitrarios, mientras que hay pruebas más eficientes disponibles para números de tipos especiales. La mayoría de las pruebas de primalidad solo indican si su argumento es primo o no. Las rutinas que también proporcionan un factor primo de argumentos compuestos (o todos sus factores primos) se denominan algoritmos de factorización. Los números primos también se utilizan en computación para sumas de control, tablas hash y generadores de números pseudoaleatorios.

División de prueba

El método más básico de comprobar la primaidad de un entero dado ${displaystyle n}$ se llama División de Primera Instancia. Este método divide ${displaystyle n}$ por cada entero de 2 hasta la raíz cuadrada ${displaystyle n}$. Cualquier integer dividiendo ${displaystyle n}$ Incluso establece ${displaystyle n}$ como composite; de lo contrario es primo. Los enteros más grandes que la raíz cuadrada no necesitan ser revisados porque, siempre que ${displaystyle n=acdot b}$, uno de los dos factores ${displaystyle a}$ y ${displaystyle b}$ es inferior o igual a la raíz cuadrada ${displaystyle n}$. Otra optimización es comprobar sólo los primos como factores en esta gama. Por ejemplo, para comprobar si 37 es primo, este método lo divide por los primos en el rango de 2 a ${displaystyle {sqrt {37}}$, que son 2, 3, y 5. Cada división produce un resto no cero, por lo que 37 es realmente primo.

Aunque este método es simple de describir, no es práctico para probar la primalidad de números enteros grandes, porque la cantidad de pruebas que realiza crece exponencialmente en función de la cantidad de dígitos de estos números enteros. Sin embargo, todavía se usa la división de prueba, con un límite más pequeño que la raíz cuadrada en el tamaño del divisor, para descubrir rápidamente números compuestos con factores pequeños, antes de usar métodos más complicados en los números que pasan este filtro.

Tamices

El tamiz de Eratosthenes comienza con todos los números sin marcar (gray). Repetidamente encuentra el primer número unmarked, lo marca como primo (colores oscuros) y marca su cuadrado y todos los múltiplos posteriores como compuesto (colores más ligeros). Después de marcar los múltiplos de 2 (rojo), 3 (verde), 5 (azul), y 7 (amarillo), todos los primos hasta la raíz cuadrada del tamaño de la tabla se han procesado, y todos los números no marcados restantes (11, 13, etc.) están marcados como primos (magenta).

Antes de las computadoras, comúnmente se imprimían tablas matemáticas que enumeraban todos los primos o factorizaciones de primos hasta un límite determinado. El método más antiguo para generar una lista de números primos se llama la criba de Eratóstenes. La animación muestra una variante optimizada de este método. Otro método de tamizado más asintóticamente eficiente para el mismo problema es el tamiz de Atkin. En matemáticas avanzadas, la teoría del tamiz aplica métodos similares a otros problemas.

Pruebas de primalidad versus pruebas de primalidad

Algunas de las pruebas modernas más rápidas para si un número dado arbitrario ${displaystyle n}$ es primo son algoritmos probabilísticos (o Monte Carlo), lo que significa que tienen una pequeña oportunidad aleatoria de producir una respuesta incorrecta. Por ejemplo, la prueba de primalidad Solovay-Strassen en un número determinado ${displaystyle p}$ elige un número ${displaystyle a}$ aleatoriamente desde ${displaystyle 2}$ a través de ${displaystyle p-2}$ y utiliza exponenciación modular para comprobar si ${displaystyle a^{(p-1)/2}pm 1}$ es divisible por ${displaystyle p}$. Si es así, responde sí y de lo contrario responde no. Si ${displaystyle p}$ realmente es primo, siempre responderá sí, pero si ${displaystyle p}$ es composite entonces responde sí con probabilidad a la mayoría 1/2 y no con probabilidad al menos 1/2. Si esta prueba se repite ${displaystyle n}$ tiempos en el mismo número, la probabilidad de que un número compuesto podría pasar la prueba cada vez es ${displaystyle 1/2^{n}$. Debido a que esto disminuye exponencialmente con el número de pruebas, proporciona alta confianza (aunque no certeza) que un número que pasa la prueba repetida es primordial. Por otro lado, si la prueba alguna vez falla, entonces el número es ciertamente compuesto. Un número compuesto que pasa tal prueba se llama pseudoprime.

Por el contrario, algunos otros algoritmos garantizan que su respuesta siempre será correcta: los primos siempre se determinarán como primos y los compuestos siempre se determinarán como compuestos. Por ejemplo, esto es cierto en la división de juicio. Los algoritmos con salida correcta garantizada incluyen algoritmos deterministas (no aleatorios), como la prueba de primalidad AKS, y algoritmos aleatorios de Las Vegas donde las elecciones aleatorias realizadas por el algoritmo no afectan su respuesta final, como algunas variaciones de la prueba de primalidad de curva elíptica. Cuando el método de la curva elíptica concluye que un número es primo, proporciona un certificado de primalidad que se puede verificar rápidamente. La prueba de primalidad de curva elíptica es la más rápida en la práctica de las pruebas de primalidad de corrección garantizada, pero su análisis de tiempo de ejecución se basa en argumentos heurísticos en lugar de pruebas rigurosas. La prueba de primalidad AKS tiene una complejidad temporal probada matemáticamente, pero en la práctica es más lenta que la prueba de primalidad de curva elíptica. Estos métodos se pueden utilizar para generar grandes números primos aleatorios, generando y probando números aleatorios hasta encontrar uno que sea primo; al hacer esto, una prueba probabilística más rápida puede eliminar rápidamente la mayoría de los números compuestos antes de que se utilice un algoritmo correcto garantizado para verificar que los números restantes son primos.

La siguiente tabla enumera algunas de estas pruebas. Su tiempo de funcionamiento se da en términos de ${displaystyle n}$, el número a ser probado y, para algoritmos probabilísticos, el número ${displaystyle k}$ de pruebas realizadas. Además, ${displaystyle varepsilon }$ es un número positivo arbitrariamente pequeño, y el registro es el logaritmo a una base no especificada. La gran notación O significa que cada vez que se limita debe multiplicarse por un factor constante para convertirlo de unidades sin dimensión a unidades de tiempo; este factor depende de detalles de implementación como el tipo de computadora utilizado para ejecutar el algoritmo, pero no en los parámetros de entrada ${displaystyle n}$ y ${displaystyle k}$.

Prueba	Desarrollado en	Tipo	Hora de correr	Notas	Referencias
Prueba de primalidad AKS	2002	determinista	${displaystyle O(log n)^{6+varepsilon }}$
Primalidad curva elíptica	1986	Las Vegas	${displaystyle O(log n)^{4+varepsilon }}$ heurística
Prueba de primalidad de Baillie-PSW	1980	Monte Carlo	${displaystyle O(log n)^{2+varepsilon }}$
Miller-Rabin prueba de primalidad	1980	Monte Carlo	${displaystyle O(k(log n)^{2+varepsilon }}$	probabilidad de error ${displaystyle 4^{-k}$
Prueba de primalidad de Solovay–Strassen	1977	Monte Carlo	${displaystyle O(k(log n)^{2+varepsilon }}$	probabilidad de error ${displaystyle 2^{-k}$

Algoritmos de propósito especial y el número primo más grande conocido

Además de las pruebas antes mencionadas que se aplican a cualquier número natural, algunos números de una forma especial se pueden probar para primalidad más rápidamente. Por ejemplo, la prueba de primalidad de Lucas-Lehmer puede determinar si un número de Mersenne (uno menos que una potencia de dos) es primo, determinísticamente, al mismo tiempo que una sola iteración de la prueba de Miller-Rabin. Por eso, desde 1992 (a partir de diciembre de 2018), el número primo más grande conocido siempre ha sido un número primo de Mersenne. Se conjetura que hay infinitos números primos de Mersenne.

La siguiente tabla proporciona los números primos más grandes conocidos de varios tipos. Algunos de estos números primos se han encontrado utilizando computación distribuida. En 2009, el proyecto Great Internet Mersenne Prime Search recibió un premio de 100.000 dólares estadounidenses por descubrir primero un número primo con al menos 10 millones de dígitos. Electronic Frontier Foundation también ofrece $ 150,000 y $ 250,000 para números primos con al menos 100 millones de dígitos y mil millones de dígitos, respectivamente.

Factorización de enteros

Dado un entero compuesto ${displaystyle n}$, la tarea de proporcionar uno (o todos) factores principales se denomina factorización de ${displaystyle n}$. Es significativamente más difícil que las pruebas de primalidad, y aunque se conocen muchos algoritmos de factorización, son más lentos que los métodos de prueba de primalidad más rápidos. La división de pruebas y el algoritmo rho de Pollard se pueden utilizar para encontrar factores muy pequeños ${displaystyle n}$, y la factorización de curva elíptica puede ser eficaz cuando ${displaystyle n}$ tiene factores de tamaño moderado. Los métodos adecuados para grandes cantidades arbitrarias que no dependen del tamaño de sus factores incluyen el tamiz cuadrático y el tamiz de campo de número general. Al igual que con las pruebas de primalidad, también hay algoritmos de factorización que requieren su entrada para tener una forma especial, incluyendo el tamiz de campo número especial. A diciembre de 2019 el mayor número conocido por haber sido factorizado por un algoritmo de uso general es RSA-240, que tiene 240 dígitos decimales (795 bits) y es el producto de dos grandes primos.

El algoritmo de Shor puede factorizar cualquier número entero en un polinomio de pasos en una computadora cuántica. Sin embargo, la tecnología actual solo puede ejecutar este algoritmo para números muy pequeños. A partir de octubre de 2012, el número más grande que ha factorizado una computadora cuántica que ejecuta el algoritmo de Shor es 21.

Otras aplicaciones computacionales

Varios algoritmos de criptografía de clave pública, como RSA y el intercambio de clave Diffie-Hellman, se basan en grandes números primos (2048-bit primos son comunes). RSA se basa en la suposición de que es mucho más fácil (es decir, más eficiente) realizar la multiplicación de dos (grandes) números ${displaystyle x}$ y ${displaystyle y}$ que calcular ${displaystyle x}$ y ${displaystyle y}$ (supuesto coprime) si sólo el producto ${displaystyle xy}$ es conocido. El intercambio clave Diffie-Hellman se basa en el hecho de que hay algoritmos eficientes para la exponencia modular (computación) ${displaystyle a^{b}{bmod {c}}$), mientras que la operación inversa (el logaritmo discreto) se cree que es un problema difícil.

Los números primos se utilizan con frecuencia para tablas de hash. Por ejemplo, el método original de Carter y Wegman para la piratería universal se basó en las funciones de computación hash eligiendo funciones lineales aleatorias modulo grandes números primos. Carter y Wegman generalizaron este método para ${displaystyle k}$- Hacha independiente usando polinomios de mayor grado, de nuevo modulo grandes primos. Además de en la función hash, los números primos se utilizan para el tamaño de la tabla hash en tablas de probing cuadráticas basadas para asegurar que la secuencia de sonda cubre toda la tabla.

Algunos métodos de checksum se basan en las matemáticas de números primos. Por ejemplo, las sumas de comprobación utilizadas en los números de libro estándar internacional se definen tomando el resto del modulo número 11, un número primo. Debido a que 11 es la primera este método puede detectar errores de un solo dígitos y transposiciones de dígitos adyacentes. Otro método de checksum, Adler-32, utiliza el modulo aritmético 65521, el mayor número primo menos que ${displaystyle 2^{16}$. Los números primos también se utilizan en generadores de números de seudorandad incluyendo generadores congruencia lineales y el Twister Mersenne.

Otras aplicaciones

Los números primos son de vital importancia para la teoría de números, pero también tienen muchas aplicaciones en otras áreas de las matemáticas, como el álgebra abstracta y la geometría elemental. Por ejemplo, es posible colocar números primos de puntos en una cuadrícula bidimensional para que no haya tres en una línea, o para que cada triángulo formado por tres de los puntos tenga un área grande. Otro ejemplo es el criterio de Eisenstein, una prueba de si un polinomio es irreducible en función de la divisibilidad de sus coeficientes por un número primo y su cuadrado.

La suma conectada de dos nudos primos

El concepto de número primo es tan importante que se ha generalizado de diferentes maneras en varias ramas de las matemáticas. Generalmente, "principal" indica minimalidad o indescomponibilidad, en un sentido apropiado. Por ejemplo, el campo primo de un campo dado es su subcampo más pequeño que contiene tanto el 0 como el 1. Es el campo de los números racionales o un campo finito con un número primo de elementos, de ahí el nombre. A menudo, se pretende un segundo significado adicional al usar la palabra principal, a saber, que cualquier objeto puede descomponerse, esencialmente de manera única, en sus componentes principales. Por ejemplo, en la teoría de nudos, un nudo primo es un nudo indescomponible en el sentido de que no puede escribirse como la suma conectada de dos nudos no triviales. Cualquier nudo se puede expresar de forma única como una suma conectada de nudos primos. La descomposición en primos de 3 variedades es otro ejemplo de este tipo.

Más allá de las matemáticas y la computación, los números primos tienen conexiones potenciales con la mecánica cuántica y se han usado metafóricamente en las artes y la literatura. También se han utilizado en biología evolutiva para explicar los ciclos de vida de las cigarras.

Polígonos construibles y particiones poligonales

Construcción de un pentágono regular con rectitud y brújula. Esto sólo es posible porque 5 es un Fermat prime.

Los primos de Fermat son primos de la forma

${displaystyle F_{k}=2^{2^{k}+1,}$

con ${displaystyle k}$ un entero no negativo. Son nombrados por Pierre de Fermat, quien conjetura que todos estos números son primos. Los primeros cinco de estos números – 3, 5, 17, 257, y 65,537 – son primos, pero ${displaystyle F_{5}$ es compuesto y todos los demás números de Fermat que se han verificado a partir de 2017. A ordinario ${displaystyle n}$- No. es constructible usando la trama y la brújula si y sólo si los factores principales impares ${displaystyle n}$ (si lo hay) son diferentes primas de Fermat. Del mismo modo, un regular ${displaystyle n}$-gon se puede construir utilizando el trazado, la brújula y un trisector del ángulo si y sólo si los factores principales ${displaystyle n}$ son cualquier número de copias de 2 o 3, junto con un (posiblemente vacío) conjunto de diferentes primos Pierpont, primos de la forma ${displaystyle 2^{a}3^{b}+1}$.

Es posible dividir cualquier polígono convexo en ${displaystyle n}$ polígonos convexos más pequeños de igual área y perímetro igual, cuando ${displaystyle n}$ es un poder de un número primo, pero esto no es conocido por otros valores de ${displaystyle n}$.

Mecánica cuántica

A partir del trabajo de Hugh Montgomery y Freeman Dyson en la década de 1970, matemáticos y físicos han especulado que los ceros de la función zeta de Riemann están conectados con los niveles de energía de los sistemas cuánticos. Los números primos también son importantes en la ciencia de la información cuántica, gracias a estructuras matemáticas tales como bases mutuamente imparciales y medidas simétricas con valor de operador positivo informacionalmente completas.

Biología

La estrategia evolutiva utilizada por las cigarras del género Magicicada hace uso de números primos. Estos insectos pasan la mayor parte de su vida como larvas bajo tierra. Solo pupan y luego emergen de sus madrigueras después de 7, 13 o 17 años, momento en el cual vuelan, se reproducen y luego mueren después de unas pocas semanas como máximo. Los biólogos teorizan que estas longitudes de ciclo de reproducción con números primos han evolucionado para evitar que los depredadores se sincronicen con estos ciclos. Por el contrario, se supone que los períodos de varios años entre la floración en las plantas de bambú son números suaves, que tienen solo pequeños números primos en sus factorizaciones.

Arte y literatura

Los números primos han influido en muchos artistas y escritores. El compositor francés Olivier Messiaen utilizó números primos para crear música amétrica a través de "fenómenos naturales". En obras como La Nativité du Seigneur (1935) y Quatre études de rythme (1949–50), emplea simultáneamente motivos con longitudes dadas por diferentes números primos para crear impredecibles ritmos: los números primos 41, 43, 47 y 53 aparecen en el tercer estudio, "Neumes rythmiques". Según Messiaen, esta forma de componer estaba "inspirada en los movimientos de la naturaleza, movimientos de duraciones libres y desiguales".

En su novela de ciencia ficción Contacto, el científico Carl Sagan sugirió que la factorización prima podría usarse como un medio para establecer planos de imágenes bidimensionales en las comunicaciones con extraterrestres, una idea que primero había desarrollado de manera informal. con el astrónomo estadounidense Frank Drake en 1975. En la novela El curioso incidente del perro a medianoche de Mark Haddon, el narrador organiza las secciones de la historia por números primos consecutivos como una forma de transmitir el estado mental de su personaje principal, un adolescente dotado para las matemáticas con síndrome de Asperger. Los números primos se utilizan como metáfora de la soledad y el aislamiento en la novela La soledad de los números primos de Paolo Giordano, en la que se los retrata como "forasteros" entre enteros.