• Author / Uploaded
• aqp1118179

• Categories
• Número primo
• Teoría del anillo
• Análisis matemático
• Álgebra abstracta
• Combinatoria

Citation preview

Números primos Un número primo es un número entero mayor que cero, que tiene exactamente dos divisores positivos. También podemos definirlo como aquel número entero positivo que no puede expresarse como producto de dos números enteros positivos más pequeños que él, o bien, como producto de dos enteros positivos de más de una forma. Conviene observar que con cualquiera de las dos definiciones el 1 queda excluido del conjunto de los números primos. Ejemplos: a) El 7 es primo. Sus únicos divisores son 1 y 7. Sólo puede expresarse como producto de 7·1. b) El 15 no es primo. Sus divisores son 1, 3, 5 y 15. Puede expresarse como 3·5. (y también como 15·1) El término primo no significa que sean parientes de alguien. Deriva del latín "primus" que significa primero (protos en griego). El teorema fundamental de la aritmética afirma que todo número entero se expresa de forma única como producto de números primos. Por eso se les considera los "primeros", porque a partir de ellos obtenemos todos los demás números enteros. (El 15 se obtiene multiplicando los primos 3 y 5) Los 25 primeros números primos son 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 y 97, que son todos los primos menores que 100. En la siguiente tabla tenemos todos los primos menores que 1000, que hacen un total de 168 (21×8) 2

3

5

79

83

89

7

11

13

17

19

23

29

31

37

41

43

47

53

59

61

67

71

73

97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181

191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 open in browser PRO version

Are you a developer? Try out the HTML to PDF API

pdfcrowd.com

439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997 Póster con los números primos hasta 1000 (pdf)

Listado con los primos menores que 1.000.000 (txt)

Para ver los 10.000 primeros números primos pincha aquí Primos en el anillo de los enteros de Gauss

Cómo averiguar si un número es primo. El algoritmo más sencillo que puede utilizarse para saber si un número n es primo es el de la división. Se trata de ir probando para ver si tiene algún divisor propio. Para ello vamos dividiendo el número n entre 2, 3, 4, 5, ... , n-1. Si alguna de las divisiones es exacta (da resto cero) podemos asegurar que el número n es compuesto. Si ninguna de estas divisiones es exacta, el número n es primo. Este método puede hacerse más eficiente observando simplemente, que si un número es compuesto alguno de sus factores (sin contar el 1) debe ser menor o igual que √ n. Por lo tanto, el número de divisiones a realizar es mucho menor. Sólo hay que dividir entre 2, 3, 4, 5, ... , [√ n]. En realidad, bastaría hacer las divisiones entre los números primos menores o iguales que √ n. Ejemplo: Para probar que 227 es primo sabiendo que √227 = 15'0665... basta con ver que no es divisible entre 2, 3, 5, 7, 11 y 13. Este procedimiento resulta eficiente para números pequeños o que tienen factores pequeños. Sin embargo si el número tiene por ejemplo unas 20 cifras y es primo, habrá que realizar miles de millones de divisiones para comprobarlo. Aunque un ordenador pueda realizar millones de divisiones en un segundo, el tiempo necesario es open in browser PRO version

Are you a developer? Try out the HTML to PDF API

pdfcrowd.com

bastante considerable. Y cuando el número de dígitos aumenta el tiempo necesario ¡¡crece de forma exponencial!! Ejemplo práctico: Supongamos que queremos saber si un número de unas 50 cifras es primo. La raíz cuadrada de un número de este orden está en torno a 1025. Si un ordenador hace 1000 millones de divisiones por segundo, necesitará 1025/109 segundos; es decir, 1016 segundos. Este tiempo equivale, aproximadamente, a 1'6*1014 minutos, que son 2'7*1012 horas, o también 1'16*1011 días, aproximadamente 3'17*108 años. Que para hacer esto se necesiten 317.097.920 años se me antoja una tarea poco recomendable. Y si nos decidiésemos a llevarla a cabo, ¿sería útil esta información pasado todo este tiempo? O más drástico todavía, ¿seguiría existiendo nuestra especie entonces?

