Números primos

Fecha de primera versión: Marzo 1997
Fecha de última actualización: 19/04/2010

Una de las cuestiones básicas en la teoría de números es la cuestión de la divisibilidad de un número por otro. Los números enteros que sólo son divisibles por 1 y por si mismos, se llaman números primos.

El número de números primos es infinito. El primero que lo demostró fue Euclides, en el Libro IX de Elementos, después lo demostraron Euler y Chebichev. La demostración es muy sencilla: Supongamos que tenemos un conjunto {p1, p2, p3, ...} que incluye todos los números primos. Calculemos el número N = p1.p2.p3 ... + 1. Evidentemente este número es primo porque no es divisible por ninguno de los números primos que hemos considerado. Por lo tanto, el conjunto del que hemos partido no incluye todos los números primos.

Los números primos son, en cierto modo, como los elementos químicos. A partir de los elementos químicos se forman todos los compuestos químicos y a partir de los números primos podemos obtener el resto de los números.

Sería fantástico que hubiese una fórmula que produjese números primos. Hasta 1536 se pensó que los números de la forma 2n-1 eran todos primos, pero ese año Hudalricus Regius, demostró que 211 - 1 = 2047 era el producto de 23 y 89. Sin embargo, muchos (se supone que infinitos) números primos cumplen esa condición. A los números primos que cumplen esa condición se les llama números primos de Mersenne (Marin Mersenne (1588-1648) fue un monje francés, muy famoso en su época). Mersenne en su libro Cogitata Physica-Mathematica dijo que los números de la forma 2n - 1 eran primos para n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 y 257 y compuestos para los restantes números < 257.

Euler en 1750 lo demostró para n = 31, Lucas, en 1876 lo demostró para n = 127. Años mas tarde Pervouchine encontró que también era primo el número para n = 61 y en 1900 Powers descubrió que también lo eran para n = 89 y n = 107.

Los números primos de Mersenne y los números perfectos están relacionados. Los números primos de Mersenne son de la forma 2n - 1 y los perfectos son de la forma 2n - 1(2n - 1).

Hasta hoy (07-12-01) se han descubierto 39 números de Mersenne, el último es 213466917 - 1 descubierto por el GIMPS (Great Internet Mersenne Prime Search) el 14 de noviembre de 2001.

Tabla de números primos de Mersenne conocidos
Número de orden Exponente Año descubrimiento Descubridor
1 2    
2 3    
3 5    
4 7    
5 13 1456 Anónimo
6 17 1588 Cataldi
7 19 1588 Cataldi
8 31 1772 Euler
9 61 1883 Pervushin
10 89 1911 Powers
11 107 1914 Powers
12 127 1876 Lucas
13 521 1952 Robinson
14 607 1952 Robinson
15 1279 1952 Robinson
16 2203 1952 Robinson
17 2281 1952 Robinson
18 3217 1937 Riesel
19 4253 1961 Hurwitz
20 4423 1961 Hurwitz
21 9689 1963 Gillies
22 9941 1963 Gillies
23 11213 1963 Gillies
24 19937 1971 Tickerman
25 21701 1978 Noll y Nickel
26 23209 1979 Noll
27 44497 1979 Nelson y Slowinski
28 86243 1982 Slowinski
29 110503 1988 Colquitt y Welsh
30 132049 1983 Slowinski
31 216091 1985 Slowinski
32 756839 1992 Slowinski y Gage
33 859433 1994 Slowinski y Gage
34 1257787 1996 Slowinski y Gage
35 1398269 1996 GIMPS
36 2976221 1997 GIMPS
37 3021377 1998 GIMPS
38 6972593 1999 GIMPS
39 13466917 2001 GIMPS

Si quieres saber más sobre los números primos de Mersenne visita esta página http://www.mersenne.org/prime.htm

Pierre de Fermat (1601-1665) creyó haber encontrado una fórmula que producía números primos Fi = 2n + 1 siendo n = 2i , esta fórmula genera números primos para i = 0, 1, 2, 3 y 4. Leonhard Euler (1707-1783) descubrió que F5 no es primo, en 1880 se demostró que F6 tampoco lo es, en 1970 se demostró que tampoco lo era F7, en 1980 se demostró para F8 y en 1990 para F9.

