Número primo

✏️ Editar 🕓 Historial 🔗 Enlaces

Número primo
Definición	Número natural mayor que 1 que tiene exactamente dos divisores positivos: 1 y sí mismo.
Primeros primos	2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, …
Primos menores que 1000	168
Mayor primo conocido	2^136.279.841 − 1 2^136.279.841 − 1^{[sin verificar]}
Cifras decimales	41.024.320^{[sin verificar]}
Anuncio del récord	21 de octubre de 2024^{[sin verificar]}
Área	Teoría de números
Aplicaciones	Criptografía, algoritmos, teoría de números

1. Resumen[editar]

En matemáticas, un número primo es un número natural mayor que 1 que tiene únicamente dos divisores positivos distintos: él mismo y el 1. Dicho de otro modo, un número primo es aquel número natural mayor que 1 que no puede descomponerse como producto de dos números naturales más pequeños, salvo el producto en el que uno de los factores es 1. La propiedad de ser primo se denomina primalidad.

Por el contrario, los números naturales mayores que 1 que poseen algún divisor positivo aparte de sí mismos y del 1 se llaman números compuestos. Por ejemplo, 11 es primo porque sus únicos divisores positivos son 1 y 11. En cambio, 12 es compuesto porque es divisible por 2, 3, 4 y 6, además de por 1 y por sí mismo. El número 1, por convención, no se considera ni primo ni compuesto.

Los 168 números primos menores que 1000 son los siguientes:

[ Desplegar / Plegar ]

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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997.

El primer número primo después de 1000 es 1009; después de 10.000 es 10.007; después de 100.000 es 100.003; e inmediatamente después de un millón es 1.000.003.

El estudio de los números primos es una parte central de la teoría de números. Los primos aparecen como los bloques básicos a partir de los cuales se construyen todos los demás números naturales mediante multiplicación, papel formalizado por el teorema fundamental de la aritmética. También ocupan un lugar destacado en la matemática aplicada moderna: los sistemas de criptografía de clave pública, como RSA, se apoyan directamente en la dificultad de factorizar números grandes en sus factores primos.

En teoría algebraica de números, a los números primos habituales se los llama a veces números racionales primos para distinguirlos de los primos de otros anillos, como los primos gaussianos. La primalidad no depende del sistema de numeración decimal, binario o sexagesimal, pero sí depende del anillo en el que se estudia. Por ejemplo, 2 es primo racional, pero como entero gaussiano admite la factorización 2 = (1 + i)(1 − i), por lo que no es primo gaussiano.

2. Historia[editar]

2.1. Oriente prehelénico[editar]

Hay indicios antiguos, aunque discutidos, de que algunas culturas anteriores a la Grecia clásica reconocieron pares o grupos de números primos. Las muescas presentes en el llamado hueso de Ishango, hallado en la República Democrática del Congo y datado en más de 20.000 años, parecen aislar los números 11, 13, 17 y 19. Algunos arqueólogos interpretan este hecho como una prueba del conocimiento de los números primos; sin embargo, la escasez de hallazgos no permite asegurar con certeza los conocimientos aritméticos de aquella época.^[1]

En Mesopotamia, numerosas tablillas de arcilla del segundo milenio a. C. muestran la resolución de problemas aritméticos y el uso de números inversos. Los escribas babilonios, que empleaban el sistema sexagesimal, necesitaban una comprensión sólida de la multiplicación, la división y la factorización de los números naturales. En las matemáticas egipcias, el cálculo con fracciones egipcias, es decir, sumas de fracciones unitarias de numerador 1, obligaba también a descomponer números y a manejar con soltura los divisores naturales, lo que en cierta manera presupone cierta familiaridad con los números primos.

2.2. Antigua Grecia[editar]

La primera prueba documental clara del conocimiento de los números primos se remonta a los Elementos de Euclides, escritos alrededor del año 300 a. C. En los libros VII a IX, Euclides define los números primos, demuestra que hay infinitos, define el máximo común divisor y el mínimo común múltiplo, y proporciona un método para determinarlos que hoy se conoce como algoritmo de Euclides. Los Elementos contienen asimismo el teorema fundamental de la aritmética y la manera de construir un número perfecto a partir de un número primo de Mersenne.