Debemos pues, buscar una alternativa que nos permita responder a este problema de una forma más favorable; necesitamos un algoritmo más eficiente. Una respuesta puede ser el teorema pequeño de Fermat. Este teorema afirma que si n es primo y mcd(a,n) = 1, entonces an-1 ≡ 1 (mod n). Hay que tener en cuenta que la exponenciación modular puede realizarse en un tiempo bastante favorable, si se hace de forma adecuada (hay algoritmos que nos dan la respuesta en tiempo polinómico) Ejemplo: Queremos comprobar si el número 15 es primo o no (utilizando esta propiedad). Tomamos a = 2, n = 15, y evaluamos 214 (mod 15). La respuesta es 214 ≡ 4 (mod 15). Podemos asegurar entonces que 15 es compuesto. Probemos con a = 2, n = 341, evaluamos 2340 (mod 341) y obtenemos que 2340 ≡ 1 (mod 341). Esto no nos permite deducir que 341 sea compuesto, pero tampoco que sea primo. Al probar con a=3 tenemos 3340 ≡ 56 (mod 341), lo cual implica que 341 es compuesto. A los números que se comportan como el 341 en el ejemplo anterior se les llama pseudoprimos para la base 2 (se comportan como un primo para a=2). Este comportamiento es bastante más peculiar peculiar para algunos números. Tomando por ejemplo a=2 y n=561, obtenemos que 2560 ≡ 1 (mod 561), 3560 ≡ 1 (mod 561), 5560 ≡ 1 (mod 561) y así con todas las bases con las que probemos. Es decir, se comporta como un primo para cualquier base que elijamos. Sin embargo, 561 es compuesto (561 = 3·11·17). A los números que como éste, son pseudoprimos para todas las bases se les llama números de Carmichael. Los números de Carmichael menores que 100.000 son 561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, open in browser PRO version

Are you a developer? Try out the HTML to PDF API

pdfcrowd.com

63973 y 75361. Desde luego, no parecen muy abundantes. Los expertos se preguntaban en los años 80 si serían un conjunto finito, con lo cual una vez identificados se podrían "evitar" fácilmente, aunque la creencia generalizada apuntaba a que el conjunto era infinito. Se demostró que si un número es de Carmichael debe ser libre de cuadrados y producto de al menos tres primos distintos. En 1994, Alford, Granville y Pomerance demostraron que existen infinitos números de Carmichael. De hecho, su resultado indica que para n suficientemente grande C(n) > n2/7, donde C(n) es la cantidad de números de Carmichael menores que n. Para evitar este contratiempo, podemos recurrir a un teorema un poco más fino debido a Euler. Este resultado afirma que si n es primo y mcd (a,n)=1, entonces a(n-1)/2 ≡ ±1 (mod n). Con esto evitamos que algunos números compuestos puedan pasar por primos como ocurre utilizando el teorema pequeño de Fermat. Ejemplo: Para comprobar que 91 es compuesto basta ver 245 ≡ 57 (mod 91). ¿Y que pasa con un número de Carmichael como el 561?. Veamos 2280 ≡ 1(mod 561), pero 5280 ≡ 67 (mod 561). Parece que esto funciona. Pero todavía podemos afinar un poco más. La idea es que si n es primo, entonces Zn es un cuerpo. Y en un cuerpo las únicas raíces cuadradas de 1 son 1 y -1. En el último ejemplo estamos diciendo que Z561 no es un cuerpo porque en él, la raíz de 1 es 67, y por tanto 561 no es primo. Si tomamos n-1 y lo dividimos entre 2 de forma sucesiva, mientras sea posible, estamos extrayendo raíces cuadradas y se trata de comprobar si los resultados dan siempre 1 ó -1. Esto da lugar al test de Miller-Rabin. Ejemplo: Tomando n = 561 hacemos 2280 (mod 561) ≡ 1 , 2140 (mod 561) ≡ 67, que continuaría con 270 y 235, pero ya no es necesario calcularlos porque tenemos que la raíz cuadrada de 1 es 67 (mod 561). Por tanto, 561 es compuesto. Si al llegar a 235 no obtenemos un resultado distinto de +1 ó -1, tendríamos que elegir otra base. Y ahí es donde podemos tener dificultades, porque si n es bastante grande quizá tengamos que probar con muchas bases y la respuesta tardará en llegar. Y podemos empezar a preguntarnos si la tardanza se debe a que n es primo o porque open in browser PRO version

Are you a developer? Try out the HTML to PDF API

pdfcrowd.com

