Los Numeros Primos

HISTORIA DE LAS

MATEMÁTICAS

LOS NÚMEROS PRIMOS

Rocío Gutiérrez Bermejo

Diciembre de 2006

Historia de las matemáticas: Los números primos Rocío Gutiérrez Bermejo

Índice

1. Introducción – exposición del tema……………………………Página 2

2. Entorno matemático y cultural…………………………………Página 3 3. La distribución de los números primos………………………..Página 9 4. Algunas conjeturas famosas y problemas sin resolver 4.1 La Hipótesis de Riemann………………………………Página 25 4.2 La conjetura de Goldbach…………………………….. Página 26 4.3 La conjetura de los primos gemelos…………………. Página 28 4.4 ¿Hay infinitos primos de Fermat?.............................. Página 29 4.5 ¿Hay infinitos primos de Mersenne?..........................Página 30 5. Números primos y criptografía…………………………………Página 35 6. Apéndice: Carta de Gauss a Encke…………………………...Página 37 7. Bibliografía……………………………………………………….Página 41

- 1 -


HISTORIA DE LOS NÚMEROS PRIMOS

1. INTRODUCCIÓN – EXPOSICIÓN DEL TEMA

Un número es primo si sólo se puede dividir por él mismo y la unidad. Lo son

el 13 y el 17, y no lo es el 15. Hay que añadir una excepción, la del número 1. Considerando la definición, podríamos decir que el número 1 es primo; sin embargo presenta un comportamiento muy diferente al resto de los números primos por su condición de elemento neutro de la multiplicación. Por tanto no consideramos el 1 ni como primo ni como compuesto. En este trabajo voy a explicar la evolución a lo largo de la historia en este ámbito de las matemáticas, cómo ha sido el esfuerzo de la humanidad por comprender los números primos que en mi opinión son un claro ejemplo de la belleza y el encanto de esta ciencia. La propiedad más importante de los números primos es que constituyen las piezas básicas en las que se descompone cualquier número natural. El Teorema Fundamental de la Aritmética dice que todo número natural mayor ó igual que 2 puede ser expresado, de manera única, como producto de números primos. ¿Cuáles son los números primos? La respuesta es que hay una cantidad infinita de primos, y la demostración de esta propiedad se remonta a Euclides y es un buen ejemplo de la belleza de las Matemáticas. Otro aspecto importante es aquél que los hace útiles: la seguridad del comercio por vía electrónica se confía hoy a códigos construidos usando estos números indivisibles; gracias a los números primos y sus propiedades se pueden hacer conexiones seguras por canales inseguros, acreditar identidades, etc. Han sido muchos los matemáticos que han dedicado esfuerzos al estudio de estos números un “poco especiales”, los primos, algunos de los cuales mencionaré. Y sobre todo me centraré en la distribución de los números primos, estudiando un artículo sobre la Historia del famoso Teorema de los números primos y otros textos que tienen que ver con esto.

- 2 -


2. ENTORNO MATEMÁTICO Y CULTURAL

Los números primos y sus propiedades fueron estudiados de manera exhaustiva por los matemáticos de la antigua Grecia.

La actividad intelectual de las civilizaciones desarrolladas en Egipto y Mesopotamia, ya había perdido casi todo su impulso mucho antes que comenzara la Era Cristiana, pero a la vez que se acentuaba este declive, surgían con fuerza nuevas culturas a lo largo de todo el Mediterráneo; y de entre ellas, la cultura helénica fue la principal abanderada en el terreno cultural. Tanto es así, que las civilizaciones anteriores a la Antigua Grecia se conocen como culturas prehelénicas. En menos de cuatro siglos, de Tales de Mileto a Euclides de Alejandría, construyeron un imperio invisible y único cuya grandeza perdura hasta nuestros días. Este logro se llama MATEMÁTICAS.

-PITÁGORAS

Hace unos 25 siglos, vivió Pitágoras de Samos, uno de los personajes más conocidos y a la vez más misteriosos de las Matemáticas. Filósofo griego nacido en Samos y muerto en Metaponto. Es considerado como uno de los Siete Grandes sabios de Grecia y su vida estuvo siempre envuelta por la leyenda. Pitágoras viajó a Egipto y Babilonia, donde asimiló conocimientos tanto matemáticos como astronómicos, así como religiosos. Fundó una escuela conocida como Hermandad Pitagórica (500 a. C. a 300 a. C) cuyos miembros estaban interesados en los números por su misticismo y sus propiedades numerológicas. Distinguieron conceptos tales como los de número primo ó numero perfecto (aquél que la suma de sus divisores propios da como resultado el número en sí mismo; por ejemplo, el 28). La influencia de la escuela pitagórica es indudable sobre los Elementos de Euclides. -EUCLIDES Floreció hacia el 300 a.C. en Alejandría, y es junto a Arquímedes y Apolonio, posteriores a él, uno de los tres mayores matemáticos de la Antigüedad y también uno de los mayores de todos los tiempos. El nombre de Euclides está ligado a la geometría, al escribir su famosa obra "Los Elementos", prototipo en esta rama de las matemáticas. Sabemos que fue profesor de Matemáticas en el Museo de Alejandría. La leyenda cuenta que cuando uno de sus alumnos le preguntó para qué servía estudiar geometría, Euclides ordenó que le dieran unas monedas “ya que debe ganar algo necesariamente con lo que aprende”. Cuando aparecieron los Elementos Euclidianos ya habían sido probados varios resultados importantes acerca de números primos. Euclides demuestra que hay infinidad de números primos en la proposición número 20 del libro IX de los Elementos: “Ningún conjunto de números primos incluye a todos”. La demostración es muy sencilla:

- 3 -


Supongamos que hay una cantidad finita de números primos kppp ,...,, 21 .