Algunos números primos están separados sólo por un número par (p.e. el 3 y el 5). A estos números se les llama números primos gemelos. Por lo tanto la cantidad mínima de números entre dos números primos es uno. ¿Cuál será la cantidad máxima? La respuesta es la que queramos: Si nos piden construir 1000 números consecutivos que no sean primos, sólo tenemos que hacer la siguiente operación: 1001! + 2, 1001! + 3, 1001! + 4,... 1001! + 1001.

Los diez primos gemelos más grandes

Número primo Número de dígitos Año descubrimiento
33218925.2169690±1 51090 2002
318032361.2107001±1 32220 2001
1807318575.298305±1 29603 2001
665551035.280025±1 24099 2000
781134345.266445±1 20011 2001
1693965.266443±1 20008 2000
83475759.264955±1 19562 2000
291889803.260090±1 18098 2001
4648619711505.260000±1 18075 2000
2409110779845.260000±1 18075 2000

 Sólo hay tres números primos contiguos: 3, 5 y 7.

Se dice que dos números son primos entre sí (también se llaman primos relativos) cuando no son divisibles entre si (dicho más matemáticamente, cuando el máximo común divisor de dichos números es 1). Ejemplo, los números 38 y 14 son primos entre sí.

Dado un número a, se llama conjunto reducido de restos, al conjunto de números menores que a, que son primos entre sí con el número a. Ejemplo: el conjunto reducido de restos de 14 es {1,3,4,5,6,8,9,10,11,12,13}.

La función de Euler de un número n (se representa por j (n)), da el número de elementos que forman el conjunto reducido de restos. En nuestro ejemplo j (14) = 11.

Los diez números primos más grandes

Número primo Número de dígitos Año descubrimiento
213466917-1 4053946 2001
26972593-1 2098960 1999
23021377-1 909526 1998
22976221-1 895932 1997
21398269-1 420921 1996
136184665536+1 402007 2002
126606265536+1 399931 2002
5.21320487+1 397507 2002
105747665536+1 394807 2002
85767865536+1 388847 2002

¿Cómo se distribuyen los números primos?

Se utiliza p (x) para representar el número de primos menor que o igual a x. La distribución es la siguiente:

Distribución de números primos
X p (x) p (x)/x p (x) er(x)
10 4 0,40 2,5 12,182494
100 25 0,25 4,0 54,598150
1000 168 0,168 5,95238095 384,668125
10000 1229 0,1229 8,13669650 3417,609
100000 9592 0,09592 10,4253545 33703,4168
1000000 78498 0,078498 12,7391781 340843,2932
10000000 664579 0,06645790 15,0471201 3426740

Si observamos la última columna vemos que cuando x es grande cada número de esa columna es aproximadamente 10 veces el anterior.

Esto se puede expresar matemáticamente de esta forma: (cuando x es grande). De aquí se deduce el teorema de los números primos:

(cuando x es grande)

Dicho en lenguaje llano: la proporción de primos entre enteros es aproximadamente igual al inverso de ln x cuando x es grande.

Puede parecer increíble que alguien descubra esta relación, sin embargo, esta relación la descubrió Carl Friedrich Gauss cuando tenía 14 años.

Si p y 2p+1 son primos, a p se le llama número primo de Sofia Germain.

Un número es casi primo si sólo tiene dos divisores primos. Por ejemplo 21 es casi primo, porque solo es divisible por 3 y 7.

En 1978 Ronald Rivest, Adi Shamir y Leonard Adlermann desarrollaron un método para cifrar mensajes (llamado RSA por las iniciales de sus apellidos) basándose en los números casi primos.

Este método consiste en seleccionar dos números primos, p y q (suficientemente grandes, de centenas de dígitos) y obtener su producto n = pq. Podemos hacer público el número n (sería la clave pública) porque es muy difícil obtener los factores p y q.

Para hacer más difícil la descomposición en factores primos del número n, se eligen p y de tal forma que cumplan las siguientes condiciones:

1- El mcd de p - 1 y q - 1 pequeño.

2- La descomposición en factores primos de p - 1 y q - 1 debe tener algún factor primo grande p' y q'.

3- La descomposición en factores primos de p' - 1 y q' - 1 deben tener factores primos grandes.