es un compuesto que se comporta como un primo para un conjunto "grande" de bases. ¿Qué debemos hacer entonces? La solución es determinar el número de bases con las que tenemos que probar para asegurar que un número compuesto no pase la prueba como si fuese primo. Definiciones: Si un entero n compuesto e impar verifica la congruencia de Euler para la base b, entonces n es un pseudoprimo de Euler para la base b. Asímismo, si n pasa el test de Miller-Rabin para la base b, entonces n es un pseudoprimo fuerte para la base b. Los siguientes resultados nos dan la respuesta a la cuestión del párrafo anterior. Proposición: Si n es compuesto e impar, al menos la mitad de las bases b que verifican 0 ee existe un entero positivo t que satisface: i) t es libre de cuadrados. ii) 0 < t < (log n)c·log(log(log n)) y tal que s(t) > √ n , donde s(t) = Π { q ∈ Z+ / q primo y q-1 divisor de t }

El test APR seguiría entonces los siguientes pasos: Paso1: Introducimos un primo impar n. open in browser PRO version

Are you a developer? Try out the HTML to PDF API

pdfcrowd.com

Paso2: Buscamos (secuencialmente) un valor t que verifique s = s(t) > √ n. Paso3: Factorizamos t. A sus factores pi les llamamos primos iniciales. Paso4: Factorizamos s. A sus factores qi les llamamos primos euclídeos. Paso5: Se comprueba que mcd (s·t, n) = 1 (si no es el caso, n no es primo) Paso6: Para cada primo inicial p se tiene una de estas dos opciones: a) np-1 ≠ 1 (mod p2) b) np-1 ≡ 1 (mod p2) y para cada primo euclídeo q tal que p | q-1 existe un carácter ξ (aplicación de un grupo en el cuerpo de los números complejos) ξ: Zq* --------> Gp de orden p y conductor q, tal que G(ξ)n ∈ η(ξ)n·G(ξn) módulo nZ[ξp, ξq] para algún 1 ≠ η(ξ) ∈ Gp (revisar) Si se da el caso a) probamos con otro primo inicial y si se da b) seguimos con el paso 7. Paso7: Para cada i = 0, 1, 2, 3, ... , t-1 se calcula mcd( ni (mod s) , n). Si alguno de los resultados obtenidos es un número comprendido estrictamente entre 1 y n entonces el número n es compuesto. Si todos los resultados dan 1 ó n, entonces podemos estar seguros de que n es primo. (continuará con AKS, Agrawal 2002)

Cuántos números primos hay Una de las primeras preguntas que podemos hacernos es si la cantidad de números primos es finita o infinita. Euclides de Alejandría demostró que hay infinitos. Supongamos que existe solamente un número finito de primos. Sea C = { p1, p2, ... pn } el conjunto formado por todos ellos. Consideremos ahora el número M = p1×p2× ... pn+1. Como cada primo pi es mayor que 1, M es un número mayor que cualquiera de los pi; es decir, M no está en el conjunto C y por tanto es compuesto. Admitirá entonces una descomposición como producto de factores primos (por el teorema fundamental de la aritmética). Por hipótesis, estos factores sólo pueden estar entre los primos que aparecen en el conjunto C. Por tanto, existirá un primo q del conjunto C, tal que q | M y obviamente, q | p1×p2× ... pn. open in browser PRO version

Are you a developer? Try out the HTML to PDF API

pdfcrowd.com

Por consiguiente, q divide a la diferencia M - p1×p2× ... ×pn (que es 1). Pero ningún número primo divide a 1, y q es un número primo que divide a 1 (Contradicción). Concluimos entonces que el conjunto de los números primos no puede ser finito (q.e.d.) Hay otras demostraciones posibles, como la de Euler, que se obtiene como corolario de un teorema que afirma que la suma de la serie de los inversos de los números primos es divergente. Otra demostración más reciente (y sencilla de hacer) fue obtenida por Polya basándose en los números de Fermat. Más adelante veremos más sobre estos números que se definen como Fn=2^(2n)+1. Así, F1=5, F2=17, F3=257, etc. Polya observó y demostró que para todo k>0 se tiene que Fn y Fn+k son coprimos; es decir, no tienen factores comunes. Esto implica la infinitud de los números primos, ya que cada uno de los Fn da lugar a uno o varios números primos que no aparecen en los anteriores números de Fermat. Curioso, ¿no? La demostración es como sigue: Observamos en primer lugar que todos los números de Fermat son impares, evidente. En segundo lugar hay que ver que Fn+k -2 es múltiplo de Fn para todo k>0. Para ello sólo hay que seguir este cálculo:

