Los N´umeros Primos: un vasto campo de exploraci´on Juan Pablo Prieto Instituto de Matem´atica y F´ısica Universidad de Talca

1

Introducci´ on

Este trabajo pretende mostrar algunas, muy pocas, facetas del estudio de los n´ umeros primos. Se espera que esta introducci´ on pueda dar lugar a revalorar la aritm´etica, aquella de los antiguos, la de las preguntas ingenuas, simples. Una ventaja de la aritm´etica es que, adem´as de su simplicidad y rigor (es de aquellas disciplinas que permite introducir los elementos m´ as importantes de una demostraci´ on: hip´ otesis, tesis, reducci´on al absurdo, etc.) y simples reglas del juego (la axiom´atica de la aritm´etica es intuitiva), permite experimentar num´ericamente, especialmente con la llegada de los computadores. Por esta raz´on, los invito a explorar algunas preguntas, con la idea de motivarlos para incluir esta tem´ atica, a nivel de exploraci´ on (investigaci´ on) en sus aulas. Partes de esta exposici´on requerir´ an de un conocimiento de elementos de probabilidad y c´ alculo integral. Uno de los grandes atractivos de la aritm´etica es justamente su complicidad con las otras ramas de la matem´atica como: c´alculo, variable compleja, geometr´ıa, algebra abstracta, etc. Como sabemos, los enteros distintos de cero, se dividen en tres clases: 1. −1, 1: unidades 2. ±2, ±3, ±5, ±7, ±11, . . .: primos 3. ±4, ±6, ±8, ±9, . . .: compuestos Primero, para evitar considerar los signos, trabajaremos con enteros positivos, en este caso un entero positivo n es un primo si n > 1 y sus u ´nicos divisores positivos son 1 y n. Los primos constituyen las part´ıculas elementales de la aritm´etica, en virtud del Teorema Fundamental de la Aritm´etica, que nos dice: Teorema 1.1 Todo entero mayor que 1 se puede expresar de manera u ´nica como producto de primos n = pe11 · · · pekk donde ei es un entero positivo. Una ventaja de los primos, por sobre las part´ıculas elementales es que hay infinitos (este es el gran Teorema de Eucl´ıdes, cuya demostraci´on todav´ıa brilla por su elegancia y potencia). 1

Demostraci´ on 1 (Eucl´ıdes). Por contradicci´ on. Supongamos que hay finitos primos y list´emoslos: p1 , . . . , pk . Sea N = p1 · · · pk + 1. Es claro que N − 1 es divisible por todos los primos pj . Adem´as, N es divisible por alg´ un pi , de modo que pi divide a N − (N − 1), lo que evidentemente es imposible. Existe otra demostraci´on famosa dada por Euler en el siglo XVII: Demostraci´ on 2 (Euler). La serie

p  1

p

diverge (esto requiere de un trabajo adicional de demostraci´ on).

En este trabajo se analizar´ an algunas preguntas cualitativas y cuantitativas acerca de los primos, y una aplicaci´ on.

2

¿C´ omo se encuentran o construyen los n´ umeros primos?

Un principio b´ asico que muestra lo elusivo que son los primos es el siguiente: Los primos se encuentran usando cribas, no usando f´ ormulas. Los matem´aticos que se dedican a buscar primos son como los buscadores de oro, y de hecho usan (b´asicamente) la misma herramienta: una criba. Para determinar si un n´ umero n es primo, el modo m´as simple (y a la vez √ menos satisfactorio) es: probar si n es divisible por 2, 3, 5, 7, . . . , hasta n − 1 (aunque basta probar hasta n). La criba m´ as antigua es la de Erast´ otenes. La idea es simple, se listan los n´ umeros y de la lista se tarjan todos los m´ ultiplos de 2, luego los de 3 y as´ı sucesivamente. Los n´ umeros que quedan sin marcar son los primos: 2 3 /4 5 /6 7 /8 /9 10 / 11 18 / 19 20 / 21 / 22 / 23 24 / 25 / 26 / 27 / 34 / 35 / 36 / 37 38 / 39 / 40 / 41 42 / 43 50 / 51 / 52 / 53 54 / 55 / 56 / 57 58 / 59

12 / 28 / 44 / 60 /

13 29 45 / 61

14 / 15 / 16 / 17 30 / 31 32 / 33 / 46 / 47 48 / 49 / 62 / 63 / 64 / 65 /

