Los números primos además de tener un papel señalado en muchas ramas de las matemáticas, ejercen una cierta fascinación sobre algunas personas entre las que me cuento. Además son importantes para algúnos métodos criptográficos como los de clave pública RSA

    Primero la definición: un número primo es un entero positivo mayor que 1 que es divisible sólo por si mismo y la unidad. El resto de los enteros mayores que 1 se llaman compuestos.

    Buena parte de su alcance se debe a un teorema fundamental en la aritmética que nos asegura que cualquier entero positivo se expresa de forma única como producto de primos.

Pequeños números primos

    El algoritmo simplemente hace las divisiones necesarias y es por tanto lento con números "grandes".

     El número debe ser un entero positivo si quieres obtener resultados correctos.

Número
Resultado

    Por si no quieres o puedes calcularlos tu mismo, aquí tienes la lista de los primos del 1 al 10.000 y aquí del 1 al 100.000. También puedes bajarte el programa que usé para generarlas: ejecutable (MS-DOS) y fuente (en C)

Distribución

    Sobre la distribución de estos números podemos hacernos dos preguntas: ¿cuántos hay? ¿están espaciados regularmente?

    A la primera pregunta se contesta que hay infinitos números primos. Una demostración elemental por reducción al absurdo se la debemos a Euclides. En notación moderna sería más o menos así: supongamos que p fuese el último primo, consideramos el número n= p!+1 (p! denotará el factorial de p, es decir p(p-1)(p-2)...1 ). Pues bien n como cualquier número tendrá al menos un factor primo, llamémoslo q. Si q fuese menor que p entonces q divide a p! por definición de factorial, pero entonces q dividiría simultáneamente a los números n y n-1 lo cual es imposible. Es decir que q>p en contra de la hipótesis de que p es el mayor.

    En cuanto a como están distribuidos diremos en primer lugar que son cada vez más escasos a medida que crece su tamaño pudiendo encontrar "rachas" tan grandes como queramos sin números primos. A la vez se conjetura que existen infinitos pares de primos gemelos (p y p+2 como por ejemplo 11 y 13).

    Más exactamente se demuestra que el número de primos menores que x denotado PI(x) (aquí tendría que haber la letra griega PI, ya me entendéis) se aproxima asintóticamente a x/Ln x. La demostración de este hecho la debemos independientemente a Hadamard y de la Vallée Poussin. Una aproximación mejor aún a PI(x) es la integral entre 2 y x de dt/Ln t. Si llamamos a esta función LI(x) observemos en una tabla el número real de primos menores que x en comparación con LI(x) y x/Ln x:

x	PI(x)	x/Ln x	PI(x)/ (x/Ln x)	LI(x)	PI(x)/ LI(x)
10^3	168	145	1'160	178	0'947820
10^6	78.498	72.382	1'085	78.628	0'998347
10^9	50.847.534	48.254.942	1'054	50.849.235	0'999966
10^12	37.607.912.018	36.191.206.825	1'039	37.607.950.281	0'999999

Otros resultados sobre la distribución de primos

Clases especiales de números primos

Números de Fermat: son de la forma 22k+1, Fermat conjeturó que todos eran primos y de hecho {3,5,17,257,65.537} , los cinco primeros lo son pero desde el 6º hasta el 17º no lo son, ni muchos otros posteriores. Se ignora si hay más primos en esta serie.

Números de Mersenne: son de la forma 2k-1 y aparecen al estudiar los números perfectos (iguales a la suma de sus divisores propios). Sólo pueden ser primos si k lo es. Se conocen gracias al ordenador un buen número de ellos. Los mayores primos conocidos son de esta forma; por ejemplo en el 2001 se calculó el mayor conocido, que es 2^13466917 - 1 , ¡un primo con 4.053.946 dígitos nada menos!

Aún sin resolver

    La teoría de números primos presenta varios problemas fáciles de plantear pero muy difíciles de resolver. Por ejemplo:

Test avanzado de primalidad

    Determinar si un número es primo haciendo todas las divisiones hasta la raíz cuadrada como se hace en la calculadora de esta página es un método muy ineficiente, aunque elemental, especialmente para grandes primos (digamos mayor que 10.000.000). Dado que en algoritmos como RSA se necesitan primos de cien dígitos o mas necesitamos hacer algo mejor.

Definición

     Sea n un entero positivo con n-1 = 2s.t , siendo s un entero no negativo y t un entero positivo impar. Decimos que n pasa el test de Miller en la base b si bt = 1 (mod n) o bien que b2j.t = -1 (mod n) para algún j, con 0<= j <= s-1.

    Ahora bien, puede demostrarse que un número primo pasa el test de Miller para todas los enteros menores que él. Los números compuestos que pasan el test de Miller, aunque extraordinariamente raros son infinitos en cantidad.

Definición

     Los números compuestos que pasan el test de Miller para la base b se denominan pseudoprimos fuertes en base b.

    Para centrar ideas: si un entero no pasa el t. de M. para algúna base b entonces es automáticamente compuesto y en otro caso podría ser primo.

    A algúnos resultados experimentales junto con el test de Miller constituyen un test rápido de primalidad para enteros relativamente pequeños.

(Datos de la página de Chris Caldwell) Ahora bien para números aún mayores utilizaremos el siguiente

Test probabilístico de primalidad de Rabin

    Sea n un entero positivo, tomemos k diferentes enteros positivos menores que n y realizaremos el test de Miller para cada uno de ellos. Si n es compuesto la probabilidad de que los pase todos es menor que (1/4)k.

    Bien, este test no nos dice que un número es primo sino que lo es con tanta certeza como nosotros deseemos (según el número de pruebas realizadas). Por ejemplo, tomando 100 bases al azar entre 1 y n, la probabilidad de que n pase todos los tests siendo compuesto es de sólo 10-60, un número pequeñísimo. De hecho es más creíble que el ordenador haya cometido un error en los cálculos (especialmente usando un Pentium-TM :-) ) que no que el número sea compuesto.

Referencias