Ahora, si m ¹ 1 es un divisor común de Fn y Fn+k , entonces m es divisor de Fn+k - 2 y Fn+k , y por tanto de su diferencia; es decir, m es divisor de 2 al mismo tiempo que de Fn que es impar. Contradicción. Podemos concluir entonces que cualesquiera dos números de Fermat no tienen ningún factor en común, q.e.d. Otra demostración interesante se la debemos a Erdos: Consideremos un número x fijo y sean p1, p2, ..., pn £ x, los números primos menores o iguales que x. .Como todo entero puede expresarse como producto de un cuadrado por un número libre de cuadrados, podemos escribir cada entero m £ x de la forma open in browser PRO version

Are you a developer? Try out the HTML to PDF API

pdfcrowd.com

donde ei ∈ {0, 1} y Q2 ≤ x. Podemos elegir los ei de 2n formas diferentes, y Q de r(x) formas y, por tanto, podemos asegurar que todos los números m ≤ x pueden escribirse alguna de estas 2n·r(x) formas, o sea, x ≤ 2n·r(x). Ahora, despejamos n de esta expresión, x ≤ 4n, y por tanto, n ≥ ln x / ln 4. El número de primos es mayor que cualquier número x fijado de antemano, q.e.d.

La sucesión de los números primos La sucesión de los números primos es poco predecible. No sabemos si obedecerán algún tipo de regla u orden que no hemos sido capaces de descubrir todavía. Durante siglos, las mentes más preclaras intentaron poner fin a esta situación pero sin éxito. Leonhard Euler comentó en una ocasión: "Los matemáticas han intentado en vano hasta la fecha descubrir algún orden en la sucesión de los números primos, y tenemos razones para creer que es un misterio en el que la mente no podrá penetrar nunca". En una conferencia dada por D. Zagier en 1975, éste dijo: "Hay dos hechos en torno a la distribución de los números primos que espero crean tan abrumadoramente, que quedarán por siempre grabadas en sus corazones. La primera es que a pesar de su sencilla definición y de su papel como ladrillos que construyen los números naturales, los números primos crecen como la mala hierba alrededor de los números naturales, simulando no obedecer otra ley que la del azar, y nadie puede predecir donde brotará el siguiente. El segundo hecho es incluso más asombroso, porque dice justamente lo opuesto: que los números primos hacen gala de una pasmosa regularidad, que hay leyes que gobiernan su comportamiento, y que obedecen esas leyes con una precisión casi militar" (Havil 2003) Euler commented "Mathematicians have tried in vain to this day to discover some order in the sequence of prime numbers, and we have reason to believe that it is a mystery into which the mind will never penetrate" (Havil 2003, p. 163). In a 1975 lecture, D. Zagier commented "There are two facts about the distribution of prime numbers of which I hope to convince you so overwhelmingly that they will be permanently engraved in your hearts. The first is that, despite their simple definition and role as the building blocks of the natural numbers, the prime numbers grow like weeds among the natural numbers, seeming to obey no other law than that of chance, and nobody can predict where the next one will sprout. The second fact is even open in browser PRO version

Are you a developer? Try out the HTML to PDF API

pdfcrowd.com

more astonishing, for it states just the opposite: that the prime numbers exhibit stunning regularity, that there are laws governing their behavior, and that they obey these laws with almost military precision" (Havil 2003, p. 171).

Pero el espíritu del hombre es obstinado y su inquietud por descubrir no conoce fronteras. Así, con el paso de los años y los siglos se ha ido avanzando a pequeños pasos, pero tantos, que al mirar atrás parecen gigantescos. En primer lugar presentamos una tabla con las cifras del número primo que ocupa el lugar 10n-ésimo. Lectura: El primo que ocupa el lugar 1000 (103) en la sucesión de los números primos es 7919. =n=

Primo 10n

Número de cifras |

=n=

Primo 10n

Número de cifras

0

2

1

|

11

2760727302517

13

1

29

2

|

12

29996224275833

14

2

541

3

|

13

323780508946331

15

3

7919

4

|

14

3475385758524527

16

4

104729

6

|

15

37124508045065437

17

5

1299709

7

|

16

394906913903735329

18

6

15485863

8

|

17

4185296581467695669

19

7

179424673

9

|

18

44211790234832169331

20

8

2038074743

10

|

19

465675465116607065549

21

9

22801763489

11

|

20

4892055594575155744537

22

10

252097800623

12

|

21

?

23

Tabla 3: Dígitos del 10n-ésimo primo open in browser PRO version

Are you a developer? Try out the HTML to PDF API

pdfcrowd.com