La criba de Eratóstenes, atribuida a Eratóstenes de Cirene, es un método sencillo para encontrar números primos. Aunque hoy los mayores números primos se obtienen con ordenadores y algoritmos más complejos, la criba sigue siendo uno de los ejemplos didácticos más conocidos de la aritmética elemental.

2.3. Del Renacimiento a la era moderna[editar]

Después de las matemáticas griegas hubo relativamente pocos avances en el estudio de los números primos hasta el siglo XVII. En 1640 Pierre de Fermat estableció, sin demostración, el pequeño teorema de Fermat, demostrado más tarde por Leibniz y Euler. Es posible que un caso particular de ese teorema se conociera mucho antes en China.

Fermat conjeturó que todos los números de la forma 2^(2^n) + 1 eran primos, los hoy llamados números de Fermat, y verificó su propiedad hasta n = 4. Sin embargo, Euler demostró que el número de Fermat correspondiente a n = 5, es decir, 2^32 + 1, es compuesto, ya que uno de sus factores primos es 641. Hasta la actualidad no se conoce ningún número de Fermat primo aparte de los que ya conocía el propio Fermat.^[2]

El monje francés Marin Mersenne investigó los números de la forma 2^p − 1, con p primo, conocidos en su honor como números de Mersenne. Esos números adquirirían siglos después una importancia práctica enorme en la búsqueda de primos cada vez mayores.

Leonhard Euler realizó aportes fundamentales. Demostró la divergencia de la serie de los recíprocos de los números primos y en 1747 probó que todo número perfecto par es de la forma 2^(p−1)(2^p − 1), donde el segundo factor es un número primo de Mersenne. La existencia o inexistencia de números perfectos impares sigue siendo una cuestión abierta.

A comienzos del siglo XIX, Legendre y Gauss conjeturaron de forma independiente que el número de primos menores o iguales que n crece aproximadamente como n/ln(n). Las ideas que Bernhard Riemann expuso en 1859 sobre la función zeta marcaron el camino hacia la demostración del teorema de los números primos, lograda de manera independiente por Jacques Hadamard y Charles-Jean de la Vallée-Poussin en 1896.

Durante los siglos XIX y XX se desarrollaron numerosos algoritmos para comprobar si un número es primo sin necesidad de dividirlo por todos los posibles divisores. En 1856 apareció el test de Lucas-Lehmer para números de Mersenne; en 1877, el test de Pépin para números de Fermat; hacia 1878, el test de Proth; en 1914, el test de Pocklington; y en 1975, el test BLS. Después llegaron métodos de complejidad subexponencial, como el test APRT-CL, el test de primalidad por curvas elípticas y, en 2002, el test de primalidad AKS.

Durante mucho tiempo se pensó que los números primos tenían muy poca aplicación fuera de la matemática pura. Eso cambió en los años 1970 con el desarrollo de la criptografía de clave pública, cuyos primeros algoritmos, como RSA, se basan en la dificultad de factorizar números grandes. Desde 1951, el mayor número primo conocido siempre ha sido encontrado con ayuda de computadoras. En los últimos años, proyectos distribuidos como GIMPS han convertido la búsqueda de primos gigantes en un fenómeno con gran participación voluntaria.

3. Propiedades[editar]

3.1. Teorema fundamental de la aritmética[editar]

El teorema fundamental de la aritmética establece que todo número natural mayor que 1 tiene una representación única como producto de factores primos, salvo el orden de los factores. Por ejemplo, el número 23.244 puede escribirse como 2^2 · 3 · 13 · 149, y cualquier otra descomposición en factores primos será idéntica salvo por el orden.

Los números primos pueden considerarse, por tanto, los «ladrillos» con los que se construye cualquier número natural. La importancia de esta unicidad es una de las razones principales para excluir al 1 del conjunto de los números primos: si se considerara primo al 1, el enunciado del teorema requeriría aclaraciones adicionales, ya que podrían añadirse factores 1 sin cambiar el producto.

A partir de esta unicidad se desarrollan conceptos como el mínimo común múltiplo, el máximo común divisor y la coprimalidad. El mínimo común múltiplo de dos o más números se obtiene descomponiéndolos en factores primos y tomando los factores comunes y no comunes con su máximo exponente. El máximo común divisor se obtiene tomando los factores comunes con su mínimo exponente. Dos números son coprimos, o primos entre sí, si no comparten ningún factor primo; un número primo es coprimo con cualquier número natural que no sea múltiplo de él mismo.