En la b´ usqueda de primos, la demostraci´ on de Eucl´ıdes da lugar a un m´etodo seguro para la obtenci´ on de nuevos primos. La construcci´ on que mostramos comienza con el 2 y entrega al menos un nuevo primo en cada paso.

N2

= 2+1

N3 N4

= =

2·3+1=7 2 · 3 · 7 + 1 = 43

N5

=

2 · 3 · 7 · 43 + 1 = 1807 = 13 · 139

N6

=

2 · 3 · 7 · 43 · 139 + 1 = 251.085 = 5 · 50207

Como ya dijimos, los primos se encuentran con cribas, esto porque no existen f´ ormulas para construir s´ olo primos (ning´ un polinomio puede producir primos u ´nicamente), sin embargo, hay algunas f´ ormulas famosas que producen un n´ umero asombroso de primos: 2

1. x2 − x + 17 es primo para x = 0, 1, 2, 3, 4, . . . , 16 2. x2 − x + 41 es primo para x = 0, 1, 2, 3, . . . , 40 3. 22x2 − 199 produce 150 primos para x entre 0 y 198. Los primos de Mersenne. Un n´ umero de la forma Mn = 2n − 1 se llama n´ umero de Mersenne. Estos n´ umeros tienen un sitial importante en la aritm´etica debido a que los m´as grandes primos conocidos son justamente primos de esta forma (ver la tabla de los Primos Top Ten). Adem´ as, como veremos, para estos n´ umeros existe un algoritmo concreto para determinar su primalidad. Observemos qu´e sucede con estos n´ umeros analizando el exponente n: • Si n = 2k con k > 1 entonces: 22k − 1 = (2k − 1)(2k + 1). • Si n es compuesto, n = pq, entonces 2pq − 1 = (2p − 1)(2p(q−1) + · · · + 1). De modo que si n es compuesto el n´ umero Mn no es primo. Sin embargo, si n es primo no necesariamente Mn ser´a primo. El Test de Lucas-Lehmer chequea la primalidad de Mp = 2p − 1. Mp es primo ⇐⇒ Mp divide a Sp 2 donde Sn = Sn−1 − 2 y S2 = 4 (observe que la sucesi´on comienza en S2 ).

En la pr´ actica este Test es muy “caro”, ya que la sucesi´on Sn , para n > 1, es: 4, 14, 194, 37.634, . . . . Por si alguien desea encontrar un nuevo (o antiguo) primo de Mersenne, el siguiente pseudoc´ odigo le permitir´ a escribir un programa para buscarlo (Test de Lucas-Lehmer): TLL(p): s:= 4; for i from 2 to p-1 do s:= sˆ2 - 2 mod 2ˆp - 1; if s==0 then 2ˆp - 1 es primo else 2ˆp - 1 es compuesto; end Se conocen s´olo 36 primos de Mersenne, de hecho de la lista de los primos “top ten” (los primos conocidos m´as grandes hasta septiembre de 1997), seis de ellos son primos de Mersenne (ver [Cal]):

3

Primos Top Ten primo

d´ıgitos

quien

a˜ no

22.976.221 − 1 21.398.269 − 1 21.257.787 − 1 2859.433 − 1 2756.839 − 1 5 ∗ 2240.937 + 1 391.581 ∗ 2216.193 − 1 2216.091 − 1 3 ∗ 2213.321 + 1 5 ∗ 2209.787 + 1

895.932 420.921 378.632 258.716 227.832 72.530 65.087 65.050 64.217 63.153

Spence, Woltman et al. Armengaud, Woltman, et al. Slowinski y Gage Slowinski y Gage Slowinski y Gage Jeffrey Young Brown, Noll, et al. Slowinski Jeffrey Young Jeffrey Young

1997 1996 1996 1994 1992 1997 1989 1985 1997 1997

Observaci´ on 2.1 Los primos de Mersenne dan lugar a los n´ umeros perfectos (P es perfecto si es la suma de sus divisores propios). Euler prob´ o que todos los n´ umeros perfectos pares tienen la forma P = Mp 2p−1 donde Mp es un primo de Mersenne. Por lo tanto, se conocen s´ olo 36 n´ umeros perfectos (no se sabe si hay n´ umeros perfectos impares). Primos de Fermat n