Otra posibilidad es contar cuántos primos acaban en una determinada cifra o cuántos son de una determinada forma como 4k+1 ó 4k+3. Por ejemplo, los números primos de la forma 4k+1 son 5, 13, 17, 29, 37, 41, 53, 61, 73, 89, 97... y los de la forma 4k+3 son 3, 7, 11, 19, 23, 31, 43, 47, 59, 67, 71, 79, 83... Para abreviar los llamaremos primos de tipo 1 y de tipo 3 respectivamente. Observamos que de los 24 primos enumerados, 11 son del tipo 1 y 13 del tipo 3. Contando el número de primos de cada tipo hasta 100.000 obtenemos: x

Primos 4k+1

Primos 4k+3

x

Primos 4k+1

Primos 4k+3

100 200 300

11 21 29

13 24 32

10.000 20.000 50.000

609 1.125 2.549

619 1.136 2.583

400 500 600

37 44 51

40 50 57

70.000 100.000 200.000

3.491 4.783 8.995

3.443 4.808 8.988

700 800 900

59 67 74

65 71 79

300.000 400.000 500.000

13.026 16.967 20.804

12.970 16.892 20.733

1000 2000 3000

80 147 222

87 155 207

600.000 700.000 800.000

24.573 28.306 32.032

24.524 28.236 31.918

5000 7000

329 442

339 457

900.000 1.000.000

35.676 39.266

35.597 39.231

Tabla 4: Recuento de primos de la forma 4k+1 y 4k+3 desde 3 hasta x open in browser PRO version

Are you a developer? Try out the HTML to PDF API

pdfcrowd.com

Observamos que los primos de tipo 3 van ganando por un escaso margen a los de tipo 1. Este fenómeno fue observado ya por Tchebychev, que se lo contaba en una carta a M. Fuss el 23 de marzo de 1853. Este sesgo resulta quizás inesperado en vista de un importante resultado en la teoría analítica de los números conocido como “el teorema de los números primos para progresiones aritméticas”. Este resultado nos dice que, para todo módulo a, los primos tienden a distribuirse equitativamente entre las diferentes progresiones an + b tales que mcd(a, b) = 1. Esto implica entre otras cosas que cualquier progresión aritmética contiene infinitos primos, hecho que fue conjeturado ya por Gauss y demostrado por Dirichlet en 1837. También nos permite deducir que existe "el mismo número de primos" acabados en 1, 3, 7 ó 9, tomando como progresiones aritméticas 10n+1, 10n+3, 10n+7 y 10n+9. x

open in browser PRO version

10n + 1 10n + 3 10n + 7 10n + 9

100

5

7

6

5

200

10

12

12

10

500

22

24

24

23

1.000

40

42

46

38

2.000

73

78

77

73

5.000

163

172

169

163

10.000

306

310

308

303

20.000

563

569

569

559

50.000

1274

1290

1288

1279

100.000

2387

2402

2411

2390

200.000

4478

4517

4503

4484

Are you a developer? Try out the HTML to PDF API

pdfcrowd.com

500.000

10386

10382

10403

10365

1.000.000

19617

19665

19621

19593

El intento de "controlar" los números primos llevo a muchos a la búsqueda de algún tipo de fórmula o expresión algebraica que generase la sucesión de los números primos. Goldbach demuestra en 1752 que no existe ningún polinomio con coeficientes enteros que dé números primos para cualquier valor entero. Años después Legendre demuestra que no existe ninguna función algebraica racional que cumpla tal requisito. Queda por decir que todavía se puede buscar un polinomio de forma que produzca una sucesión de números primos lo más larga posible. Euler propuso el polinomio n2 + n + 41 que da números primos para valores 0 ≤ n < 40 (también para 40 < n < 81 excepto n = 41, 44, 49, 56, 65 y 76 [sucesión cuadrática]). Otro resultado que hay que mencionar, a pesar de los resultados de Goldbach y Legendre, es que se ha podido encontrar un polinomio en 10 variables con coeficientes enteros que da números primos siempre que se sustituyan las variables por enteros no negativos. Jones, Sato, Wada y Wiens han hallado un polinomio de grado 25 en 26 variables cuyos valores positivos son exactamente los números primos. Otra fórmula que produce únicamente números primos tiene que ver con una constante q = 1'3063778..., conocida como constante de Mills (el menor número que tiene esta propiedad). Tomando f(n) = [θ^(3n)] siempre se obtienen números primos, donde [x] representa la parte entera de x. Los primeros valores de f(n) son 2, 11, 1361, 2521008887, ... No se sabe todavía si θ es racional o irracional (febrero 2012). Hacia 1845 Joseph Bertrand propone que para cada entero positivo n, existe al menos un primo p tal que n < p < 2n. Esta proposición conocida como postulado de Bertrand, fue demostrada por Tchebychev en 1850. En 1919, Ramanujan prueba que para n > 5, existen al menos dos primos entre n y 2n; para n > 8, existen al menos tres primos entre n y 2n; para n > ?, existen al menos cuatro primos entre n y 2n. De forma más general, demuestra que para cada k > 0, existen k primos entre n y 2n salvo para un número finito de casos. Erdös, en 1932, consigue una prueba bastante más simple del caso de dos primos entre n y 2n para n>6, añadiendo además que uno de esos open in browser PRO version