Consideramos ahora el producto de todos los primos y le sumamos 1. Es decir, 1),...,,( 21 += kpppN , que no sería divisible por ninguno de ellos y por tanto, ó N es un

nuevo primo, ó es divisible por algún primo que no hemos considerado. Tenemos entonces que N es compuesto; así cualquier cantidad finita de primos puede ser incrementada y por tanto hay infinitos números primos. El Teorema Fundamental de la Aritmética aparece en libro IX de los elementos de Euclides. También demostró el siguiente teorema: “Si el número 2n - 1 es primo, entonces el número 2n-1(2n - 1) es un número perfecto”. Euclides -ERATÓSTENES (195-276 a.C.)

Cerca del 200 a. C., el astrónomo Eratóstenes de Cirene ideó un algoritmo para calcular números primos llamado Criba ó Tamiz de Eratóstenes.: La criba de Eratóstenes es un algoritmo que permite hallar todos los números primos menores que un número natural dado N. Se forma una tabla con todos los números naturales comprendidos entre 2 y N y se van tachando los números que no son primos de la siguiente manera: cuando se encuentra un entero que no ha sido tachado, ese número es declarado primo, y se procede a tachar todos sus múltiplos. El proceso termina cuando el cuadrado del mayor número confirmado como primo es mayor que N. Números primos menores que 100:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80

81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

Se da luego un gran vacío en la historia de los números primos que usualmente es llamado la Edad Oscura.

- 4 -


-FERMAT (1.601-1665) El próximo gran descubrimiento fue realizado por Fermat muchos siglos más tarde. Pierre de Fermat nació en Francia en 1601 y las matemáticas eran su gran afición. Él demostró que cada número primo de la forma 4n+1 puede ser escrito de manera única como la suma de dos cuadrados y demostró cómo cualquier número puede ser escrito como la suma de cuatro cuadrados. Ideó un nuevo método de factorización de números largos, y un teorema importante es el que se conoce como El pequeño teorema de Fermat; éste establece que si p es un número primo entonces para cualquier entero a obtenemos que aa p = módulo p.

Fermat mantuvo correspondencia con otros matemáticos de su época, y en particular con el monje Marín Mersenne (1.548-1.688), que nació en Francia y actuó de intermediario entre algunos matemáticos del siglo XVII. En una de sus cartas a Mersenne, él conjetura que los números 2n + 1 eran siempre primos si n es una potencia de 2. Él había verificado esto para n = 1, 2, 4, 8 y 16 y sabía que si n no era una potencia de 2, el resultado fallaba. Los números de esta forma son llamados Números de Fermat y no fue hasta más de 100 años más tarde que Euler demostró que 232 + 1 = 4294967297 es divisible por 641 y por tanto no es primo. Los números de la forma 2n - 1 también atrajeron la atención porque es muy fácil demostrar que a menos que n sea primo, este número será compuesto. A menudo éstos son llamados Números primos de Mersenne

nM , dado que Mersenne los estudió. No todos los números de la forma 2n - 1 con n

primo son primos. Hablaré más adelante sobre todos los números de Mersenne encontrados hasta hoy. La teoría de números del siglo XIX fue impulsada gracias a los resultados de Fermat. -EULER (1.707-1.783) Fue el científico más importante de Suiza, nacido en Basilea en 1707. El trabajo de Euler tuvo un gran impacto en la teoría de números en general y sobre la de primos en particular. Fue el primero en publicar la prueba del Pequeño Teorema de Fermat, y también demostró otra famosa afirmación de Fermat: “un primo de la forma 4k+1 se puede expresar como la suma de dos cuadrados perfectos de manera única, mientras que un número de la forma 4k-1 no puede descomponerse de ninguna forma como suma de dos cuadrados perfectos”. Como ya he dicho antes, factorizó el 5º primo de Fermat. Pero esto fue sólo el principio, profundizó mucho en este tema y cuatro volúmenes de sus obras completas tratan de teoría de números. De su correspondencia con Christian Goldbach, surgió la conjetura de Goldbach: “todo número par mayor que 2 es suma de dos primos”. Euler fue el primero en notar que la Teoría de Números puede ser estudiada utilizando herramientas del análisis. Una gran contribución suya fue la prueba analítica de la infinitud de los primos, que aparece en el artículo Variae observaciones circa series que comentaré al hablar de la distribución de los números primos, y que se deduce de su famosa identidad:

- 5 -


1

1

)1(−−

∞

=

− ∏∑ −=p

s

n

s pn ,

con p recorriendo los primos y s>1

En el mismo artículo estudió el comportamiento de la suma de los inversos de los primos, y vio que divergía. También demostró que existían infinitos primos de la forma 4k+1, y llegó a conjeturar la existencia de infinitos primos en cualquier progresión aritmética

kbabababaa ++++ ,...,3,2,, , siendo a y b primos entre sí. Aunque no lo probó, fue Dirichlet quien lo consiguió en el año 1837 (y hoy se conoce como Teorema de Dirichlet). Leonhard Euler A medida que avanzaba el siglo XIX, cada vez intrigaba más entender cómo estaban distribuidos los números primos entre todos los números. -GAUSS (1.777-1.855) Matemático alemán nacido en Brunswick, Gauss fue un niño prodigio en matemáticas y continuó siéndolo toda su vida. Hay quien le considera uno de los tres mayores matemáticos de la historia junto a Arquímedes y Newton. Hizo una labor importante en la Teoría de Números, sintetizada en su famosa obra "Disquisitiones arithmeticae", responsable del desarrollo del lenguaje y de las notaciones de la rama de la teoría de números conocida como álgebra de congruencias, ejemplo primitivo de las clases de equivalencia. El 1801 demostró el teorema fundamental de la aritmética: todo número natural se puede representar como el producto de números primos de una y sólo una forma. A la temprana edad de 14 años, el joven Gauss conjeturó que cuando x crece ilimitadamente, el número de primos menores ó iguales que x, llamado π(x), es como x/log(x). La demostración de esta conjetura, conocida como el Teorema de los números primos, requirió casi cien años. En 1896, Jacques Hadamard y Charles de la Vallée Poussin dieron demostraciones completas y rigurosas de que (π(x)logx)/x se acerca indefinidamente a 1 cuando x crece, tras los notables progresos realizados por Chebychev (quien dedujo que xCxxxC 21 )(log/ << π para ciertas constantes 1C y

2C ) y Riemann durante el siglo XIX.

- 6 -


Carl Friedrich Gauss

-RIEMANN (1.826-1.866) Georg Friedrich Riemann fue un matemático alemán, nacido en Breselenz en 1826 y fallecido en Selasca (Italia). Empezó su vida con estudios religiosos, intentando demostrar la veracidad del Génesis mediante razonamientos matemáticos. Fracasó en el intento, pero se descubrió su talento matemático y su ambición religiosa se desvió. En 1851 su tesis doctoral recibió la aprobación ni más ni de menos que del propio Gauss. En 1860 escribió una breve pero muy importante memoria en la que, a partir de la identidad de Euler despejó π(x) en términos de la función zeta:

1

1( )

sn

sn

ζ∞

=

=∑

Retrato de Riemann

- 7 -


Riemann dejó indicado el camino para demostrar el teorema de los números primos. Conjeturó que, una vez extendida adecuadamente la función zeta al plano complejo, todos los números x + iy con x > 0 y tales que ,0)( =+ iyxζ deben cumplir que x = ½, es decir, los ceros de zeta en el semiplano derecho están en “fila india”. Ésta es la famosa Hipótesis de Riemann. Que esta conjetura sea verdad equivale a obtener el error óptimo en el teorema de los números primos. Este problema sigue sin resolverse y constituye un agujero en la teoría de los números primos; el Instituto Clay de Matemáticas ofrece un millón de dólares por resolver cada uno de los problemas del milenio, entre los que se encuentra la Hipótesis de Riemann.

- 8 -


3. LA DISTRIBUCIÓN DE LOS NÚMEROS PRIMOS ¿Qué se puede decir acerca de la distribución global de los números primos entre los números enteros? En el artículo A history of the prime number theorem de L.J. Goldstein (University of Maryland), se pueden encontrar algunas claves para responder a esta pregunta. A continuación expongo un resumen de dicho artículo: El Teorema de los números primos nos permite predecir el modo en que los primos están distribuidos. Sea x un número real positivo, y sea )(xπ el número de primos menores ó iguales que x. Entonces, el teorema de los números primos afirma que:

(1) 1

log/

)(lim =

∞→ xx

xx

π,

donde logx denota el logaritmo natural de x. En otras palabras, el teorema de los números primos afirma que:

(2) )(,loglog

)( ∞→

+= x

x

xo

x

xxπ

Actualmente es mucho mejor remplazar (1) y (2) por la siguiente afirmación equivalente:

(3)

+= ∫ x

xo

y

dyx

x

loglog)(

2π

La ventaja de esta versión es que la función

∫=x

y

dyxLi

2,

log)(

llamada logaritmo integral, proporciona una buena aproximación numérica de

)(xπ a x/logx. (El artículo habla de la antigua Grecia, de cuándo surgió el concepto de número primo, y también de la prueba de la infinitud de los primos que aparece en los Elementos de Euclides y de la Criba de Eratóstenes; no comento esa parte dado que ya lo he hecho anteriormente).

- 9 -


Hay una prueba de que existen infinitos números primos bastante

diferente de la de Euclides, y que es muy significativa para la historia del Teorema de los números primos. La prueba la realizó Leonhard Euler en la segunda mitad del siglo XVIII, y es como sigue: Asumimos que Npp ,...,1 es una lista completa de todos los primos, y

consideramos el producto

(6) ∏∏==

−

+++=

−

N

i ii

N

i i ppp 12

1

1

...11

11

1 .

Dado que todo número entero positivo n puede escribirse de manera única como producto de potencias de números primos, toda fracción 1/n aparece en

el desarrollo formal del producto (6). Por ejemplo, si n = NaN

a pp ...11 , entonces 1/n

aparece multiplicando los términos .,...,/1,/1 2121

NaN

aa ppp

Por tanto, si R es cualquier entero positivo,

(7) ∑∏==

−

≥

−

R

n

N

i i

np 11

1

/11

1 .

Sin embargo, cuando ∞→R , la suma de la derecha en (7) tiende a infinito, lo que contradice la inecuación. Así, Npp ,...,1 no puede ser una lista completa de

todos los primos. En la prueba se relaciona el Teorema Fundamental de la Aritmética con la existencia de infinitos números primos; también se usa la divergencia de la serie armónica. El texto no menciona los siguientes Teoremas que probó Euler y que publicó en su artículo Variae observaciones circa series en 1.737, los cuales creo que merece la pena comentar:

- “Si hacemos tender a infinito la fracción ...12106421

...13117532

⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅

, donde el numerador es el

producto de todos los números primos y el denominador el es producto de todos los números inferiores en una unidad a los primos, el resultado es el mismo que la suma de

la serie ...6

1

5

1

4

1

3

1

2

11 ++++++ que es ciertamente infinita.”

Prueba: Si tenemos:

...6

1

5

1

4

1

3

1

2

11 ++++++=x ,

entonces

...8

1

6

1

4

1

2

1

2

1+++=x ,

- 10 -


que restándosela a la primera ecuación queda:

...7

1

5

1

3

11

2

1+++=x .,

donde no hay denominadores pares. De ésta, obtenemos la serie:

...21

1

15

1

9

1

3

1

3

1

2

1++++=⋅ x ,

y tendremos

...13

1

11

1

7

1

5

11

3

2

2

1+++++=⋅ x ,

donde no podemos encontrar entre los numeradores ningún número divisible por 2 ó por 3. Para eliminar los números divisibles por 5, obtenemos la serie:

...35

1

25

1

5

1

5

1

32

21+++=⋅

⋅⋅

x ,

y tendremos

...13

1

11

1

7

11

532

421++++=⋅

⋅⋅⋅⋅

x .

Procediendo del mismo modo, quitando todos los términos divisibles por 7, por 11, y por todos los números primos, finalmente se tendrá:

⋅=⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅

1...23191713117532

...22181612106421x

Como

...6

1

5

1

4

1

3

1

2

11 ++++++=x ,

...7

1

6

1

5

1

4

1

3

1

2

11 +++++++ = ,

...22181612106421

...23191713117532

⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅

expresión cuyos numeradores constituyen la secuencia de números primos y los denominadores son los mismos menos una unidad. Q.E.D. - “La suma de los recíprocos de los números primos,

...13

1

11

1

7

1

5

1

3

1

2

1++++++ ,

es divergente.”

- 11 -


Prueba: Si escribimos:

A=++++++ ...13

1

11

1

7

1

5

1

3

1

2

1

B=++++++ ...13

1

11

1

7

1

5

1

3

1

2

1222222

C=++++++ ...13

1

11

1

7

1

5

1

3

1

2

1333333

y así sucesivamente denotamos todas las potencias por sus correspondientes letras, tendremos, llamando e al número cuyo logaritmo hiperbólico es igual a 1,

...4

1

3

1

2

1++++ DCBA

e = ...7

1

6

1

5

1

4

1

3

1

2

11 +++++++ .

Como

...6

7

4

5

2

3

1

2...

4

1

3

1

2

1++++=++++ llllDCBA ,

por el Teorema probado antes se tiene:

...4

1

3

1

2

1++++ DCBA

e = ,...6421

...7532

⋅⋅⋅⋅⋅⋅⋅⋅

= ...7

1

6

1

5

1

4

1

3

1

2

11 +++++++ .

Para que ...

4

1

3

1

2

1++++ DCBA

e sea igual a ...7

1

6

1

5

1

4

1

3

1

2

11 +++++++ =∞ , es necesario que

A sea una cantidad infinitamente grande y así los términos

...4

1

3

1

2

1+++ DCB

desaparecerán y tendremos

...13

1

11

1

7

1

5

1

3

1

2

1+++++

=ee A = ...7

1

6

1

5

1

4

1

3

1

2

11 +++++++ .

Por lo tanto,

=++++++ ...13

1

11

1

7

1

5

1

3

1

2

1...)

