El tamiz de Eratóstenes es una rutina para compilar una tabla de números primos descubierta por el matemático griego Eratóstenes en el siglo III a.C. Ésta permite hallar todos los números primos menores que un número dado N.
Primero, escribimos todos los números menores que N (excepto 1). Por ejemplo, si suponemos que queremos hallar todos los números primos menores que 49, escribimos los números del 2 al 48.
Tomamos entonces el primer número primo, que es 2, y tachamos todos sus
A continuación, tachamos todos los múltiplos del siguiente número primo, 3, que permanece en la tabla, empezando con
Seguimos este proceso, borrando todos los múltiplos de los siguientes números primos, hasta llegar al último número primo antes de √N. En nuestro ejemplo,
Los números que han permanecido sin tachar son todos los números primos menores de 49, como se muestra en el diagrama 4.
Podemos utilizar este método para encontrar todos los números primos menores de 100 (ver diagrama 5).
El teorema fundamental de la aritmética afirma que cualquier número compuesto se puede escribir como un
tiene dos factores repetidos, el 2 y el 5.
Este teorema significa que los números primos pueden ser contemplados como las piezas de construcción
para los enteros. Puede parecer razonable pensar, entonces, que debería haber algún tipo de modelo que determinara qué números son primos. Sin embargo, tal modelo no existe.
Si miramos los enteros pequeños, parece que los números primos son muy comunes. Por ejemplo, la mitad de los números de 2 al 11 son primos, el 2, 3, 5, 7 y 11. Tres de los siguientes diez números, del 12 al 21, son primos (13, 17, y 19), una proporción del 30 por ciento. De los primeros cien enteros, el 16,8 por ciento son números primos, mientras que, en el primer millón de enteros, el 7,85 por ciento son primos. Por ello parece razonable suponer que los números primos son menos frecuentes cuando mayores son los números.
El teorema de los números primos nos dice cuántos números primos es probable que haya menores o iguales que un cierto valor n. El teorema afirma que la proporción de enteros positivos menores que o iguales a n que son números primos tiende a 1/lm n cuando n aumenta (donde lm n es el
Hay un número infinito de números primos. Esto se puede demostrar estableciendo que no hay ningún número primo que sea el mayor.
Primeramente, supongamos que pn sea el mayor número primo, y que p1, p2, …, pn-1 son todos los números primos menores que pn. En otras palabras,
A continuación, consideremos el número N formado al multiplicar todos los números primos hasta pn entre sí y añadiendo 1. En otras palabras,
Podemos ver que el número
Los primeros intentos de hallar un modelo de la distribución de los primos, se concentraron en hallar una fórmula algebraica que diera como resultado siempre un número primo. Marin Mersenne, un monje francés del siglo XVII, investigó los números de la forma
donde p es un número primo. Los números de esta forma se denominaron posteriormente números de Mersenne. Él afirmó que estos números serían primos si p fuera 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 o 257, y números compuestos para todos los otros valores de p menores de 257. No fue posible comprobar esto hasta 1947 cuando las calculadoras estuvieron disponibles. A pesar de cometer algunos errores, Mersenne fue en general muy exacto.
Los números de Mersenne proporcionan una manera de producir algunos números primos espectacularmente grandes, tales como
Dos teoremas famosos que involucran números primos son: (1) el teorema de