Are you a developer? Try out the HTML to PDF API

pdfcrowd.com

dos primos debe ser de la forma 4k+1 y el otro de la forma 4k+3. Otra cuestión similar (pero más restrictiva) había sido propuesta por Legendre unos años antes de la demostración de Tchebychev. Legendre conjeturó que existe al menos un primo entre n² y (n+1)² para todo entero n > 0. La conjetura sigue sin demostrarse. (febrero 2012)

El teorema del número primo π(n) ≈ n/log n ≈ Li(x) La función que nos dice cuántos números primos hay en el intervalo [0, n] se representa por π(n) = # { p ≤ n , p primo}. Legendre y Gauss dedicaron mucho tiempo y esfuerzo a calcular números primos y contar los que había en grandes intervalos. Conjeturaron que el valor de π(n) podía aproximarse por n/log(n). Tchebychev, en su intento de demostrar esta conjetura, obtiene que existen dos constantes c1 y c2 verificando 0 < c1 ≤ 1 ≤ c2 < ∞ tales que c1 · n / log(n) ≤ π(n) ≤ c2 · n / log(n) En 1881, James J. Sylvester da otro resultado similar pero mucho más fino; a saber, que 0,96695 ≤ c1 ≤ 1 ≤ c2 ≤ 1,04423 El teorema del número primo nos da una aproximación asintótica al valor de π(n) y se expresa de la siguiente forma:

open in browser PRO version

Are you a developer? Try out the HTML to PDF API

pdfcrowd.com

Fue demostrado en primer lugar por Hadamard y de la Vallée Poussin en 1896 basándose en algunas propiedades de la función Zeta de Riemann. Una mejor aproximación de π(x) es la función Li(x).

lo cual equivale a decir que

se aproxima mejor a π(n) que n/log(n).

En 1901, Koch demuestra que la Hipótesis de Riemann es equivalente a la desigualdad | π(x) - Li(x) | ≤ c·√x·ln(x) para alguna constante c. Erdös en 1949 y Selberg en 1950 dieron demostraciones más sencillas en el sentido que no se apoyan en "herramientas de gran calibre" como la función zeta o similares. Para valores de n no demasiado grandes se comprobó que π(n) < Li(n), lo cual dio lugar a la conjetura de que la desigualdad se verificaba para todo valor de n. Sin embargo, la conjetura fue refutada en 1914 por Littlewood al demostrar que ambas funciones se cruzan infinitas veces. Skewes demostró posteriormente que el primer encuentro de ambas funciones ocurre para un n menor que 10^(10^(10^(34))). Este número ha sido reducido después hasta 10371.

open in browser PRO version

Are you a developer? Try out the HTML to PDF API

pdfcrowd.com

x

π(x)

Li(x)-π(x)

θ(x)

Comments

106

78,498

129

-0.209

107

664,579

336

-0.1809

108

5,761,455

753

-0.1339

Meissel 1871

109

50,847,534

1,700

-0.0994

Meissel 1886 (Corrected)

1010

455,052,511

3,103

-0.0594

Lehmer 1959 (Corrected)

1011

4,118,054,813

11,587

-0.0725

1012

37,607,912,018

38,262

-0.0781

1013

346,065,536,839

108,970

-0.0723

Bohmann 1972 (Corrected)

1014

3,204,941,750,802

314,889

-0.0678

Lagarias Miller Odlyzko 1985

1015

29,844,570,422,669

1,052,618

-0.0735

LMO 1985

1016

279,238,341,033,925

3,214,631

-0.0726

LMO 1985

1017

2,623,557,157,654,233

7,956,588

-0.0581

Deléglise Rivat 1994

1018

24,739,954,287,740,860

21,949,554

-0.05177

Deléglise Rivat 1994

1019

234,057,667,276,344,607

99,877,774

-0.0760

Deléglise 1996

1020

2,220,819,602,560,918,840

