Número primo de Mersenne

De Wikipedia, la enciclopedia libre
(Redirigido desde «Número de Mersenne»)
Saltar a: navegación, búsqueda

Se dice que un número M es un número de Mersenne si es una unidad menor que una potencia de 2. M_n=2^n-1.

Un número primo de Mersenne es un número de Mersenne que es primo, es decir, M_n=2^n-1, con n primo (no es una condición suficiente que n sea primo para que M_n lo sea). Se denominan así en memoria del filósofo del siglo XVII Marin Mersenne quien en su Cognitata Physico-Mathematica realizó una serie de postulados sobre ellos que sólo pudo refinarse tres siglos después. También compiló una lista de números primos de Mersenne con exponentes menores o iguales a 257, y conjeturó que eran los únicos números primos de esa forma. Su lista sólo resultó ser parcialmente correcta, ya que por error incluyó M67 y M257, que son compuestos, y omitió M61, M89, y M107, que son primos; y su conjetura se revelaría falsa con el descubrimiento de números primos de Mersenne más grandes. No proporcionó ninguna indicación de cómo dio con esa lista, y su verificación rigurosa sólo se completó más de dos siglos después.

Actualmente (febrero de 2013), sólo se conocen 48 números primos de Mersenne, siendo el mayor de ellos M57.885.161 = 257.885.161−1, un número de más de diecisiete millones de cifras. El número primo más grande que se conocía en una fecha dada casi siempre ha sido un número primo de Mersenne: desde que empezó la era electrónica en 1951 siempre ha sido así salvo en 1951 y entre 1989 y 1992.

Lista de los números primos de Mersenne conocidos[editar]

Gráfico que representa el número de cifras de cada uno de los primos de Mersenne conocidos. Nótese que la escala vertical es logarítmica.
Gráfico del número de dígitos del primo de Mersenne más grande que se conocía cada año (era electrónica). La escala vertical es logarítmica.

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

# n Mn Nº de cifras
de Mn
Fecha del
descubrimiento
Descubridor
1 2 3 1 antigüedad desconocido
2 3 7 1 antigüedad desconocido
3 5 31 2 antigüedad desconocido
4 7 127 3 antigüedad desconocido
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-01-1952 Robinson (SWAC)
14 607 531137992…031728127 183 30-01-1952 Robinson (SWAC)
15 1.279 104079321…168729087 386 25-06-1952 Robinson (SWAC)
16 2.203 147597991…697771007 664 07-10-1952 Robinson (SWAC)
17 2.281 446087557…132836351 687 09-10-1952 Robinson (SWAC)
18 3.217 259117086…909315071 969 08-09-1957 Riesel
19 4.253 190797007…350484991 1.281 03-11-1961 Hurwitz
20 4.423 285542542…608580607 1.332 03-11-1961 Hurwitz
21 9.689 478220278…225754111 2.917 11-05-1963 Gillies
22 9.941 346088282…789463551 2.993 16-05-1963 Gillies
23 11.213 281411201…696392191 3.376 02-06-1963 Gillies
24 19.937 431542479…968041471 6.002 04-03-1971 Tuckerman
25 21.701 448679166…511882751 6.533 30-10-1978 Noll y Nickel
26 23.209 402874115…779264511 6.987 09-02-1979 Noll
27 44.497 854509824…011228671 13.395 08-04-1979 Nelson y Slowinski
28 86.243 536927995…433438207 25.962 25-09-1982 Slowinski
29 110.503 521928313…465515007 33.265 28-01-1988 Colquitt y Welsh
30 132.049 512740276…730061311 39.751 20-09-1983 Slowinski
31 216.091 746093103…815528447 65.050 06-09-1985 Slowinski
32 756.839 174135906…544677887 227.832 19-02-1992 Slowinski y Gage
33 859.433 129498125…500142591 258.716 10-01-1994 Slowinski y Gage
34 1.257.787 412245773…089366527 378.632 03-09-1996 Slowinski y Gage
35 1.398.269 814717564…451315711 420.921 13-11-1996 GIMPS / Joel Armengaud
36 2.976.221 623340076…729201151 895.932 24-08-1997 GIMPS / Gordon Spence
37 3.021.377 127411683…024694271 909.526 27-01-1998 GIMPS / Roland Clarkson
38 6.972.593 437075744…924193791 2.098.960 01-06-1999 GIMPS / Nayan Hajratwala
39 13.466.917 924947738…256259071 4.053.946 14-11-2001 GIMPS / Michael Cameron
40 20.996.011 125976895…855682047 6.320.430 17-11-2003 GIMPS / Michael Shafer
41 24.036.583 299410429…733969407 7.235.733 15-05-2004 GIMPS / Josh Findley
42 25.964.951 122164630…577077247 7.816.230 18-02-2005 GIMPS / Martin Nowak
43 30.402.457 315416475…652943871 9.152.052 15-12-2005 GIMPS / Curtis Cooper y Steven Boone
44 32.582.657 124575026…053967871 9.808.358 04-09-2006 GIMPS / Curtis Cooper y Steven Boone
45 37.156.667 202254406…308220927 11.185.272 06-09-2008 GIMPS / Hans-Michael Elvenich
46 42.643.801 169873516…562314751 12.837.064 12-04-2009 GIMPS / Odd M. Strindmo
47 43.112.609 316470269…697152511 12.978.189 23-08-2008 GIMPS / Edson Smith
48 57.885.161 581887266…724285951 17.425.170 25-01-2013 GIMPS / Curtis Cooper