Fermat afirm´ o que todos los n´ umeros de la forma Fn = 22 + 1 son primos. Una peque˜ na tabla nos muestra los primeros valores: Fo F1 F2 F3 F4 F5

= = = = = =

3 5 17 257 65537 4294967297

Euler prob´ o, 100 a˜ nos despu´es, que F5 no es primo, simplemente al descubrir que F5 = 641 · 6700417 Hasta el momento s´olo se conocen 5 primos de Fermat. Asimismo, se ha probado que F6 , F7 , F8 , F11 , F12 , F13 , F73 son compuestos (este u ´ ltimo n´ umero tiene m´as de 1021 d´ıgitos). El n´ umero de Fermat m´as peque˜ no del que aun no se sabe su estado es F20 que tiene 315.653 d´ıgitos. Sin embargo, se sabe que F3310 , que tiene m´as de 10990 d´ıgitos, no es primo y uno de sus factores es 5 · 23313 + 1. As´ı como los primos de Mersenne est´an relacionados con los n´ umeros perfectos, los primos de Fermat est´an relacionados con las construcciones geom´etricas con regla y comp´ as. Esta relaci´on la descubri´ o Gauss en su adolescencia. Teorema 2.2 (Gauss). El pol´ıgono regular de n lados es constructible con regla y comp´ as si y s´ olo si n es de la forma n = 2k · p1 · · · ps con k entero ≥ 0 y pi primos distintos de Fermat.

4

Por ejemplo, los pol´ıgonos regulares de n lados con n = 3, 4, 5, 6, 8, 10, 12, . . ., 17 son constructibles con regla y comp´as. Pero si n = 7, 9, 11, 13, 14, 18, es imposible construir un pol´ıgono regular de n lados con regla y comp´as. La construcci´on del hept´ agono con regla y comp´ as fue un problema abierto por m´ as de 2.000 a˜ nos. A pesar de todo lo que se ha trabajado con los n´ umeros de Fermat, la siguiente conjetura parece decir que la afirmaci´ on original de Fermat dista mucho de ser v´ alida. Conjetura 2.3 Hay un n´ umero finito de primos de Fermat.

3

¿Es 2.152.302898.747 un n´ umero primo?

Para encontrar primos peque˜ nos (menores que 10.000.000), la manera m´ as eficiente de hacerlo es usando la Criba de Erast´ otenes. Evidentemente, es m´as dif´ıcil determinar si un n´ umero de 20 d´ıgitos es primo usando divisi´ on y es imposible si el n´ umero tiene 200 d´ıgitos. Para esto se necesitan algoritmos mucho m´as eficientes. El peque˜ no Teorema de Fermat (no confundir con el Ultimo) nos da una poderosa herramienta para decidir si un n´ umero es compuesto: Teorema 3.1 Peque˜ no Teorema de Fermat: Si p es primo y si a es cualquier entero, entonces ap ≡ a (mod p). En particular, si p no divide a a, entonces ap−1 ≡ 1 (mod p). Dado n > 1 elijamos un entero a > 1 y calculemos an−1 (mod n)1 , si el resultado no es 1, n ser´a compuesto. Si el resultado es 1, entonces n podr´ıa ser primo, que suele llamarse un “primo probable en base a” (pseudo primo). Por ejemplo, hay 1.091.987.405 primos menores que 25.000.000.000, pero s´ olo 21.853 pseudo primos en base 2. Puede haber pocos pseudo primos, pero en todo caso hay infinitos en cualquier base a. Con el objeto de mejorar esta prueba de primalidad, podemos intentar usar diferentes bases 2, 3, 5, . . . , etc. Sin embargo, en este caso nos encontraremos con los n´ umeros de Carmichael. Definici´ on 3.2 Un entero compuesto n se llama, n´ umero de Carmichael si an−1 ≡ 1 (mod n) para todo entero a relativamente primo con n. Ejemplos: 561, 1105, 1729, 2465, 2821. A pesar de su “rareza”, tambi´en hay infinitos n´ umeros de Carmichael. Otro test de primalidad, que en teor´ıa es un criterio para determinar si un n´ umero es primo, pero que en la pr´ actica es in´ util, es el siguiente: Teorema 3.3 de Wilson. n es primo

⇐⇒

(n − 1)! ≡ −1(mod n)