222,744,643

-0.0546

Deléglise 1996

2*1020

4,374,267,703,076,959,271

472,270,046

-0.0823

X. Gourdon 2000 Nov

1021

21,127,269,486,018,731,928

597,394,253

-0.0471

X. Gourdon 2000 Nov

2*1021

41,644,391,885,053,857,293 1,454,564,714 -0.0816

pi(x) project, 2000 Dec

4*1021

82,103,246,362,658,124,007 1,200,472,717 -0.0479

pi(x) project, 2000 Dec

22

10 open in browser PRO version

Are you a developer? Try out the HTML to PDF API

pdfcrowd.com

1022

201,467,286,689,315,906,290 1,932,355,207 -0.0491

pi(x) project, 2000 Dec

1.5*1022 299,751,248,358,699,805,270 2,848,114,312 -0.0592

P. Demichel, X. Gourdon, 2001 Feb

2*1022 397,382,840,070,993,192,736 2,732,289,619 -0.0493

pi(x) project, 2001 Feb

4*1022 783,964,159,847,056,303,858 5,101,648,384 -0.0655 pi(x) project, 2001 Mar (Current world record)

(Añadir Hardy-Wright pag 10)

Números de Fermat Un número de Fermat es un número de la forma 2^2n + 1. La sucesión de números de Fermat para n = 0, 1, 2, ... sería entonces 3, 5, 17, 257, 65537, 4294967297, 18446744073709551617, ... Cada uno de ellos duplica (o casi) al anterior en número de cifras, lo cual da una idea de la rapidez con la que crecen. Fermat comprobó que los cinco primeros números eran primos y conjeturó que posiblemente todos ellos lo fuesen.

El gran cíclope (Euler) fue el encargado de desmentir esta hipótesis al demostrar que F5 = 4294967297 es divisible por 641. Además hasta la fecha (abril 2007) no se han vuelto a encontrar más primos entre los números de Fermat. open in browser PRO version

Are you a developer? Try out the HTML to PDF API

pdfcrowd.com

Factores de los números de Fermat son: 274.177 de F6, 59.649.589.127.497.217 de F7, 1.238.926.361.552.897 de F8, 2.424.833 de F9, 45.592.577 de F10, ...

Primos de Mersenne y números perfectos A los números primos de la forma 2n-1 se les llama primos de Mersenne. Es fácil demostrar que si 2n-1 es primo, entonces n debe ser primo. Si suponemos que n es compuesto, pongamos n = a·b (a, b>1), entonces 2n-1 = (2a)b-1 = (2a-1)·(2a(b-1) + 2a(b-2) + ... + 2a + 1) y por lo tanto 2n-1 también es compuesto. Pero el hecho de que n sea primo no asegura que 2n-1 sea primo. Una propiedad destacable es que si p es primo y 2p-1 es compuesto entonces sus factores son de la forma 2kp+1. Por ejemplo pero 211-1 = 2047 = 23·89 y 23 = 2·11+1, 89 = 8·11+1. Todavía no se sabe si el número de primos de Mersenne es finito o infinito (diciembre 2010) Un número entero se llama perfecto si es igual a la suma de sus divisores (sin contar el propio número). Los casos más sencillos son 6=1+2+3 y 28=1+2+4+7+14. Euclides demostró que si 2n-1 es un número primo, entonces 2n-1(2n-1) es un número perfecto. Euler demostró que todos los números perfectos pares son de este tipo. Por tanto, no se sabe si hay una cantidad finita o infinita de números perfectos. Tampoco se sabe si existe algún número perfecto que sea impar. Tabla de números primos de Mersenne conocidos (diciembre 2010) Exponente open in browser PRO version

Dígitos

Are you a developer? Try out the HTML to PDF API

Año

Descubridor pdfcrowd.com

open in browser PRO version

2

1

3

1

5

2

7

3

13

4

1456

Anónimo (H.Regius1)

17

8

1588

Cataldi (J. Scheybl2)

19

10

1588

Cataldi

31

12

1772

Euler

61

19

1883

Pervushin

89

27

1911

Powers

107

33

1914

Powers

127

39

1876

Lucas

521

157

1952

Robinson

607

183

1952

Robinson

1279

386

1952

Robinson

2203

664

1952

Robinson

2281

687

1952

Robinson

3217

969

1937

Riesel

4253

1.281

1961

Hurwitz

Are you a developer? Try out the HTML to PDF API

pdfcrowd.com

open in browser PRO version

4423

1.332

1961

Hurwitz

9689