3.2. Propiedades elementales[editar]

En el sistema decimal, todos los números primos salvo el 2 y el 5 terminan en 1, 3, 7 o 9. En general, en cualquier base de numeración, todos los primos salvo un número finito terminan en una cifra coprima con la base.
Todo primo distinto de 2 es de la forma 4n + 1 o 4n + 3. Todo primo distinto de 2 y de 3 es de la forma 6n + 1 o 6n − 1.
Lema de Euclides: si un número primo p divide al producto ab de dos números enteros, entonces p divide a a o divide a b.
Pequeño teorema de Fermat: si p es primo y a es un número natural distinto de 1, entonces a^p − a es divisible por p.
Teorema de Wilson: un número natural n > 1 es primo si y solo si (n − 1)! + 1 es divisible por n.
El anillo Z/pZ es un cuerpo si y solo si p es primo. Equivalentemente, p es primo si y solo si φ(p) = p − 1, donde φ es la función φ de Euler.
La característica de todo cuerpo es cero o un número primo.
La constante de Copeland-Erdős, formada al concatenar los números primos en decimal: 0,235711131719232931374143…, es un número irracional.
La función zeta de Riemann, para Re(s) > 1, admite una representación como producto sobre todos los primos: ζ(s) = Σ 1/n^s = ∏ 1/(1 − p^(−s)). Este producto conecta la distribución de los números primos con el análisis complejo.

4. Distribución de los números primos[editar]

4.1. Infinitud[editar]

Existen infinitos números primos. La primera demostración conocida se debe a Euclides, en el libro IX de los Elementos. Su argumento clásico parte de un conjunto finito arbitrario de primos p1, p2, …, pn y considera el número q = p1 · p2 · p3 · … · pn + 1. Ese número es mayor que 1 y distinto de todos los primos de la lista. Si q es primo, entonces hay un primo fuera del conjunto original. Si q es compuesto, debe tener un factor primo p; si ese p estuviera en la lista original, entonces dividiría también a la diferencia q − p1 · p2 · … · pn = 1, lo cual es imposible. En ambos casos, el conjunto finito no era exhaustivo. Como el razonamiento se aplica a cualquier conjunto finito, el conjunto de todos los primos es infinito.

Si se toma como conjunto inicial el de los n primeros primos, el producto p1 · p2 · … · pn se llama primorial de pn, denotado pn#. Los números primos de la forma pn# + 1 se denominan primos de Euclides. No todos los números de esa forma son primos: por ejemplo, 2 · 3 · 5 · 7 · 11 · 13 + 1 = 30.031 = 59 · 509.

Un resultado más fuerte, demostrado por Euler, es que la serie de los recíprocos de los números primos, 1/2 + 1/3 + 1/5 + 1/7 + …, es divergente. Este enunciado implica la infinitud de los primos. Además, el teorema de Dirichlet asegura que en toda progresión aritmética a + n·q, con a y q enteros positivos coprimos, existen infinitos términos primos.

El postulado de Bertrand afirma que si n es un número natural mayor que 3, siempre existe un número primo p tal que n < p < 2n − 2. Una versión más débil y elegante dice que, si n > 1, siempre hay un primo p tal que n < p < 2n.

4.2. Frecuencia[editar]

Aunque no se puede predecir exactamente la posición de cada primo, su distribución global obedece leyes precisas. La función π(n), que cuenta cuántos primos hay menores o iguales que n, fue estudiada por Gauss y Legendre. El teorema de los números primos, demostrado en 1896 por Hadamard y De la Vallée-Poussin, establece que π(n) es asintóticamente igual a n/ln(n). Posteriormente, en 1949, Selberg y Erdős dieron una demostración con métodos elementales, sin recurrir al análisis complejo.

Gauss propuso como aproximación aún más precisa la función logaritmo integral Li(n). Los valores comparados son:

n	π(n)	π(n) − n/ln n	Li(n) − π(n)	n/π(n)
10	4	−0,3	2,2	2,500
10²	25	3,3	5,1	4,000
10³	168	23	10	5,952
10⁴	1.229	143	17	8,137
10⁵	9.592	906	38	10,425
10⁶	78.498	6.116	130	12,740
10⁷	664.579	44.158	339	15,047
10⁸	5.761.455	332.774	754	17,357
10⁹	50.847.534	2.592.592	1.701	19,667
10¹⁰	455.052.511	20.758.029	3.104	21,975
10¹¹	4.118.054.813	169.923.159	11.586	24,283