No se conoce si existen más números primos de Mersenne entre el 43º (M30.402.457) y el 48º (M57.885.161) por lo tanto, esta tabla es provisional. Por poner un ejemplo histórico, el 29º número primo de Mersenne fue descubierto después del 30º y el 31º.

Propiedades[editar]

Si n es compuesto, entonces Mn es compuesto.

Demostración
Si n es un número natural, por el teorema binomial se tiene:

c^n-d^n=(c-d)\sum_{k=0}^{n-1} c^kd^{n-1-k},

Tomando c=2, d=1 y n=ab (a, b > 1), se tiene:

M_{n}=M_{ab}=2^{ab}-1=(2^{a})^{b}-1^{b}=(2^a-1)\sum_{k=0}^{b-1} (2^{a})^k1^{b-1-k}=(2^a-1)\cdot \left(1+2^a+2^{2a}+2^{3a}+\dots+2^{(b-1)a}\right)

2^a-1 es mayor que 1 porque se ha procurado que a es estrictamente mayor que 1, y la suma 1+2^a+2^{2a}+2^{3a}+\dots+2^{(b-1)a} también lo es. Por tanto, se tiene una factorización de M_{n}, así que M_{n} es compuesto.

Observación: Por contraposición, si Mn es primo, entonces n es primo. Esto facilita la búsqueda de nuevos números primos de Mersenne Mn, ya que sólo hay que comprobar la primalidad de aquellos para los que n es primo.

Si p es un número primo distinto de 2, cualquier primo q que divida a 2p-1 debe ser uno más que un múltiplo de 2p.
Esta proposición también se cumple si 2^p-1 es primo.

  • Ejemplo I: 2^5-1=31 es primo, siendo:
31 = 6 · 5 + 1
  • Ejemplo II: 2^{11}-1=2047=23\cdot 89, siendo:
23 = 2 · 11 + 1
89 = 8 · 11 + 1
2047 = 186 · 11 + 1

Demostración

Si q es un primo que divide 2^p-1, entonces 2^p ≡ 1 (mod q). Por el Pequeño Teorema de Fermat, 2^{q-1} ≡ 1 (mod q). Supongamos que p que no divide a q − 1 para llegar a contradicción. Entonces, como p y q − 1 deben ser primos entre sí, una nueva aplicación del Pequeño Teorema de Fermat muestra que (q-1)^{p-1} ≡ 1 (mod p). Por tanto, existe un número x(q-1)^{p-2} tal que (q − 1)·x ≡ 1 (mod p), y por tanto un número k tal que (q − 1)·x − 1 = kp.