2.917

1963

Gillies

9941

2.993

1963

Gillies

11213

3.376

1963

Gillies

19937

6.002

1971

Tickerman

21701

6.533

1978

Noll y Nickel

23209

6.987

1979

Noll

44497

13.395

1979

Nelson y Slowinski

86243

25.962

1982

Slowinski

110503

33.265

1988

Colquitt y Welsh

132049

39.751

1983

Slowinski

216091

65.050

1985

Slowinski

756839

227.832

1992

Slowinski y Gage

859433

258.716

1994

Slowinski y Gage

1257787

378.632

1996

Slowinski y Gage

1398269

420.921

1996

GIMPS (Armengaud, Woltman, et. al.)

2976221

895.932

1997

GIMPS (Spence, Woltman, et. al.)

Are you a developer? Try out the HTML to PDF API

pdfcrowd.com

3021377

909.526

1998

GIMPS, PrimeNet (Clarkson, Woltman, Kurowski et. al.)

6972593

2.098.960

1999

GIMPS (Hajratwala, Woltman, Kurowski et. al.)

13466917

4.053.946

2001

Michael Cameron (GIMPS, PrimeNet)

20996011

6.320.430

2003

Michael Shafer's (GIMPS, PrimeNet)

Nota: No se han incluido los últimos primos (que si aparecen en la tabla de abajo) porque aunque se sabe quien es la madre todavía no sabemos quien es el padre; quiero decir, que se sabe que son primos de Mersenne, pero no se sabe si son los que siguen inmediatamente a los anteriores. (1) Aunque el quinto número perfecto (primo de Mersenne)

Cazando primos titánicos Los números primos más grandes conocidos hoy (diciembre de 2010) son: Primo open in browser PRO version

Dígitos

Fecha

Are you a developer? Try out the HTML to PDF API

Nombre

Descubridor pdfcrowd.com

243112609-1

12.978.189

2008

Mersenne 47??

242643801-1

12.837.064

2009

Mersenne 46??

237156667-1

11.185.272

2008

Mersenne 45??

232582657-1

9.808.358

2006

Mersenne 44??

230402457-1

9.152.052

2005

Mersenne 43??

225964951-1

7.816.230

2005

Mersenne 42?

224036583-1

7.235.733

2004

Mersenne 41?

Josh Findley (GIMPS, PrimeNet)

220996011-1

6.320.430

2003

Mersenne 40

Michael Shafer's (GIMPS, PrimeNet)

213466917-1

4.053.946

2001

Mersenne 39

Michael Cameron (GIMPS, PrimeNet)

27653.29167433+1

2.759.677

2005

x

28433.27830457+1

2.357.207

2004

x

26972593-1

2.098.960

1999

Mersenne 38

5359.25054502+1

1.521.561

2003

x

4847.23321063+1

999.744

2005

x

23021377-1

909.526

1998

Mersenne 37

22976221-1

895.932

1997

Mersenne 36

open in browser PRO version

Are you a developer? Try out the HTML to PDF API

Hajratwala, Woltman, Kurowski et. al. (GIMPS, PrimeNet)

Clarkson, Woltman, Kurowski et. al. (GIMPS, PrimeNet) Spence, Woltman, pdfcrowd.com

22976221-1

895.932

1997

Mersenne 36

1372930131072+1

804.474

2003

Fermat General

1361244131072+1

803.988

2004

Fermat General

1176694131072+1

795.695

2003

Fermat General

et. al. (GIMPS)

La conjetura de los primos gemelos Dos primos se llaman gemelos si se diferencian en dos unidades. Por ejemplo 5 y 7 ó también 29 y 31. Saber si hay una cantidad finita o infinita de tales parejas es un problema abierto en mayo de 2007, aunque se cree ampliamente que hay infinitos. En 1919 Viggo Brun demostró que la suma de los inversos de los primos gemelos converge a un número que llamaremos la constante de Brun para primos gemelos. Se representa como B2 y su valor se estima en torno a 1.902160583104. Alfonso de Polignac (1817-1890) fue un matemático francés que conjeturó que para cada número natural k>0, existen infinitas parejas de primos que están a una distancia de 2k. El caso k=1 es la conjetura de los primos gemelos. De forma similar al teorema del número del número primo, la conjetura de Hardy-Littlewood postula que el número de primos p£ N, tales que p+2 es también primo se aproxima asintóticamente a 2·C 2·N/(Ln N)2, donde C2 = 0,6601618158... En 1940, Paul Erdös demuestra que existe una constante c