4- La descomposición en factores primos de p' + 1 y q' + 1 deben tener factores primos grandes.

Los números primos p y q que cumplen estas cuatro condiciones se llaman números primos fuertes.

La clave privada sería otro número m (es conveniente que este número sea primo también) (de centenas de dígitos) que cumple la siguiente condición:

mcd (m,(p-1).(q-1)) = 1 (el máximo común divisor de m y el producto (p-1)(q-1) es 1).

Para cifrar una texto se convierten las letras a números mediante una tabla, a continuación se forman bloques de números y elevamos ese número a la m y lo dividimos por n y nos quedamos con el resto. Después convertimos ese resto a las letras resultantes.

¿Cómo averiguar si un número es primo?

No es fácil saber si un número es primo.

Método de la criba de Eratóstenes

Consiste en construir una tabla con todos los números y a continuación, empezando por el 2 tachamos todos los números que estén a una distancia de 2 (el 4, 6, 8, etc.) después seguimos con el 3 tachando todos los números que estén a una distancia de 3 (el 6, 9, 12, etc) y así sucesivamente. 

Método de división a prueba

Consiste en dividir n por todos los números primos anteriores a n. En realidad basta con calcular los números primos anteriores a raíz cuadrada de n.

Calculadora de números primos

Método de Fermat

El pequeño teorema de Fermat dice que si p es primo y a es un entero ap = a (mod p). Dicho en palabras claras: El resto de dividir ap entre p y el resto de dividir a entre p son iguales.  

Dividiendo ap = a (mod p) por a nos queda ap-1 = 1 (mod p), que es la forma que se utiliza para probar si un número es primo.

Sea p el número que queremos saber si es primo. Si ap-1 = 1 (mod p) luego p puede ser primo (ojo puede que no lo sea). Si cumple la prueba se dice que p es probable primo base a (a-PRP).  

Los números que pasan la prueba pero no son primos se llaman pseudoprimos. Por ejemplo 341 pasa la prueba 2-PRP pero es compuesto (341 = 11.31).

Vamos a ver que cumple la prueba: 2340 = 1 (mod 341). 2340 = 210.210 ... 210 (34 veces) . El resto de dividir 210 (1024) entre 341 es 1, luego el resto de dividir 2340 entre 341 es 1.1... 1 (34 veces)= 1. Luego cumple la prueba pero 341 no es primo.

Esta prueba es bastante buena. Hay 1.091.987.405 primos entre el 1 y 25.000.000.000, pero sólo hay 21.853 pseudoprimos que pasen la prueba 2-PRP. 

Cuando se prueba si un número es primo con este método, se hace la prueba con varias bases (2-PRP, 3-PRP, 5-PRP,...)

Este teorema (pequeño teorema de Fermat) también se llama teorema de Euler-Fermat, se utiliza en problemas de este tipo:

Calcular el resto de dividir 31895243 entre 13.

De la aplicación del teorema deducimos que 3112=1 (mod 13).

895243 = 74603 * 12 + 7.

31895243 = 31(74603*12 +7)= (3112)74603 * 317

Recordemos que queremos calcular el resto de dividir este número entre 13. El resto será el producto de los restos de los dos factores.

Como el resto de dividir 3112 entre 13 es 1, el resto del primer factor será 1, por lo tanto el resto de (3112)74603 * 317 será el resto de 317 . Vamos a calcular el resto de dividir 317 entre 13.

Como 31 = 13*2 + 5, 57 tendrá el mismo resto que 317 al dividirlo por 13.

Vamos a calcular el resto de dividir 57 entre 13. Como 7 = 4 + 2 + 1, 57 = 54*52*5

El resto de 5/13 es 5

El resto de 52/13 es 12 (o -1)

El resto de 54/13 es 1

El resto de 54*52*5 será 1*12*5 = 1*(-1)*5 = -5 = 8

Un método mejor que a-PRP es a-SPRP (strong probable prime).  Este método es una consecuencia del anterior. Consiste en calcular la raíz cuadrada a la expresión ap-1 = 1, y obtendríamos a(p-1)/2 = ±1.

Haciendo p - 1 = 2sd, siendo d un número impar y s positivo, decimos que p es a-SPRP si cumple una de estas condiciones:

