En matemáticas y más precisamente en aritmética , un número de Mersenne es un número de la forma 2 n - 1 (donde n es un no-cero natural de número ), un Mersenne primer número (a veces Mersenne primer número ), por lo tanto es un número primero de esta forma. Estos números son el nombre de erudito religioso y matemático francés del XVII ° siglo Marin Mersenne , pero hace casi 2.000 años, Euclides ya se utilizan para el estudionúmeros perfectos .
Si un número de Mersenne 2 n - 1 es primo, necesariamente n es primo, pero esta condición no es suficiente: 2, 3, 5, 7 y 11 son primos, los números de Mersenne 2 2 - 1 = 3 , 2 3 - 1 = 7 , 2 5 - 1 = 31 y 2 7 - 1 = 127 son de hecho primos, pero el número de Mersenne 2 11 - 1 = 2047 = 23 × 89 no lo es.
Existe una prueba de primalidad eficiente para los números de Mersenne, la prueba de primalidad de Lucas-Lehmer , que hace que los números primos más grandes conocidos sean números de Mersenne. Sin embargo, los números primos de Mersenne son raros: 51 se conocen a principios de 2020. Su investigación es el tema de un proyecto de computación colaborativa, el proyecto GIMPS . No sabemos si existe una infinidad de números primos de Mersenne.
Los números primos de Mersenne están relacionados con números perfectos , que son números "iguales a la suma de sus divisores propios ". Es esta conexión la que ha motivado históricamente el estudio de los números primos de Mersenne. Desde el IV º siglo aC. BC , Euclides demostró que si M = 2 p - 1 es un número primo, entonces M ( M + 1) / 2 = 2 p –1 (2 p - 1) es un número perfecto. Dos mil años más tarde, en el XVIII ° siglo , Euler demostró que todos los números perfectos pares tienen esta forma. No se conoce ningún número perfecto impar.
El n- ésimo número de Mersenne 2 n -1 a veces se denota por M n = 2 n -1 ( n ∈ ℕ * ). No todos los números de Mersenne son primos, por ejemplo, M 4 = 2 4 - 1 = 15 = 3 × 5 . De hecho, tan pronto como se compone n = kl, se compone M n = 2 kl - 1 , porque 2 k - 1 , que es estrictamente mayor que 1 si k es estrictamente mayor que 1, es un divisor de 2 kl - 1 .
Por lo tanto, un número de Mersenne M n = 2 n -1 puede ser primo solo si n es primo.
Lo contrario es falso: incluso si n es primo, el número de Mersenne M n puede no ser primo. El contraejemplo más pequeño es M 11 = 2047 = 23 × 89 .
Los números de Mersenne tienen las siguientes propiedades
P: M p es primo -: M p no es primo Cyan: Mersenne lo había previsto Rose: había previsto lo contrario | ||||||||
pag | 2 | 3 | 5 | 7 | 11 | 13 | 17 | 19 |
M p | PAG | PAG | PAG | PAG | - | PAG | PAG | PAG |
pag | 23 | 29 | 31 | 37 | 41 | 43 | 47 | 53 |
M p | - | - | PAG | - | - | - | - | - |
pag | 59 | 61 | 67 | 71 | 73 | 79 | 83 | 89 |
M p | - | PAG | - | - | - | - | - | PAG |
pag | 97 | 101 | 103 | 107 | 109 | 113 | 127 | 131 |
M p | - | - | - | PAG | - | - | PAG | - |
pag | 137 | 139 | 149 | 151 | 157 | 163 | 167 | 173 |
M p | - | - | - | - | - | - | - | - |
pag | 179 | 181 | 191 | 193 | 197 | 199 | 211 | 223 |
M p | - | - | - | - | - | - | - | - |
pag | 227 | 229 | 233 | 239 | 241 | 251 | 257 | 263 |
M p | - | - | - | - | - | - | - | - |
Si M n es primo, entonces n también. Marin Mersenne , un monje de la orden de los Mínimos a principios del XVII ° siglo , es el autor de la propuesta que se demuestre lo contrario . También proporciona una lista de números primos de "Mersenne" hasta el exponente 257, que resultará ser falso: incluyó erróneamente 67 y 257, y omitió 61, 89 y 107.
Lo contrario es falso: M p puede ser compuesto mientras que p es primo; el contraejemplo más pequeño es M 11 = 2047 = 23 × 89: 11 es primo pero M 11 no lo es, como lo recuerda nuevamente en 1732 Euler , quien menciona, que también es el caso para p = 23, 83, 131, 179, 191 y 239.
Para que M n sea primo, n debe ser primo, lo que ya simplifica la búsqueda de números primos de Mersenne. Para probar si un número de Mersenne M p (con p primo) es primo, existe un método comparativamente muy rápido, desarrollado originalmente por Édouard Lucas en 1878 y mejorado por Derrick Lehmer en la década de 1930 . Es gracias a esta prueba excepcionalmente simple en comparación con el tamaño de los números considerados que durante mucho tiempo los números primos más grandes conocidos han sido los números primos de Mersenne.
Los primeros cuatro números primos de Mersenne se conocían desde la antigüedad. El quinto (2 13 - 1) fue descubierto antes de 1461 por una persona desconocida. Los dos siguientes fueron encontrados por Pietro Cataldi en 1588 . Más de un siglo después, en 1750 , Euler encontró uno más. El siguiente en orden cronológico (pero no numérico) fue encontrado por Lucas en 1876 , luego uno por Ivan Pervushin en 1883 . Otros dos fueron encontrados a principios del XX ° siglo por RE Powers (en) en 1911 y 1914 .
La investigación de Mersenne sobre los números primos se vio revolucionada por la introducción de las computadoras electrónicas. La primera identificación de un número Mersenne por este medio tuvo lugar a las 22:00 horas del30 de enero de 1952por una computadora SWAC en el Instituto de Análisis Numérico del campus de la Universidad de California en Los Ángeles , bajo la dirección de Derrick Lehmer, con un programa escrito por Raphael Robinson .
Fue el primer número primo de Mersenne identificado en 38 años. El siguiente fue encontrado menos de dos horas después por la misma computadora, que encontró tres más en los meses siguientes.
En diciembre de 2018 , se conocían 51 números primos de Mersenne, siendo el más grande M 82589933 , que también es en la misma fecha el número primo más grande conocido. Como muchos de sus predecesores, fue descubierto por un cálculo distribuido bajo la égida del proyecto GIMPS , Great Internet Mersenne Prime Search (que significa "gran búsqueda en Internet de números primos de Mersenne").
No sabemos si el conjunto de números primos de Mersenne es finito o infinito (pero conjeturamos que es infinito). En diciembre de 2018 , se conocían 51 números primos de Mersenne (series A000043 ( p ) y A000668 ( M p )).
Históricamente, no siempre se han descubierto en orden ascendente (ejemplos: el 12, M 127 , el 29 M 4423 ...).
rango | pag | M p | M p valor en base diez | Número de dígitos en base diez |
Fecha de descubrimiento | Descubridor (s) |
---|---|---|---|---|---|---|
1 | 2 | M 2 | 3 | 1 | antigüedad | notado (como un número primo) por los matemáticos griegos |
2 | 3 | M 3 | 7 | 1 | ||
3 | 5 | M 5 | 31 | 2 | ||
4 | 7 | M 7 | 127 | 3 | ||
5 | 13 | M 13 | 8.191 | 4 | Edad Media ( XIII ° siglo ) | Ibn Fallus (1194-1239) |
6 | 17 | M 17 | 131,071 | 6 | 1588 | Cataldi |
7 | 19 | M 19 | 524,287 | 6 | 1588 | Cataldi |
8 | 31 | M 31 | 2,147,483,647 | 10 | 1750 | Euler |
9 | 61 | M 61 | 2305843009 213693951 | 19 | 1883 | Pervushin |
10 | 89 | M 89 | 618970019… 449562111 | 27 | 1911 | Poderes (en) |
11 | 107 | M 107 | 162259276… 010288127 | 33 | 1914 | Potestades |
12 | 127 | M 127 | 170141183… 884105727 | 39 | 1876 | Lucas |
13 | 521 | M 521 | 686479766… 115057151 | 157 | 30 de enero de 1952 | Robinson ( SWAC ) |
14 | 607 | M 607 | 531137992… 031728127 | 183 | 30 de enero de 1952 | Robinson (SWAC) |
15 | 1,279 | M 1279 | 104079321… 168729087 | 386 | 25 de junio de 1952 | Robinson (SWAC) |
dieciséis | 2.203 | M 2203 | 147597991… 697771007 | 664 | 7 de octubre de 1952 | Robinson (SWAC) |
17 | 2 281 | M 2281 | 446087557… 132836351 | 687 | 9 de octubre de 1952 | Robinson (SWAC) |
18 | 3 217 | M 3217 | 259117086… 909315071 | 969 | 8 de septiembre de 1957 | Riesel ( BESK (en) ) |
19 | 4.253 | M 4253 | 190797007… 350484991 | 1,281 | 3 de noviembre de 1961 | Hurwitz ( IBM ) |
20 | 4.423 | M 4423 | 285542542… 608580607 | 1332 | 3 de noviembre de 1961 | Hurwitz (IBM) |
21 | 9 689 | M 9689 | 478220278… 225754111 | 2 917 | 11 de mayo de 1963 | Gillies (en) ( ILLIAC II) |
22 | 9 941 | M 9941 | 346088282… 789463551 | 2 993 | 16 de mayo de 1963 | Gillies (ILLIAC II) |
23 | 11,213 | M 11213 | 281411201… 696392191 | 3 376 | 2 de junio de 1963 | Gillies (ILLIAC II) |
24 | 19 937 | M 19937 | 431542479… 968041471 | 6,002 | 4 de marzo de 1971 | Tuckerman (en) (IBM) |
25 | 21,701 | M 21701 | 448679166… 511882751 | 6 533 | 30 de octubre de 1978 | Noll (en) y Nickel ( CDC ) |
26 | 23,209 | M 23209 | 402874115… 779264511 | 6,987 | 9 de febrero de 1979 | Noll (CDC) |
27 | 44,497 | M 44497 | 854509824… 011228671 | 13,395 | 8 de abril de 1979 |
Nelson (en) y Slowinski (en) ( Cray Research ) |
28 | 86,243 | M 86243 | 536927995… 433438207 | 25 962 | 25 de septiembre de 1982 | Slowinski (Cray) |
29 | 110,503 | M 110503 | 521928313… 465515007 | 33 265 | 28 de enero de 1988 | Colquitt y Welsh ( NEC ) |
30 | 132,049 | M 132049 | 512740276… 730061311 | 39,751 | 19 de septiembre de 1983 | Slowinski (Cray) |
31 | 216,091 | M 216091 | 746093103… 815528447 | 65,050 | 1 st de septiembre de 1,985 | Slowinski (Cray) |
32 | 756,839 | M 756839 | 174135906… 544677887 | 227 832 | 19 de febrero de 1992 | Slowinski y Gage |
33 | 859 433 | M 859433 | 129498125… 500142591 | 258,716 | 10 de enero de 1994 | Slowinski y Gage |
34 | 1,257,787 | M 1257787 | 412245773… 089366527 | 378,632 | 3 de septiembre de 1996 | Slowinski y Gage |
35 | 1,398,269 | M 1398269 | 814717564… 451315711 | 420 921 | 13 de noviembre de 1996 | GIMPS / Joel Armengaud |
36 | 2976 221 | M 2976221 | 623340076… 729201151 | 895 932 | 24 de agosto de 1997 | GIMPS / Gordon Spence |
37 | 3,021,377 | M 3021377 | 127411683… 024694271 | 909,526 | 27 de enero de 1998 | GIMPS / Roland Clarkson |
38 | 6,972,593 | M 6972593 | 437075744… 924193791 | 2,098,960 | 1 st 06 1999 | GIMPS / Nayan Hajratwala |
39 | 13,466,917 | M 13466917 | 924947738… 256259071 | 4.053.946 | 14 de noviembre de 2001 | GIMPS / Michael Cameron |
40 | 20.996.011 | M 20996011 | 125976895… 855682047 | 6320 430 | 17 de noviembre de 2003 | GIMPS / Michael Shafer |
41 | 24,036,583 | M 24036583 | 299410429… 733969407 | 7 235 733 | 15 de mayo de 2004 | GIMPS / Josh Findley |
42 | 25 964 951 | M 25964951 | 122164630… 577077247 | 7 816 230 | 18 de febrero de 2005 | GIMPS / Martin Nowak |
43 | 30 402 457 | M 30402457 | 315416475… 652943871 | 9.152.052 | 15 de diciembre de 2005 | GIMPS / Cooper y Boone |
44 | 32,582,657 | M 32582657 | 124575026… 053967871 | 9.808.358 | 4 de septiembre de 2006 | GIMPS / Cooper y Boone |
45 | 37 156 667 | M 37156667 | 202254405… 308220927 | 11 185 272 | 6 de septiembre de 2008 | GIMPS / Elvenich |
46 | 42 643 801 | M 42643801 | 169873516… 562314751 | 12 837 064 | 12 de abril de 2009 | GIMPS / Odd Magnar Strindmo |
47 | 43 112 609 | M 43112609 | 316470269… 697152511 | 12 978 189 | 23 de agosto de 2008 | GIMPS / Smith |
48? | 57 885 161 | M 57885161 | 581887266… 724285951 | 17 425 170 | 25 de enero 2013 | GIMPS / Cooper |
49? | 74 207 281 | M 74207281 | 300376418… 086436351 | 22 338 618 | 7 de enero de 2016 | GIMPS / Cooper |
50? | 77 232 917 | M 77232917 | 467333183 ... 762179071 | 23 249 425 | 3 de enero de 2018 | GIMPS / Jonathan Pace |
51? | 82,589,933 | M 82589933 | 148894445 ... 217902591 | 24 862048 | 7 de diciembre de 2018 | GIMPS / Patrick Laroche |
El nuevo más pequeño no Mersenne primos, pero los primeros indicios (de ajuste entre el 1 st y 9 th número de números primos de Mersenne, conocido al final del XIX XX siglo ) son:
N O | pag | M p | M p valor en base diez |
Número de dígitos en base diez |
Descomposición |
---|---|---|---|---|---|
1 | 11 | M 11 | 2.047 | 4 | 23 × 89 |
2 | 23 | M 23 | 8 388 607 | 7 | 47 × 178 481 |
3 | 29 | M 29 | 536 870 911 | 9 | 233 × 1.103 × 2.089 |
4 | 37 | M 37 | 137 438 953 471 | 12 | 223 × 616 318 177 |
5 | 41 | M 41 | 2199 023 255 551 | 13 | 13 367 × 164511 353 |
6 | 43 | M 43 | 8796093022 207 | 13 | 431 × 9,719 × 2,099,863 |
7 | 47 | M 47 | 140 737 488 355 327 | 15 | 2,351 × 4,513 × 13,264,529 |
8 | 53 | M 53 | 9007 199 254 740 991 | dieciséis | 6.361 × 69.431 × 20.394.401 |
9 | 59 | M 59 | 576460752303423487 | 18 | 179 951 × 3 203 431 780 337 |
El número M 67 , igual a 147 573 952 589 676 412 927 , apareció en la lista original de Mersenne; sin embargo, Lucas demostró en 1876 que este número no era primo, sin poder sin embargo exhibir sus factores. La factorización de este número (193,707,721 x 761,838,257,287) fue determinada por Frank Nelson Cole en 1903.
Los números de Mersenne (primos o no) son las respuestas en la base 2. La secuencia de respuestas en la base b es la secuencia de Lucas U ( b + 1, b ). Ahora cualquier secuencia de Lucas U ( P , Q ) con P y Q primos entre ellos tiene una fuerte divisibilidad . Por el mismo razonamiento que para la secuencia de números de Mersenne ( ver arriba ), una condición necesaria (pero no suficiente) para que el término n -ésimo de tal secuencia sea primo es, por lo tanto, que n también sea primo .
Los números primos de Solinas son números primos de la forma p = f (2 k ) donde f es un polinomio unitario con coeficientes enteros de bajo "peso de reducción modular" (una condición técnica destinada a que el módulo de reducción p sea rápido y que, por simplicidad, a veces se reemplaza por: los coeficientes distintos de cero de f son pocos e iguales ± 1). Solinas da una serie de ejemplos, el primero de los cuales es f ( t ) = t - 1, de "peso" 1 (que corresponde a los números de Mersenne) y el último es f ( t ) = t 4 - t 3 + t 2 + 1, de “peso” 4, pero que también incluye f ( t ) = t d - t d –1 + t d –2 -… + (–1) d , de “peso” 3.
Dado que los números de Mersenne son las repeticiones en base 2, su escritura binaria no incluye ningún 0. De manera similar, podemos estudiar en las bases superiores los números primos cuya escritura no tiene un dígito determinado. En 2019 se comprobó que existe una infinidad de números primos cuya expansión en base 10 no incluye ninguno de los dígitos del 0 al 9.
donde él