Como 2^{q-1} ≡ 1 (mod q), al elevar ambos lados de la congruencia a la potencia x resulta 2^{(q-1)x} ≡ 1, y como 2^{p} ≡ 1 (mod q), al elevar ambos lados de esta segunda congruencia a la potencia k resulta 2^{pk} ≡ 1. Por tanto, 1≡ \frac{2^{(q-1)x}}{2^{pk}}2^{(q-1)x-pk} (mod q). Pero teniamos que (q − 1)xkp = 1, lo que implica que 2^{1} ≡ 1 (mod q); en otras palabras, que q divide 1. Con esto, la premisa inicial de que p no divide q − 1 es insostenible.

Por lo tanto, q=n\cdot p+1. Pero, además, este n tiene que ser par, porque 2^p-1 es impar y todos sus divisores deben ser también impares. Com p era un primo impar, la única manera que esto ocurra es que n=2k y, finalmente, q=2kp+1.

Si p es un número primo distinto de 2, cualquier primo q que divida 2^p-1 es congruente con \pm 1 \pmod 8.

Demostración

2^{p+1} = 2 \pmod q, así que 2^{(p+1)/2} es una raíz cuadrada de 2 módulo q.
Por reciprocidad cuadrática, cualquier módulo primo del cual 2 tenga raíz cuadrada es congruente con \pm 1 \pmod 8.

Preguntas abiertas[editar]

Desmentida la conjetura original de Mersenne (que establecía una lista de números primos de Mersenne menores o iguales que M257 y afirmaba que no existían más que esos), han surgido otras preguntas abiertas relacionadas con la caracterización de estos números. En particular, la conjetura de Bateman, Selfridge and Wagstaff (1989) también recibe el nombre de "Nueva conjetura de Mersenne".

Nueva conjetura de Mersenne[editar]

La Nueva conjetura de Mersenne o Conjetura de Bateman, Selfridge y Wagstaff (Bateman et al. 1989) establece que para cada número natural impar p, si se cumplen dos de las siguientes condiciones, también se cumple la tercera:

  1. p = 2k ± 1 o p = 4k ± 3 para algún número natural k.
  2. 2p − 1 es primo (un número primo de Mersenne).
  3. (2p + 1) / 3 es primo (un número primo de Wagstaff).

Si p es un número compuesto impar, entonces tanto 2p − 1 como (2p + 1)/3 son compuestos. Por tanto, sólo es necesario examinar números primos para verificar esta conjetura.

Se puede pensar que la nueva conjetura de Mersenne es un intento de rescatar la centenaria conjetura original de Mersenne, que se demostró falsa. Sin embargo, según Robert D. Silverman, John Selfridge declaró que la NCM es "obviamente cierta" ya que fue elegida con el fin de encajar en los datos conocidos y los contraejemplos más allá de esos casos son progresivamente más improbables. Se puede considerar más como una observación que como una pregunta abierta en busca de respuesta. Su página web contiene la verificación de los resultados obtenidos hasta este número.

Conjetura de Lenstra–Pomerance–Wagstaff[editar]

Lenstra, Pomerance y Wagstaff han conjeturado que no sólo existe un número infinito de primos de Mersenne, sino que el número de primos de Mersenne con exponente p menor que x se puede aproximar asintóticamente por

e^\gamma\cdot\log_2(x),

donde γ es la constante de Euler-Mascheroni y e^\gamma = 1,781072417990197\dots

Relación con otras categorías de números[editar]

Números perfectos[editar]

Euclides, muchos siglos antes que Mersenne, ya conocía estos números y encontró una fuerte relación entre ellos y los números perfectos. Si M es un número primo de Mersenne, entonces M·(M+1)/2 es un número perfecto. Asimismo, Euler demostró en el siglo XVIII que todos los números perfectos pares son de la forma M·(M+1)/2. No se conocen en la actualidad números perfectos impares, y se sospecha que no existe ninguno.

Números dobles de Mersenne[editar]

Un número doble de Mersenne se define como:

M_{M_p} = 2^{2^p-1}-1

donde p es el exponente de un número primo de Mersenne.

Números repunit[editar]

Los números repunit (del inglés repeated unit, "unidad repetida") son los que, en una base dada, se representan como una cadena de unos. Los números de Mersenne son los números repunit en el sistema binario.

Véase también[editar]

Referencias[editar]

Enlaces externos[editar]