7

1

6

1

5

1

4

1

3

1

2

11( +++++++l =∞ .

Q.E.D.

- 12 -


En 1.798 Legendre afirma que )(xπ es de la forma )log/( BxAx + para

ciertas constantes A y B. Redefinió su conjetura en 1.808 afirmando que

,)(log

)(xAx

xx

−=π

donde .08366.1)(lim =∞→

xAx

(Nota: en el artículo de Goldstein el denominador aparece con un signo +, pero he contrastado con otros textos y la conjetura de Legendre es como la he expresado.) Precisamente en )(xA está el error de Legendre que se verá más adelante. En su memoria de 1.808, Legendre formuló otra famosa conjetura: Sean k y l dos enteros relativamente primos entre sí; entonces, existen infinitos primos de la forma knl + ,...)3,2,1,0( =n . En otras palabras, si )(, xlkπ denota el número de

primos p de la forma knl + con xp ≤ , Legendre conjeturó que (8) ∞→)(, xlkπ cuando ∞→x .

La prueba de (8) que dio Dirichlet en 1.837 proporciona varias ideas cruciales para el enfoque del teorema de los números primos.

Aunque Legendre fue el primero en publicar conjeturas sobre el Teorema de los números primos, Gauss había hecho ya un extenso trabajo sobre la teoría de primos en 1.792-3. Se divertía recopilando resultados para hacer tablas que muestran cómo están distribuidos los primos. Sospechó que la densidad con la que los primos se encontraban alrededor del entero n era 1/logn, por lo que el número de primos en el intervalo [a,b) será aproximadamente igual a

∫b

a x

dx

log.

Gauss nunca publicó sus investigaciones sobre la distribución de los primos. Conocemos información sobre su trabajo en esto y sus tablas gracias a una carta que escribió Gauss al astrónomo Encke, el 24 de Diciembre de 1.849. A continuación comento dicho texto, cuyo original incluyo en el Apéndice: En su carta, Gauss hace notar a Encke que sus observaciones referentes a la frecuencia de números primos son de su interés, ya que éstas le hacen recordar los esfuerzos que hizo en este campo en los años 1.792 y 1.793. Afirma que antes de comenzar con sus investigaciones en el campo de la aritmética superior, uno de sus primeros proyectos fue centrar su atención en la disminución de la frecuencia de primos, para lo cual contaba los primos de varios intervalos y grababa los resultados en tablas. Gauss adjuntó dichos resultados en varias páginas. Cuenta cómo observó que la frecuencia era por término medio inversamente proporcional al logaritmo, por tanto el número de primos por debajo de uno dado n es aproximadamente

∫ n

dn

log,

donde se entiende que el logaritmo es hiperbólico (natural). Después, cuando en 1.796 se hizo con las tablas de Vega, llevó su cálculo más lejos, confirmando su estimación.

- 13 -


Asegura que utilizaba sus ratos libres para contar el número de primos en un intervalo dado. Gauss confiesa a Encke que en ocasiones se rendía haciendo el cálculo, pero que haciendo caso de la petición de Goldschmidt rellenó los huecos que había dejado en el primer millón y continuó con el cálculo según las tablas de Burkhardt. Así contó los tres primeros millones y comparó los resultados con la integral. Incluye un pequeño extracto, una tabla en la que aparecen los datos junto con el error numérico que se comete. Gauss dice que no sabía que Legendre había estado trabajando en este tema, y hace referencia a una carta anterior que Encke le escribió a él, gracias a la cual se entera de las investigaciones de Legendre. Entonces Gauss observó su Teoría de Números, y en la segunda edición encontró varias cosas que él había pasado por alto. Sostiene que en la

fórmula de Legendre An

n

−log, donde A es una constante igual a 1.08366, él ha

encontrado algunas desviaciones, y a pesar de que son incluso menores que las que se producen con la integral )(xLi (aproximación de )(xπ de Gauss), la tasa con la que se incrementa el término de error de la fórmula de Legendre es mayor. Gauss añade algunos números que deberían usarse en sustitución de A para hacer el cálculo, y afirma que la evidencia numérica no sostiene ninguna conjetura sobre el valor límite de A. Finalmente, Gauss pregunta a Encke si sería posible incitar al joven Mr. Dase a contar el número de primos en los siguientes millones, usando las tablas cuya distribución no tiene previsto hacer pública. Explica cómo ha hecho los cálculos a partir del primer millón, siguiendo un método que ha ideado él mismo, para que sea más cómodo. Gauss adjuntó al texto sus tablas, las cuales eran de tres tipos. En las primeras, cada entrada representa un intervalo de longitud 1.000. Así, por ejemplo (mirar página 15), hay 168 primos entre 1 y 1.000, 135 entre 1.001 y 2.000, 127 entre 3.001 y 4.000, y así sucesivamente. En el segundo conjunto de tablas, Gauss sigue investigando la distribución de primos y la compara con el resultado de su integral. En su carta explica el significado de dichas tablas. Las cuentas para cada 100.000 números están en una única página en 10 columnas. Por ejemplo, entre 1.000.000 y 1.100.000 hace lo siguiente (mirar página 16): entre 1.000.000 y 1.010.000 hay 100 intervalos de longitud 100, y corresponden a la primera columna. Entre esos 100 intervalos hay uno que contiene un único primo, no hay ninguno que tenga dos ó tres primos, hay dos con cuatro primos, once con cinco primos, etc., produciendo en total 752 que es igual a

....1461152411 +⋅+⋅+⋅+⋅ ; la segunda columna corresponde a los primos entre 1.010.001 y 1.020.000, y así sucesivamente hasta llegar a 1.100.00. En total, en ese intervalo de longitud 100.000, encuentra 7.210 primos, y compara el resultado con

)(xLi :

99,212.7log

000.100.1

000.000.1

=∫ x

dx.

En la tabla correspondiente a estos cálculos aparecen 3 filas en blanco, las correspondientes a 14, 15 y 16, pero en las siguientes páginas sí aparecen intervalos conteniendo ese número de primos. Finalmente, aparecen tablas es las que están combinados todos los datos obtenidos para un millón entero. Por ejemplo (mirar página 17), entre 1.000.000 y 2.000.000 hay en total 70.382 primos. A continuación incluyo algunas de las tablas que Gauss adjuntó a la carta a Encke, en particular las que corresponden a los 3 ejemplos a los que hago referencia.

- 14 -


- 15 -


- 16 -


Continuando con el artículo, Goldstein dice que las tablas de Gauss no están libres de errores (un estudiante las ha revisado usando un ordenador y ha encontrado algunos errores). Pese a ello, sus cálculos siguen proporcionando una evidencia abrumadora a favor del Teorema de los números primos.

- 17 -


El siguiente paso hacia la prueba del Teorema de los números primos lo

dio Dirichlet en 1.837, en una dirección completamente diferente. En una memoria, Dirichlet probó la conjetura de Legendre (8) respecto a la existencia de infinitos números primos en una progresión aritmética. El trabajo de Dirichlet contiene dos grandes nuevas ideas. Sea nΖ el anillo de clases residuales módulo n, y sea x

nΖ el grupo de

unidades de nΖ . Entonces xnΖ consiste en estas clases residuales que

contienen un elemento relativamente primo con n. Si k es un entero, k es su clase residual módulo n. La primera idea brillante de Dirichlet fue introducir los caracteres del grupo x

nΖ , es decir, los homeomorfismos de xnΖ en el grupo

multiplicativo *C de los números complejos excepto el cero. Si χ es uno de esos caracteres, entonces asociamos con χ una función del grupo de los enteros no negativos como sigue:

)()( aa χχ = si 1),( =na 0 en otro caso

**: CZ →χ es un caracter numérico módulo n.

El principal resultado de Dirichlet sobre caracteres numéricos fue la relación de ortogonalidad, que afirma: (A) )()( na

a

φχ =∑ si χ es 1

0 en otro caso , donde a recorre un sistema completo de residuos módulo n. (B) )()( na

a

φχ =∑ si 1≡a (mod n)

0 en otro caso , donde χ recorre todos los caracteres numéricos módulo n. La segunda gran idea de Dirichlet fue asociar cada carácter numérico módulo n y cada número real 1>s , con la serie infinita

(9) ∑∞

=

=1

)(),(

nsn

nsL

χχ .

Es claro que la serie converge absolutamente y representa una función continua para 1>s . Sin embargo, un análisis más delicado muestra que la serie (9) converge (aunque no absolutamente) para 0>s y representa una función continua de s en este intervalo semi-infinito siempre que χ no sea idénticamente 1. ),( χsL se llama L-función de Dirichlet.

- 18 -


(10) ∏ −−=p

sp

psL 1)

)(1(),(

χχ ( 1>s ),

donde el producto recorre todos los números primos. La prueba de (10) es muy similar al argumento dado en la prueba de Euler de la existencia de infinitos números primos. Dirichlet prueba que hay infinitos números primos en la progresión aritmética a, a+n, a+2n,..., (a,n)=1, imitando de algún modo la prueba de Euler, estudiando la función ),( χsL para s cerca de 1.

El Teorema de Dirichlet sobre los primos en progresiones aritméticas fue uno de los mayores logros de las matemáticas del siglo XIX, porque introdujo una nueva idea en la teoría de números: que los métodos analíticos pueden ser aplicados provechosamente a problemas aritméticos. El artículo de Dirichlet en 1.837 fue el principio de una revolución en el pensamiento numérico-teórico, cuyo fundamento fue aplicar análisis a la teoría de números. Al principio los matemáticos no estaban conformes con las ideas de Dirichlet. Sin embargo, la historia de la teoría de números en el siglo XIX muestra que esta idea fue repudiada eventualmente y la conexión entre el análisis y la teoría de números fue reconocida. El primer progreso importante hacia la prueba del teorema de los números primos después de Dirichlet fue debido al matemático ruso Chebychev, en dos memorias escritas en 1.851 y 1.852. Introdujo dos funciones de la variable real x:

∑≤

=xp

px log)(θ ,

∑≤

=xpm

px log)(ψ ,

donde p recorre los primos y m los enteros positivos. Chebychev probó que el teorema de los números primos (1) es equivalente a las dos afirmaciones:

(11) 1)(

lim =∞→ x

xx

θ,

(12) 1)(

lim =∞→ x

xx

ψ.

Además, probó que si x

xx

)(lim

θ∞→

existe, entonces su valor debe ser 1. Más aún,

Chebychev probó que

(13) 10555.1log/

)(suplim1

log/

)(inflim92129.0 ≤≤≤≤

∞←∞→ xx

x

xx

x

xx

ππ.

Los métodos de Chebychev no tenían poder suficiente para probar el teorema de los números primos.

- 19 -


La “gran zancada” hacia la prueba del teorema de los números primos fue dada por B. Riemann en una memoria escrita en 1.860. Incluyo un facsímil de la primera página su manuscrito:

- 20 -


(Comienza diciendo que el punto de partida para su investigación es la observación de

Euler de que ∏ ∑=−

s

s

np

11

1

1, siendo p los números primos y n los enteros.)

Riemann tomó la medida de conectar la aritmética con la teoría de funciones de variable compleja. Introdujo la siguiente función:

(14) 1

1( )

sn

sn

ζ∞

=

=∑ ,

conocida como Función zeta de Riemann. Es fácil ver que la serie (14) converge absoluta y uniformemente para s en un subconjunto compacto del semiplano Re(s)>1. Además, usando el mismo argumento que usó Euler en la prueba de la infinitud de los primos, es fácil probar que

(15) ∏−

−=

psp

s1

11)(ζ (Re(s)>1),

donde el producto se extiende a todos los primos p. La prueba de Euler sugiere que el comportamiento de )(sζ para s=1 está de alguna manera conectado con la distribución de los números primos. Y efectivamente es así.

La única singularidad de )(sζ sucede para s=1 y la serie de Laurent alrededor de s=1 se parece a

(16) ...)1(1

1)( 10 +−++

−= saas

sζ

Además, si tomamos (17) )()2/()1()( 2 sssssR s ζπ Γ−= − , entonces )(sR es una función entera y satisface: (18) )1()( sRsR −= . Una variación de la idea de la prueba de Euler es: Supongamos que hay un número finito de primos Npp ,...,1 . Entonces por (15), )(sζ tendría límite

cuando s tiende a 1, lo que contradice (16). Por tanto, la presencia de un polo de )(sζ en s=1 implica que hay infinitos números primos. Hay una estrecha conexión entre la función )(xψ y )(sζ . El primero en sacar provecho de esta conexión fue Riemann en su memoria de 1.860. Se tiene que:

- 21 -


(19) ∫ ∑+

−≤

∞→==

iT

iTxp

s

Txpds

s

s

s

x

m m

2

2)(log

)(

)('

2

1lim ψ

ζζ

.

La función

(20) )(

)('

s

s

s

x s

ζζ

tiene polos en x=0 y en todos los ceros ρ de )(sζ . Además, por la ecuación (15) vemos que 0)( ≠sζ para 1)Re( >s . Por tanto, todos los ceros de )(sζ se encuentras en el semiplano 1)Re( ≤s . Es más, dado que R(s) es entero y

0)( ≠sζ para 1)Re( >s , la ecuación (18) implica que los únicos ceros de )(sζ para los que 0)Re( <s son ,8,6,4,2 −−−−=s …, y son los ceros triviales de )(sζ . Así, todos los ceros no triviales de )(sζ están en la franja 1)Re(0 ≤≤ s . Ésta es la llamada franja crítica. El residuo de (20) en un cero no trivial ρ es

ρ

ρx.

Riemann llegó a la siguiente fórmula notable, conocida como la fórmula explícita de Riemann:

(21) )1log(2

1

)0(

)0(')( 2−−−−−= ∑ x

xxx

ζζ

ρψ

ρ

ρ

,

donde ρ recorre todos los ceros no triviales de la función zeta de Riemann. Hay dos razones que hacen sorprendente la fórmula de Riemann. La primera es que relaciona la función )(xψ que está conectada con la distribución de los primos, con la distribución de los ceros de la función zeta. Y la otra es que la fórmula (21) pone en evidencia una forma del teorema de los números primos igualando )(xψ con x más un término de error que depende de los ceros de la función zeta. Si denotamos este error con )(xE , vemos que el teorema de los números primos es equivalente a la afirmación:

(22) 0)(

lim =∞→ x

xEx

,

que a su vez es equivalente a

(23) 01

lim =∑∞→

ρ

ρ

ρx

xx.

- 22 -


Riemann fue incapaz de probar (23), pero hizo numerosas conjeturas respecto a la distribución de los ceros ρ para los que (23) se deduce inmediatamente. La conjetura más famosa de Riemann se conoce como la Hipótesis de Riemann (hablaré de ella más adelante), que aún sigue sin probarse. No obstante, si la Hipótesis de Riemann es cierta, entonces

ρρ

ρ 12

1

xx

=

y con este hecho y la ecuación (21), es posible probar que

(24) )()( 2

1ε

ψ+

Ο+= xxx

para todo 0>ε , donde )( 2

1ε+

Ο x denota una función )(xf tal que ε+

2

1

/)( xxf está acotada cuando x es grande. De esta manera, la hipótesis de Riemann implica (23) de un modo trivial, y por eso el teorema de los números primos se deduce de la hipótesis de Riemann. Por tanto, la conexión entre la función zeta y la distribución de los números primos no es un hecho accidental. En su memoria, Riemann hizo otras conjeturas. Por ejemplo, si

)(tN denota el número de ceros no triviales ρ de )(sζ tales que ,)Im( TT ≤≤− ρ Riemann conjeturó que

(25) )(log2

)2log(1log

2

1)( TOTTTtN +

+−=

ππ

π,

y fue probado por von-Mangoldt en 1.895. Una interesante línea de investigación ha sido envuelta por la obtención de

estimaciones para el número de ceros no triviales en la línea 2

1)Re( =s .

Afortunadamente, no es necesario probar la hipótesis de Riemann para probar el teorema de los números primos en la forma (12). Sin embargo, es necesaria la obtención de información sobre la distribución de los ceros de

)(sζ . Dicha información fue obtenida de manera independiente por Hadamard y de la Vallée Poussin en 1.896 proporcionando las primeras pruebas completas del teorema de los números primos. Aunque sus pruebas difieren en detalles, ambos establecen la existencia de una región libre de ceros que permite probar el teorema en la forma

(26) ( ) ).()(14/1log xcxeOxx −+=ψ

- 23 -


El Teorema de los números primos fue probado después de un siglo de

duro trabajo por parte de algunos de los mejores matemáticos. Cada paso en dirección a la prueba ha estado históricamente condicionado por el trabajo de generaciones precedentes. El artículo concluye afirmando que en cada paso de la cadena hasta llegar a la prueba, han sido descubiertas ideas fértiles y brillantes, y se ha proporcionado información para el siguiente eslabón.

- 24 -


4. ALGUNAS CONJETURAS FAMOSAS Y PROBLEMAS SIN RESOLVER 4.1 LA HIPÓTESIS DE RIEMANN

Una vez extendida adecuadamente la función ∑∞

=

=1

1)(

nsn

sζ al plano complejo,

todos los números x+iy con x>0 y tales que 0)( =+ iyxζ , deben cumplir 2

1=x .

Los valores de s para los que la función se hace cero, son necesariamente de la forma

it+2/1 . No se ha encontrado ningún cero que no cumpla esa condición, pero no se ha conseguido demostrar que eso ocurra para todos los ceros. Como hemos visto, el teorema de los números primos nos dice que el número de primos menores o iguales que un número x, es aproximadamente igual al cociente entre x y el logaritmo neperiano de x cuando x es muy grande. Si la hipótesis de Riemann es cierta, se obtiene el menor orden de error al sustituir )(xπ por su mejor aproximación. Esta conjetura constituye uno de los problemas abiertos más importantes de las matemáticas contemporáneas.

- 2 - 4 1 1/2

Ceros triviales

Regiones sin ceros Zonas desconocidas

Línea crítica - 2 - 4 1 1/2

Ceros triviales


Línea crítica - 2 - 4 1 1/2

Ceros triviales


Línea crítica

Distribución de ceros de la función zeta de Riemann

- 25 -


Golfrey Harold Hardi probó en 1.915 que hay una infinidad de ceros en la recta crítica, y con la ayuda de John Edensor Littlewood verificó que el número de ceros en la línea recta que une ½ con ½+iT es por lo menos AT para cierta constate positiva A si T es suficientemente grande. El trabajo de Selberg nos dice que el número de ceros en ese segmento es por lo menos TAT log para cierto A>0, y también sabemos que la cantidad

de ceros en la banda crítica con 0<t<T es asintótico a π2

TLogTcuando ∞←T . Norman

Levinson demostró en 1.974 que la constante A satisface π20

7≥A .

Aunque la hipótesis no ha sido demostrada, extensos cálculos realizados evidencian la verificación de la conjetura. Una prueba de la veracidad de esto aportaría luz a muchos de los misterios alrededor de la distribución de los números primos. Los cálculos verifican que los 1310 ceros no triviales de la función zeta calculados hasta la fecha están en la línea crítica. 4.2 LA CONJETURA DE GOLDBACH

El 7 de junio de 1.742, Christian Goldbach le escribió una carta a Leonhard Euler, sugiriéndole que pensara una demostración para la siguiente afirmación porque a él no se le ocurría: “Todo número par positivo, mayor que dos, se puede escribir como la suma de dos números primos”. Veamos algunos ejemplos en los que es muy fácil comprobar que la conjetura es cierta: 4 = 2 + 2 6 = 3 + 3 8 = 3 + 5 10 = 5 + 5 12 = 5 + 7 14 = 7 + 7 = 3 + 11 16 = 5 + 11 18 = 7 + 11 = 5 + 13 20 = 3 + 17 = 7 + 13 22 = 11 + 11 24 = 11 + 13 = 7 + 17 ..... 864 = 431 + 433 866 = 3 + 863 868 = 5 + 863 870 = 7 + 863, y así podríamos seguir.

- 26 -


Carta de Goldbach a Euler

Euler no pudo encontrar la demostración y, en realidad, después de más de dos

siglos y medio todavía nadie ha podido resolver el problema y tampoco nadie ha podido demostrar que sea falso. En 1.855 se sabía que los primeros 10.000 números cumplían la conjetura y en 1.940 se llegó a los 100.000. Hoy en día ha sido verificada hasta 10.000.000.000.000, pero por más que los ordenadores sigan avanzando, nunca llegarían a probarlo para todos los números. Se necesita una prueba matemática capaz de demostrar que Goldbach, tenía razón.

- 27 -


Existe otra conjetura también sugerida por Goldbach, conocida con el nombre de “La Conjetura Impar de Goldbach”, que dice que todo número impar mayor que cinco se escribe como la suma de tres números primos. Al día de hoy también permanece como un problema abierto de las matemáticas, aunque se sabe que es cierta hasta números impares de siete millones de dígitos. También se sabe que si la Hipótesis de Riemann es cierta, entonces la conjetura de Goldbach impar implica la conjetura de Goldbach par. De hecho, también se ha visto (en 1.997) que si la Hipótesis de Riemann es cierta, entonces la conjetura de Goldbach también lo es. 4.3 LA CONJETURA DE LOS PRIMOS GEMELOS

Dos números primos se denominan gemelos si uno de ellos es igual al otro más dos unidades. Las primeras parejas de números primos gemelos son:

(3,5), (5,7), (11,13), (17,19), (29,31), (41,43), (59,61), (71,73), (101,103), (107,109), (137,139), (149,151), (179,181), (191,193), (197,199), (227,229), (239,241),(269,271), (281,283), (311,313), (347,349), (419,421), (431,433), (461,463),(521,523), (569,571), (599,601), (617,619), (641,643), (659,661), (809,811), (821,823), (827,829), (857,859), (881,883)

La conjetura de los primos gemelos postula la existencia de infinitos pares de primos gemelos. Dado que es una conjetura, está todavía sin demostrar.

“Existe un número infinito de primos p tales que p + 2 también es primo.”

La conjetura ha sido investigada por muchos teóricos de números. La mayoría de matemáticos cree que la conjetura es cierta, y se basan en evidencias numéricas y razonamientos heurísticos sobre la distribución probabilística de los números primos. En 1.849, Alphonse de Polignac formuló una conjetura más general según la cual, para todo número natural k existen infinitos pares de primos cuya diferencia es 2·k. El caso k=1 es la conjetura de los números primos gemelos. En 1.940, Erdös mostró que existe una constante c < 1 e infinitos primos p tales que

)log(pcqp ⋅<− , donde q denota el número primo que sigue a p. Este resultado fue mejorado sucesivamente: en 1.986 Maier mostró que podía emplearse una constante c < 0,25. En 1966, Jing-run Chen mostró que existen infinitos números primos p tales que p+2 es un producto de, a lo más, dos factores primos. En 2.004 R. F. Arenstorf de la Vanderbilt University ha presentado una posible demostración de la conjetura en 38 páginas utilizando métodos de la teoría de números analítica clásica, aunque el lema 8 de dicha publicación es incorrecto.

- 28 -


4.4 ¿HAY INFINITOS PRIMOS DE FERMAT?

Un número primo de Fermat, nombrado en honor a Pierre de Fermat, quien fue el primero que estudió estos números, es un número primo de la forma:

122 +=n

nF ,

donde n es un número natural. Sólo se conocen cinco primos de Fermat, que son 3 (n=0), 5 (n=1), 17 (n=2), 257 (n=3) y 65.537 (n=4).

Fermat conjeturó que todos los números naturales de esa forma eran números primos, pero como ya mencioné antes Euler probó que no era así; al tomar 5=n se obtiene un número compuesto:

670041764142949672971232 ⋅==+ Luego el número más pequeño que siendo número de Fermat no es primo, es el 4294967297. Todos los números que tienen la forma de los primos de Fermat, aunque no sean primos, se llaman números de Fermat.

Existen dos problemas abiertos sobre estos números:

1. ¿Sólo hay cinco números primos de Fermat? 2. ¿Existen infinitos primos de Fermat?

Propiedades de los números de Fermat:

1. Un número de Fermat es igual al producto de todos los anteriores más 2. 2. Ningún número de Fermat puede ser la suma de dos números primos. Como

todos los números de Fermat son impares, uno de los sumandos debe ser 2. Entonces, el otro tendrá que ser, ó bien 1 (en el caso de F0 = 3) ó bien el producto de todos los anteriores, pero ninguno de éstos es primo.

3. Dos números de Fermat distintos siempre son primos entre sí. 4. Gauss demostró que existe una relación entre la construcción de polígonos

regulares con regla y compás y los números primos de Fermat: un polígono regular de n lados puede ser construido con regla y compás si y sólo si n es, ó bien una potencia de 2, ó bien el producto de una potencia de 2 y primos de Fermat distintos entre sí.

5. Todo número compuesto de Fermat se puede descomponer en factores primos de la forma 12 2 +⋅ +nk , con k entero positivo.

- 29 -


4.5 ¿HAY INFINITOS PRIMOS DE MERSENNE?

Los números de Mersenne son del tipo Mn = 2n - 1 con n primo, siendo los primeros 1, 3, 7, 15, 31, 63, 127,…Toman el nombre de Marin Mersenne (1.588-1.648), monje y matemático originario de Francia. La definición de estos números permite saber que el n-ésimo número de Mersenne es una cadena de n unos cuando se escribe en binario (base 2). Por ejemplo, M7 = 27 - 1 = 127 = 11111112 es un número de Mersenne. Si n es menor o igual a 7 entonces Mn es primo, pero después no es así necesariamente.

Los primos de Mersenne son números de Mersenne que además son primos, es decir, divisibles sólo por ellos mismos y por la unidad. El primo de Mersenne número cuatro de esta lista es precisamente el ejemplo anterior. El recientemente descubierto, y mayor primo conocido hasta el momento, hace el número 44 y es concretamente: 232582657 - 1 = 12457502601536945540…11752880154053967871, donde la línea de puntos significa que hay millones de dígitos que han sido omitidos. No todos los primos son primos de Mersenne, pero como éstos se pueden implementar fácilmente en un programa de ordenador los 6 mayores primos conocidos son de Mersenne. Para saber si un número de Mersenne es primo se utiliza el test de Lucas-Lehmer. El nuevo primo de Mersenne tiene 9.808.358 dígitos. Puede obtenerse a través de un programa realizado por Richard Crandall, descubridor del algoritmo que usa el proyecto GIMPS. Los diez mayores primos de Mersenne, incluyendo este último, han sido descubiertos gracias al proyecto internacional GIMPS (Great Internet Mersenne Prime Search) basado en computación distribuida, y que usa los PC´s de voluntarios a lo largo de todo el mundo. La búsqueda de los primos de Mersenne ha sido siempre un ejercicio que pone a prueba la potencia de computación y por tanto la fortaleza de los sistemas de encriptación. Los primos de Mersenne están relacionados con los llamados números perfectos que ya fueron estudiados en la antigua Grecia.

No se sabe si existen infinitos primos de Mersenne.

La siguiente tabla muestra los números primos de Mersenne conocidos hasta hoy:

# n Mn Número de dígitos Mn Fecha de descubrimiento Descubridor

1 2 3 1 antigüedad desconocido




- 30 -


5 13 8191 4 1456 anónimo

6 17 131071 6 1588 Cataldi

7 19 524287 6 1588 Cataldi

8 31 2147483647 10 1772 Euler

9 61 2305843009213693951 19 1883 Pervushin

10 89 618970019…449562111 27 1911 Powers

11 107 162259276…010288127 33 1914 Powers

12 127 170141183…884105727 39 1876 Lucas

13 521 686479766…115057151 157 30 de enero 1952 Robinson

14 607 531137992…031728127 183 30 de febrero 1952 Robinson

15 1,279 104079321…168729087 386 25 de junio 1952 Robinson

16 2,203 147597991…697771007 664 7 de octubre 1952 Robinson

17 2,281 446087557…132836351 687 9 de octubre 1952 Robinson

18 3,217 259117086…909315071 969 8 de septiembre 1957 Riesel

19 4,253 190797007…350484991 1,281 3 de noviembre 1961 Hurwitz

20 4,423 285542542…608580607 1,332 3 de noviembre 1961 Hurwitz

- 31 -


21 9,689 478220278…225754111 2,917 11 de mayo 1963

Gillies

22 9,941 346088282…789463551 2,993 16 de mayo 1963

Gillies

23 11,213 281411201…696392191 3,376 2 de junio 1963 Gillies

24 19,937 431542479…968041471 6,002 4 de marzo 1971 Tuckerman

25 21,701 448679166…511882751 6,533 30 de octubre 1978

Noll & Nickel

26 23,209 402874115…779264511 6,987 9 de febrero 1979

Noll

27 44,497 854509824…011228671 13,395 8 de abril 1979 Nelson & Slowinski

28 86,243 536927995…433438207 25,962 25 de septiembre 1982

Slowinski

29 110,503 521928313…465515007 33,265 28 de enero 1988

Colquitt & Welsh

30 132,049 512740276…730061311 39,751 20 de septiembre 1983

Slowinski

31 216,091 746093103…815528447 65,050 6 de septiembre 1985

Slowinski

32 756,839 174135906…544677887 227,832 19 de febrero 1992

Slowinski & Gage

33 859,433 129498125…500142591 258,716 10 de enero 1994

Slowinski & Gage

- 32 -


34 1,257,787 412245773…089366527 378,632 3 de septiembre 1996

Slowinski & Gage

35 1,398,269 814717564…451315711 420,921 13 de noviembre 1996

GIMPS / Joel Armengaud

36 2,976,221 623340076…729201151 895,932 24 de agosto 1997

GIMPS / Gordon Spence

37 3,021,377 127411683…024694271 909,526 27 de enero 1998

GIMPS / Roland Clarkson

38 6,972,593 437075744…924193791 2,098,960 1 de junio 1999

GIMPS / Nayan Hajratwala

39 13,466,917 924947738…256259071 4,053,946 14 de noviembre 2001

GIMPS / Michael Cameron

40* 20,996,011 125976895…855682047 6,320,430 17 de noviembre 2003

GIMPS / Michael Shafer

41* 24,036,583 299410429…733969407 7,235,733 15 de mayo 2004

GIMPS / Josh Findley

42* 25,964,951 122164630…577077247 7,816,230 18 de febrero 2005

GIMPS / Martin Nowak

43* 30,402,457 315416475…652943871 9,152,052 15 de diciembre 2005

GIMPS / Curtis Cooper & Steven Boone

- 33 -


44* 32,582,657 124575026…053967871 9,808,358 4 de septiembre 2006

GIMPS / Curtis Cooper & Steven Boone

* No se conoce si existen más números primos de Mersenne entre el 39 (M13,466,917) y el 44 (M32,582,657) por lo tanto, esta tabla es provisional.

Hay otras preguntas que surgen en torno a los números primos, como por ejemplo: ¿Existen infinitos primos de la forma ?12 +n ¿Existe siempre un número primo entre 2n y ?)1( 2+n (Chebychev probó el llamado postulado de Bertrand: “Para todo número natural n, siempre existe un número primo p mayor que n y menor que 2n”).

- 34 -


5. LOS NÚMEROS PRIMOS Y LA CRIPTOGRAFÍA

La palabra “Criptografía” viene del griego “Kryptos”, escondido, y “Graphos”, escritura. Es decir, “Escritura escondida”. Se trata de escribir algo de manera que otra persona que quiera leer lo que hemos escrito no pueda entenderlo a no ser que conozca cómo se ha escondido. Los sistemas criptográficos están teniendo un gran auge últimamente ante el miedo de que una transmisión en Internet pueda ser interceptada, como por ejemplo una transacción comercial de cientos de miles de euros o una información sobre determinados temas confidenciales. Una de las tareas que más tiempo ocupa a los grandes sistemas de ordenadores es el cálculo de números primos cada vez mayores. Su objetivo es poder obtener un número que sirva para cifrar mensajes y que después sea muy complicado descifrarlos. La criptografía depende de las funciones trampa, que son como los candados: fáciles de cerrar pero se necesita una llave para poder abrirlos. Dos métodos que se utilizan, basados en los números primos muy grandes, son: A) El criptosistema RSA, basado en el hecho de que es fácil multiplicar dos números primos pero es difícil factorizar el resultado. Una ejecución del RSA entre un emisor (E) y un receptor (R) consta de tres pasos que se describen de la siguiente forma:

1. Acordando un parámetro de seguridad k, el algoritmo genera dos primos p y q de k bits y un par de exponentes e y d tales que )(mod1 nde φ≡⋅ siendo

qpn ⋅= y por tanto )1)(1()( −−= qpnφ . La salida del algoritmo es una clave pública para el emisor: (e, n), y una clave secreta, d, para el receptor.

2. Cifrado: el emisor quiere cifrar un mensaje m que cumple m.c.d(m,n)=1 (por tanto, )mod(1)( nm n ≡φ ). Con los datos m, e, y n se obtiene el texto cifrado

)mod(nmc e= . 3. Descifrado: el receptor recibe el texto c y lo descifra utilizando:

)mod(1)( )()(1 nmmmmmmc ttnntedd ≡⋅≡⋅≡≡≡ + φφ (teniendo c y e como datos de entrada).

Llegados a este punto es importante mencionar de nuevo el Pequeño Teorema de Fermat: “Si p es un número primo, entonces, para cada número natural a, )mod(paa p = ”. Esto quiere decir que, si se eleva un número a a la p-ésima potencia y al resultado se le resta a, lo que queda es divisible por p. Una pequeña generalización del teorema, que se sigue de él, dice lo siguiente: “si p es primo y m y n son enteros positivos con m ≡ n (mod p-1), entonces am ≡ an (mod p) para todos los enteros a”. Expresado así, el teorema se utiliza para justificar el método de encriptación RSA.

- 35 -


El pequeño teorema de Fermat se puede generalizar mediante el teorema de Euler: para cualquier módulo n y cualquier entero a coprimo con n, se tiene:

)mod(1)( na n =φ ,

donde φ(n) es la función fi de Euler que cuenta el número de enteros entre 1 y n coprimos con n. Ésta es de hecho una generalización, ya que si n = p es un número primo, entonces φ(p) = p - 1.

B) El algoritmo de Diffie-Hellman, basado en que es fácil calcular pg x mod , siendo

p un número primo, pero es difícil hallar x a partir de xg y p . Funciona como sigue: Necesitamos un primo p gigantesco, y un número g tal que 1<g<p. Dos interlocutores, A y B, quieren acordar una clave. A se inventa en privado un número aleatorio grande, a, y envía a B ag módulo p por un canal inseguro. Como no se pueden tomar logaritmos de congruencias eficientemente, ni siquiera B puede conocer a. De igual forma, B se inventa b y envía a A bg módulo p. A puede calcular abg )( y B puede calcular bag )(

(módulo p), con lo que tanto A como B conocen la clave secreta abg . Sean Alice y Bob los interlocutores, un esquema del algoritmo es el siguiente:

Un adversario E que poseyera p, g, ag y bg , podría calcular el secreto compartido si tuviera también uno de los valores privados (a ó b) o lograse invertir la función. Pero

calcular a dado ag es el problema del logaritmo discreto en ∗pZ , un problema que se

cree intratable computacionalmente. Sin embargo, el protocolo es sensible a ataques activos del tipo "hombre en el medio". Si la comunicación es interceptada por un tercero, éste se puede hacer pasar por el emisor cara al destinatario y viceversa, ya que no se dispone de ningún mecanismo para validar la identidad de los participantes en la comunicación. Así, el "hombre en el medio" podría acordar una clave con cada participante y retransmitir los datos entre ellos, escuchando la conversación en ambos sentidos.

- 36 -


6. APÉNDICE: CARTA DE GAUSS A ENCKE

- 37 -


- 38 -


- 39 -


- 40 -


7. BIBLIOGRAFÍA

� C. Gillispie, Dictionary of Scientific Biography, Charles Scribner's Sons.

� http://www-groups.dcs.st-and.ac.uk/~history/ MacTutor History of

Mathematics.

� http://almez.pntic.mec.es

� http://wikipedia.org

� “The distribution of prime numbers”, A.E,Ingham.

� “The little Book of Big Primes”, Paulo Ribenhoim.

� http://www.divulgamat.net

� “Primos: ayer y hoy” (Apuntes de Ciencia y Tecnología), Elena Cristóbal y

Fernando Chamizo.

� www.jstor.org

� http://scholar.google.es

� http://www.blues.uab.es/~ipdm4/bibi/euler/

� http://www.ams.org (American Mathematical Society).

� http://www.math.princeton.edu/~ytschink/.gauss/

� http://www.maths.tcd.ie/pub/HistMath/People/Riemann/

� http://primes.utm.edu/notes/conjectures

� http://mersenne.org

� http://math.ucsd.edu/~kobryant/TalkReferences/GoldbachTalk.pdf

� http://delitosinformaticos.com/seguridad/criptografia.shtml

� www.escet.urjc.es/~matemati/md_iti/RSA.pdf

- 41 -

Documents

Los Numeros Primos