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, después lo demostraron Euler y Chebichev.
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 estan 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 (11-07-99) se han descubierto 38 números de Mersenne, el último es 26972593 - 1 descubierto por el GIMPS (Great Internet Mersenne Prime Search).
|
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 |
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 estan 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. ¿Cúal 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.
Sólo hay tres números primos contiguos: 3, 5 y 7.
Se dice que dos números son primos entre sí (tambien se llaman primos relativos) cuando no son divisibles entre si (dicho más matemáticamente, cuando el mácimo 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.
Se utiliza p (x) para representar el número de primos menor que o igual a x. La distribución es la siguiente:
|
X |
p (x) |
p (x)/x |
r(x)=x/p (x) |
er(x) |
|
10 |
4 |
0,40 |
2,5 |
12,182494 |
|
100 |
25 |
0,25 |
4 |
54,598150 |
|
1000 |
168 |
0,168 |
5,95238095 |
384,668125 |
|
10000 |
1229 |
0,1229 |
8,13669650 |
3417,609/TD> |
|
100000/TD> |
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)
Dicho en lenguaje llano: la proporción de primos entre enteros es aproximadamente igual al inverso de ln x cuando x es grande.
Puede aprecer increible 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 algun 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 tambien) (de centenas de dígitos) que cumple la siguiente condición:
mcd(m,(p-1).(q-1)) = 1 (el máximo comun 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. Despues convertimos ese resto a las letras resultantes.
No es facil saber si un número es primo.
Método de Fermat:Se comprueba si n (que es el número del que queremos saber si es primo) es divisor del número 2(n-1) -1.
Método de división a prueba (criba de Eratostenes):Consiste en dividir n por todos los números primos anteriores a n. En realidad basta con calcular los números primos anteriores a raiz cuadrada de n.
Método de las curvas elípticas:
Este método realiza una operacion que sólo da resultado si n es primo (cuando n es compuesto la operación falla).
Método de la criba cuadrada:Se trata de hallar numeros naturales x e y con la propiedad de que n sea un divisor de x2-y2.
Este teorema dice que a(p-1) = 1 (mod p) si p es primo y a y p son primos entre si.
Este teorema se utiliza en problemas de este tipo: Calcular el resto de dividir 31895243 entre 13.
De la aplicacion 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
¿Hay infinitos números primos de Mersenne?
Sean p y 2p + 1 primos. ¿Hay inifinitos pares de números primos que cumplan esta condición?
¿Hay infinitos números primos gemelos?