ad = 1 (mod p) 

(ad)2^r = -1 para algún r < s

Como en la prueba a-PRP, algunos números pasan la prueba a-SPRP y no son primos, por ejemplo, 2047 pasa la prueba 2-SPRP y es compuesto (23.89), pero son muy pocos.

Por ejemplo: 

Si p < 1.373.653 y pasa las pruebas 2-SPRP y 3-SPRP, p es primo.
Si p < 25.326.001 y pasa las pruebas 2-SPRP, 3-SPRP y 5-SPRP, p es primo.
Si p < 341.550.070.728.321 y pasa las pruebas 2-SPRP, 3-SPRP, 5-SPRP, 7-SPRP, 11-SPRP, 13-SPRP y 17-SPRP, p es primo.

Método de la prueba p-1

Una característica de los números primos grandes es que en casi todos, el número anterior o el siguiente se factorizan muy fácilmente. 

Se basa en el siguiente teorema:

Sea p > 1. Si para factor primo q de p - 1, existe un entero a tal que:

ap-1 = 1 (mod p) y a(p-1)/q no = 1 (mod p), luego p es primo.

Método de la prueba p+1

Una característica de los números primos grandes es que en casi todos, el número anterior o el siguiente se factorizan muy fácilmente. 

Sean p y q enteros, tales que p2 - 4q no es un cuadrado módulo n.
Una de las soluciones de x2 - px + q = 0 es r = (p + sqr(p2 - 4q))/2.
Las potencias de r tienen la forma:

rm = (V(m) + U(m)sqr(p2 - 4q))/2 donde U y V se definen recursivamente de esta forma:

U(0) = 0, U(1) = 1, ... U(m) = pU(m - 1) - qU(m - 2)
V(0) = 2, V(1) = p, ... V(m) = pV(m - 1) - qV(m - 2)

Estas secuencias se llaman secuencias de Lucas asociadas a p y q.  Para el caso, p = 1, q = -1, la secuencia U es la serie de Fibonnaci. 

Una propiedad importante de estas secuencias es esta:

U(2m) = U(m)V(m)
V(2m) = V(m)2 - 2qm

Sea 2r = a + b sqr(p2 - 4q) mod(n). Si n es primo 2r n = a - b sqr(p2 - 4q) mod(n).

Si existe un entero d, para el cual el símbolo de Jacobi (d|n) = -1 y para todos los factores primos r de n + 1, existen primos relativos p y q que cumplen:

p2 - 4q = d
U(n + 1) = 0 (mod n)
U((n + 1)/r) no es 0 (mod n)

entonces n es primo.

Método de las curvas elípticas:

Este método realiza una operación que sólo da resultado si n es primo (cuando n es compuesto la operación falla).

Una curva elíptica E(a,b) tiene la ecuación y2 = x3 + ax + b (siendo 4a3 + 27b2 no cero).

Se llaman curvas elípticas porque se presentaron por primera vez, en la resolución del cálculo de la longitud de arcos de elipses.

Método de la criba cuadrada:

Se trata de hallar números naturales x e y con la propiedad de que n sea un divisor de x2-y2.

Problemas no resueltos.

¿Hay infinitos números primos de Mersenne?

Sean p y 2p + 1 primos. ¿Hay infinitos pares de números primos que cumplan esta condición?

¿Hay infinitos números primos gemelos? Primos gemelos son los que están separados sólo por un número. Por ejemplo: 3 y 5.

¿Hay infinitos números primos obtenidos sumando 1 a un número elevado al cuadrado?

¿Siempre hay un número primo entre dos números cuadrados consecutivos?

¿Todo número par mayor de 2 se puede obtener como suma de dos números primos? (Esta es la conjetura de Goldbach)

¿Existe algún número primo de Fermat mayor de 65537?

¿La serie de Fibonacci contiene infinitos números primos?

¿Existen infinitos números primos de la forma n! + 1 o n! - 1?

¿Existen infinitos números primos de la forma n# + 1 o n# - 1? Siendo n# el producto de todos los números primos menores o iguales a n.

Links

En estas páginas puedes encontrar mucha información sobre los números primos:

www.utm.edu/research/primes/index.html
http://www.mersenne.org/prime.htm