Para probar, usando este criterio, que 101 es primo habr´ıa que calcular 100!, que es un n´ umero de 160 d´ıgitos. Existen muchas otras pruebas de primalidad, basadas en diferentes resultados en teor´ıa de n´ umeros, algunas de las cuales son extremadamente avanzadas para exponer aqu´ı. 1 En el ap´ endice se presenta un programa escrito en Pascal para realizar esto usando cuadrados sucesivos, es decir descomponiendo el exponente en base 2

5

4

¿Cu´ antos primos hay?

Pregunta aparentemente simple que, sin embargo, tiene muchas aristas, como veremos m´as adelante. Una posible respuesta es justamente la que dio Eucl´ıdes: hay infinitos primos. Esta misma respuesta nos obliga a hacernos una mejor pregunta. ¿C´ omo se distribuyen los primos? ¿Cu´ antos primos hay menores que un cierto n´ umero? ¿Cu´al es la probabilidad que un n´ umero n sea primo? Si tenemos una ventana de largo k y la deslizamos sobre la recta real, ¿cu´antos primos vemos? La respuesta ingenua a la u ´ltima pregunta es un poco m´ as sencilla, vemos algunos, pocos y menos primos, a medida que nos deslizamos. De hecho hay intervalos de longitud arbitraria sin ning´ un primo. Por ejemplo, el intervalo [1001! + 2, 1001! + 1001] no contiene ning´ un primo. La respuesta a la segunda pregunta, es conocida como el Teorema del N´ umero Primo, que fue demostrado en 1896 por Hadamard e independientemente por de la Vall´ee Poussin. Sea π(x) el n´ umero de primos menores o iguales a x. Por ejemplo los primos menores que 100 son: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 89, 97. Con estos datos, π(3) = 2, π(25) = π(26) = π(27) = 9 y π(45) = 14. De hecho, en el intervalo [1001! + 2, 1001! + 1001] la funci´ on π es constante. Usando una tabla de n´ umeros primos (que se puede encontrar en cuasi cualquier texto de aritm´etica) es posible graficar π(x) en un intervalo (por ejemplo entre 0 y 100). A´ un cuando el gr´ afico aparece como irregular, hay claramente un comportamiento definido para esta funci´ on. El conocimiento de π(x) da una idea de la distribuci´ on de los primos. Gauss y Legendre propusieron las siguientes aproximaciones (obtenidas en forma emp´ırica):  x dt π(x) ≈ := li(x) : Gauss (1791) ln t 2 π(x) ≈

x : ln x − 1, 08336

Legendre (1798)

Otra aproximaci´ on est´a dada simplemente por

x . ln x

Teorema 4.1 del N´ umero Primo (TNP): La cantidad de primos menores o iguales a x es asint´ otico a x/ ln x. Decimos que a(x) es asint´ otico a b(x) si lim a(x)/b(x) = 1. No significa que a(x) − b(x) se aproxime a cero. x→∞

Veamos num´ericamente estas aproximaciones

6

x

π(x)

x/ ln x

x/(ln x − 1)

1000 10000 100000 1000000 10000000 100000000

168 1229 9592 78498 664579 5761455

145 1086 8686 72382 620420 5428681

169 1218 9512 78030 661459 5740304

Consecuencias: 1. Se puede aproximar π(x) por x/(ln x − 1) Consecuencia del TNP. 2. El n-´esimo primo es aproximadamente n ln n. Equivalente al TNP. 3. Dado que aproximadamente. n/ ln n de los enteros menores o iguales a n son primos, la probabilidad de que uno sea primo es alrededor de 1/ ln n. Estudio probabil´ıstico de los primos. En esta parte pretendemos justificar el TNP usando un an´ alisis heur´ıstico. Se debe tener en consideraci´on que la argumentaci´ on vertida aqu´ı no es rigurosa, que por lo dem´ as era la manera de hacer matem´atica por muchos siglos. En todo caso, las conjeturas de Gauss y Legendre respecto de la funci´ on π(x) fueron obtenidas con evidencia emp´ırica. La probabilidad que un n´ umero cualquiera sea divisible por p es 1/p ya que, partiendo de 1: 1, p, 2p, 3p, . . . cada p enteros uno es divisible por p. As´ı, la probabilidad que x no sea divisible por ning´ un primo menor que x es:  W (x) =

1 1− 2



1 1− 3



1 1− 5



 

··· =

pi