thumb|400px|Números naturales de cero a cien. Los números primos están marcados en rojo. thumb|400px|La distribución de los números primos (trazos azules) hasta el 400 En matemáticas, un número primo es un número natural mayor a 1 que tiene únicamente dos divisores positivos distintos: él mismo y el 1.Niven y Zuckerman: Introducción a la teoría , Editorial Trillas. México D. F., pág. 55 Por el contrario, los números compuestos son los números naturales que tienen algún divisor natural aparte de sí mismos y del 1, y, por lo tanto, pueden factorizarse. El número 1, por convenio, no se considera ni primo ni compuesto.
Los 168números primos menores que 1000 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, 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 y 997 .
El primer número primo a partir del número mil es el 1009, después de diez mil es el , a partir de cien mil es el e inmediatamente tras un millón es el .
La propiedad de ser número primo se denomina primalidad.
En la teoría algebraica de números, los números primos se denominan números racionales primos para distinguirlos de los números gaussianos primos.Niven- Zuckerman. Introducción a la teoría de números La primalidad no depende del sistema de numeración, pero sí del anillo donde se estudia la primalidad. Dos es primo racional; sin embargo tiene factores como entero gaussiano: 2 = (1+i)*(1-i).
El estudio de los números primos es una parte importante de la teoría de números, rama de las matemáticas que trata las propiedades, básicamente aritméticas,Abramo Hefez: Curso de álgebbra vol.1, ISBN 9972-9394-1-3, pág. 87 de los números enteros.
Los números primos están presentes en algunas conjeturas centenarias tales como la hipótesis de Riemann y la conjetura de Goldbach, resuelta por Harald Helfgott en su forma débil.
La distribución de los números primos es un asunto reiterativo de investigación en la teoría de números: si se consideran números aisladamente, los primos parecieran estar distribuidos de modo probabilístico, pero la distribución «global» de los números primos se ajusta a leyes bien definidas.
Historia El Oriente prehelénico thumbnail|150px|Imagen del hueso de Ishango expuesto en el Real Instituto Belga de Ciencias Naturales.
Las muescas presentes en el hueso de Ishango, que data de hace más de (anterior por tanto a la aparición de la escritura) y que fue hallado por el arqueólogo Jean de Heinzelin de Braucourt,Marcus du Sautoy, La symphonie des nombres premiers P.42 (en francés) parecen aislar cuatro números primos: 11, 13, 17 y 19. Algunos arqueólogos interpretan este hecho como la prueba del conocimiento de los números primos. Con todo, existen muy pocos hallazgos que permitan discernir los conocimientos que tenía realmente el hombre de aquella época.Préhistoire de la géométrie: le problème des sources, artículo de Olivier Keller (en francés)
Numerosas tablillas de arcilla cocida atribuidas a las civilizaciones que se fueron sucediendo en Mesopotamia a lo largo del II milenio a.C. muestran la resolución de problemas aritméticos y atestiguan los conocimientos de la época. Los cálculos requerían conocer los inversos de los naturales, que también se han hallado en tablillas. En el sistema sexagesimal que empleaban los babilonios para escribir los números, los inversos de los divisores de potencias de 60 (números regulares) se calculan fácilmente; por ejemplo, dividir entre 24 equivale a multiplicar por 150 (2·60+30) y correr la coma sexagesimal dos lugares. El conocimiento matemático de los babilonios necesitaba una sólida comprensión de la multiplicación, la división y la factorización de los naturales.
En las matemáticas egipcias, el cálculo de fracciones requería conocimientos sobre las operaciones, la división de naturales y la factorización. Los egipcios solo operaban con las llamadas fracciones egipcias, suma de fracciones unitarias, es decir, aquellas cuyo numerador es 1, como , por lo que las fracciones de numerador distinto de 1 se escribían como suma de inversos de naturales, a ser posible sin repetición en lugar de . Es por ello que, en cierta manera, tenían que conocer o intuir los números primos.
Antigua Grecia 230px|thumb|right|Un fragmento de los Elementos de Euclides encontrado en Oxirrinco La primera prueba indiscutible del conocimiento de los números primos se remonta a alrededor del año y se encuentra en los Elementos de Euclides (tomos VII a IX). Euclides define los números primos, demuestra que hay infinitos de ellos, define el máximo común divisor y el mínimo común múltiplo y proporciona un método para determinarlos que hoy en día se conoce como el 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 que permite encontrar números primos. Hoy en día, empero, los mayores números primos que se encuentran con la ayuda de ordenadores emplean otros algoritmos más rápidos y complejos.
Desde la época del Renacimiento 230px|thumb|Pierre de Fermat Después de las matemáticas griegas hubo pocos avances en el estudio de los números primos hasta el siglo . En 1640 Pierre de Fermat estableció (aunque sin demostración) el pequeño teorema de Fermat, posteriormente demostrado por Leibniz y Euler. Es posible que mucho antes se conociera un caso especial de dicho teorema en China.
Fermat conjeturó que todos los números de la forma 22n+1 eran primos (debido a lo cual se los conoce como números de Fermat) y verificó esta propiedad hasta n = 4 (es decir, 216 + 1). Sin embargo, el número de Fermat 232 + 1 es compuesto (uno de sus factores primos es 641), como demostró Euler. De hecho, hasta nuestros días no se conoce ningún número de Fermat que sea primo aparte de los que ya conocía el propio Fermat.
El monje francés Marin Mersenne investigó los números primos de la forma 2p − 1, con p primo. En su honor, se los conoce como números de Mersenne.
En el trabajo de Euler en teoría de números se encuentran muchos resultados que conciernen a los números primos. Demostró la divergencia de la serie , y en 1747 demostró que todos los números perfectos pares son de la forma 2p-1(2p - 1), donde el segundo factor es un número primo de Mersenne. Se cree que no existen números perfectos impares, pero todavía es una cuestión abierta.
A comienzos del siglo , Legendre y Gauss conjeturaron de forma independiente que, cuando n tiende a infinito, el número de primos menores o iguales que n es asintótico a , donde ln(n) es el logaritmo natural de n. Las ideas que Bernhard Riemann plasmó en un trabajo de 1859 sobre la función zeta describieron el camino que conduciría a la demostración del teorema de los números primos. Hadamard y De la Vallée-Poussin, cada uno por separado, dieron forma a este esquema y consiguieron demostrar el teorema en 1896.
Actualmente no se comprueba la primalidad de un número por divisiones sucesivas, al menos no si el número es relativamente grande.
Durante el siglo se desarrollaron algoritmos para saber si un número es primo o no factorizando completamente el número siguiente (p+1) o el anterior (p-1). Dentro del primer caso se encuentra el test de Lucas-Lehmer, desarrollado a partir de 1856. Dentro del segundo caso se encuentra el test de Pépin para los números de Fermat (1877). El caso general de test de primalidad cuando el número inmediatamente anterior se encuentra completamente factorizado se denomina test de Lucas.
Posteriormente se encontraron algoritmos de primalidad con solo obtener una factorización parcial de p+1 o p-1. Ejemplos de estos algoritmos son el test de Proth (desarrollado alrededor de 1878) y el test de Pocklington (1914). En estos algoritmos se requiere que el producto de los factores primos conocidos de p-1 sea mayor que la raíz cuadrada de p. Más recientemente, en 1975, Brillhart, Lehmer y Selfridge desarrollaron el test de primalidad BLS que solo requiere que dicho producto sea mayor que la raíz cúbica de p. El mejor método conocido de esta clase es el test de Koniaguin y Pomerance del año 1997, que requiere que dicho producto sea mayor que p3/10.
A partir de la década de 1970 varios investigadores descubrieron algoritmos para determinar si cualquier número es primo o no con complejidad subexponencial, lo que permite realizar tests en números de miles de dígitos, aunque son mucho más lentos que los métodos anteriores. Ejemplos de estos algoritmos son el test APRT-CL (desarrollado en 1979 por Adleman, Pomerance y Rumely, con mejoras introducidas por Cohen y Lenstra en 1984), donde se usan los factores de pm-1, donde el exponente m depende del tamaño del número cuya primalidad se desea verificar, el test de primalidad por curvas elípticas (desarrollado en 1986 por S. Goldwasser, J. Kilian y mejorado por A. O. L. Atkin), que entrega un certificado consistente en una serie de números que permite después confirmar rápidamente si el número es primo o no. El desarrollo más reciente es el test de primalidad AKS (2002), que si bien su complejidad es polinómica, para los números que puede manejar la tecnología actual es el más lento de los tres.
Durante mucho tiempo, se pensaba que la aplicación de los números primos era muy limitada fuera de la matemática pura. Esto cambió en los años 1970 con el desarrollo de la criptografía de clave pública, en la que los números primos formaban la base de los primeros algoritmos, tales como el algoritmo RSA.
Desde 1951, el mayor número primo conocido siempre ha sido descubierto con la ayuda de ordenadores. La búsqueda de números primos cada vez mayores ha suscitado interés incluso fuera de la comunidad matemática. En los últimos años han ganado popularidad proyectos de computación distribuida tales como el GIMPS, mientras los matemáticos siguen investigando las propiedades de los números primos.
El número 1 no se considera primo
La cuestión acerca de si el número 1 debe o no considerarse primo está basada en la convención. Ambas posturas tienen sus ventajas y sus inconvenientes. De hecho, hasta el siglo , los matemáticos en su mayoría lo consideraban primo. Muchos trabajos matemáticos siguen siendo válidos a pesar de considerar el 1 como un número primo, como, por ejemplo, el de Stern y Zeisel. La lista de Derrick Norman Lehmer de números primos hasta el 10.006.721, reimpresa hasta el año 1956,Hans Riesel, Prime Numbers and Computer Methods for Factorization. New York: Springer (1994): 36 (en inglés) empezaba con el 1 como primer número primo.Richard K. Guy & John Horton Conway, The Book of Numbers. New York: Springer (1996): 129 - 130 (en inglés)