La diferencia entre dos primos consecutivos es al menos 2, salvo entre 2 y 3. Si dos primos consecutivos difieren en 2, se llaman primos gemelos, como (3, 5), (5, 7), (11, 13), (17, 19) y (29, 31). No se sabe si existen infinitos pares de primos gemelos; es una de las conjeturas abiertas más conocidas.

Por otro lado, la diferencia entre primos consecutivos puede ser tan grande como se quiera. Dado un número natural n, los n números consecutivos de la forma (n+1)! + i, con 2 ≤ i ≤ n+1, son todos compuestos, porque cada uno es divisible por i. Por ejemplo, para n = 5 se obtiene 6! + 2 = 722, 6! + 3 = 723, 6! + 4 = 724, 6! + 5 = 725 y 6! + 6 = 726, todos compuestos. El siguiente valor, 6! + 7 = 727, es primo.

5. Encontrar números primos[editar]

5.1. Cribas[editar]

La criba de Eratóstenes permite hallar todos los primos menores o iguales que un número dado. Se escribe la lista de números naturales desde 2 hasta ese número y se tachan reiteradamente los múltiplos de los primos ya descubiertos. La criba de Atkin, más moderna, es más compleja pero, si se optimiza adecuadamente, también es más rápida. Existe asimismo la criba de Sundaram, que genera solo números compuestos, de modo que los primos son los números que faltan en la lista.

5.2. Tests de primalidad[editar]

En la práctica interesa saber si un número concreto es primo sin tener que construir una lista completa. El método más simple es la división por tentativa: se divide el número entre los primos menores o iguales que su raíz cuadrada. Si alguna división es exacta, el número es compuesto; si ninguna lo es, el número es primo. Por ejemplo, para n ≤ 120 basta comprobar si es divisible por 2, 3, 5 y 7, porque el siguiente primo, 11, ya supera la raíz cuadrada de 120. El método deja de ser útil para números grandes, porque la cantidad de candidatos crece aproximadamente como √n / ln(√n − 1).

Existen numerosos tests deterministas más eficientes, basados en propiedades que caracterizan a los primos. Algunos, como el test de Lucas-Lehmer para números de Mersenne, son muy rápidos para clases específicas. El test AKS, publicado en 2002, tiene tiempo de ejecución polinómico para cualquier número, pero en la práctica es lento en comparación con los métodos subexponenciales.

También se usan tests probabilísticos, como el test de Miller-Rabin o el test de Solovay-Strassen. Estos métodos no prueban con certeza absoluta que un número sea primo, sino que lo califican como «definitivamente compuesto» o «probablemente primo». Los números compuestos que pasan un test probabilístico se llaman pseudoprimos. Los números de Carmichael, por ejemplo, son compuestos que superan el test de Fermat; el test de Miller-Rabin no presenta ese inconveniente.

5.3. Fórmulas que solo generaran primos[editar]

A lo largo de la historia se han buscado fórmulas que generen números primos. El nivel más alto de exigencia sería una función que asigne a cada natural n el n-ésimo primo. Algunas fórmulas exactas existen, pero son impracticables. Por ejemplo, el teorema de Wilson permite expresar la primalidad de p mediante una congruencia que involucra el factorial (p−1)!, y existen fórmulas como f(n) = 2 + (2(n!) mod (n+1)), que genera todos los primos, solo primos, y únicamente el valor 2 se repite. Sin embargo, su cálculo requiere factoriales, lo que las hace computacionalmente inviables.

Ningún polinomio en una sola variable devuelve solo valores primos. El polinomio f(n) = n² + n + 41, estudiado por Euler, devuelve valores primos para n = 0, 1, …, 39, pero para n = 40 da 40² + 40 + 41 = 41², que es compuesto.

Sí existen polinomios en varias variables cuyos valores positivos, cuando las variables recorren los números naturales, son exactamente los números primos. Un ejemplo famoso es el polinomio de Jones, Sato, Wada y Wiens, publicado en 1976, pero prácticamente solo devuelve valores negativos, por lo que no sirve como generador práctico.

Otro resultado es el teorema de Mills: existe una constante θ tal que la parte entera de θ^(3^n) es siempre un número primo. Sin embargo, no se conoce una fórmula cerrada para esa constante; las aproximaciones actuales dependen de suposiciones no demostradas, como la hipótesis de Riemann.^[3]

6. Clases de números primos[editar]

6.1. Primos de Mersenne[editar]

Los números de Mersenne son los de la forma M_p = 2^p − 1, donde p es un número primo. Los mayores números primos conocidos son, por lo general, de esta forma, porque existe un test de primalidad especialmente eficaz para ellos: el test de Lucas-Lehmer.

Hasta el momento, el mayor número primo conocido es M_136.279.841 = 2^136.279.841 − 1, que tiene 41.024.320^{[sin verificar]} cifras decimales. Se trata cronológicamente del quincuagésimo segundo^{[sin verificar]} primo de Mersenne conocido. Su descubrimiento se anunció el 21 de octubre de 2024^{[sin verificar]} gracias al proyecto de computación distribuida GIMPS.^[4]

6.2. Primos de Fermat[editar]

Los números de Fermat son los de la forma F_n = 2^(2^n) + 1, con n natural. Están ligados a la construcción de polígonos regulares con regla y compás. Los únicos números de Fermat primos conocidos son los cinco que ya conocía el propio Fermat: los correspondientes a n = 0, 1, 2, 3 y 4. Para los valores de n entre 5 y 32 se sabe que los números son compuestos.^[2:1]

6.3. Otras clases[editar]

Existen decenas de subconjuntos de primos con propiedades particulares. Entre ellos:

Primos primoriales: de la forma p = n# ± 1, donde n# es el primorial de n.
Primos factoriales: de la forma p = n! ± 1.
Primos pitagóricos: los que se pueden escribir en la forma 4n + 1.
Primos gemelos: pares de primos separados por 2 unidades.
Primos de Sophie Germain: si p es primo y 2p + 1 también lo es.
Primos de Euclides: de la forma p_n# + 1.
Pseudoprimos: números compuestos que pasan un test de primalidad, como los números de Carmichael.

7. Aplicaciones[editar]

Históricamente, los números primos se consideraron un objeto de la matemática pura con pocas aplicaciones prácticas. Esa percepción cambió con la criptografía de clave pública en los años 1970. Algoritmos como RSA se basan en que multiplicar dos primos grandes es fácil, pero factorizar el producto resultante es computacionalmente difícil. La seguridad de numerosas operaciones en internet, como el comercio electrónico, la banca digital y los mensajes cifrados, depende de esta propiedad.

Los primos también aparecen en la generación de números pseudoaleatorios, en funciones de dispersión, en códigos correctores de errores y en varias ramas de la informática teórica. El algoritmo de Shor, pensado para computadoras cuánticas, permitiría en teoría factorizar números grandes en tiempo polinómico, lo que plantea un horizonte de cambio para la criptografía actual.

8. Presencia en el mundo hispanohablante[editar]

El estudio de los números primos es universal y no se asienta en una región geográfica concreta. En el mundo hispanohablante se usa mayoritariamente la denominación número primo, y la propiedad correspondiente se llama primalidad. El término aparece con regularidad en la enseñanza escolar de matemáticas, en textos universitarios de teoría de números y en divulgación científica.

No hay en este caso una variante regional relevante en español: los términos son estables en América Latina y España. Eventos globales como los anuncios de nuevos récords de GIMPS suelen reproducirse de forma similar en la prensa científica hispanohablante, aunque no constituyen un fenómeno local.

Notas[editar]

El hueso de Ishango fue hallado por el arqueólogo Jean de Heinzelin de Braucourt. Las interpretaciones aritméticas de sus muescas son atractivas, pero existen muy pocos hallazgos que permitan discernir los conocimientos reales de aquella época. ↩︎
Para n = 5, el número de Fermat 2^32 + 1 fue factorizado por Euler al hallar el factor 641. Aunque se han comprobado muchos valores posteriores, no se conoce ningún primo de Fermat nuevo. ↩︎ ↩︎
La constante de Mills se define de forma no constructiva; para calcularla haría falta conocer de antemano los primos que la fórmula genera, lo que reduce su utilidad práctica. ↩︎
La búsqueda del mayor número primo conocido se concentra desde hace años en el proyecto Great Internet Mersenne Prime Search. Los récords se anuncian con el descubrimiento de nuevos primos de Mersenne. ↩︎