In matematica e più precisamente in aritmetica , un numero di Mersenne è un numero di forma 2 n - 1 (dove n è un non-nullo naturale numero ), un primo di Mersenne numero (talvolta Mersenne numero ), è quindi un primo numero di questa forma. Questi numeri sono chiamati dopo studioso di religione e matematico francese del XVII ° secolo Marin Mersenne , ma quasi 2.000 anni fa, Euclide già utilizzati per studiarenumeri perfetti .
Se un numero di Mersenne 2 n - 1 è primo, necessariamente n è primo, ma questa condizione non è sufficiente: 2, 3, 5, 7 e 11 sono primi, i numeri di Mersenne 2 2 - 1 = 3 , 2 3 - 1 = 7 , 2 5 - 1 = 31 e 2 7 - 1 = 127 sono effettivamente primi, ma il numero di Mersenne 2 11 - 1 = 2047 = 23 × 89 non lo è.
Esiste un efficiente test di primalità per i numeri di Mersenne, il test di primalità di Lucas-Lehmer , che rende i più grandi numeri primi conosciuti numeri di Mersenne. I numeri primi di Mersenne sono però rari: 51 sono noti all'inizio del 2020. La loro ricerca è oggetto di un progetto di calcolo collaborativo, il progetto GIMPS . Non sappiamo se esiste un'infinità di numeri primi di Mersenne.
I numeri primi di Mersenne sono legati ai numeri perfetti , che sono numeri "uguali alla somma dei loro divisori propri ". È questa connessione che ha storicamente motivato lo studio dei numeri primi di Mersenne. Dal IV ° secolo aC. BC , Euclide dimostrò che se M = 2 p - 1 è un numero primo, allora M ( M + 1) / 2 = 2 p –1 (2 p - 1) è un numero perfetto. Due millenni dopo, nel XVIII ° secolo , Eulero dimostrato che tutti i numeri perfetti coetanei hanno questa forma. Non si conosce un numero perfetto dispari.
La n- esimo Mersenne numero 2 n -1 è talvolta indicato con M n = 2 n -1 ( n ∈ ℕ * ). Non tutti i numeri di Mersenne sono primi, ad esempio M 4 = 2 4 - 1 = 15 = 3 × 5 . Infatti appena n = kl si compone, si compone M n = 2 kl - 1 , perché 2 k - 1 , che è strettamente maggiore di 1 se k è strettamente maggiore di 1, è un divisore di 2 kl - 1 .
Un numero di Mersenne M n = 2 n -1 può quindi essere primo solo se n è primo.
Il contrario è falso: anche se n è primo, il numero di Mersenne M n può non essere primo. Il controesempio più piccolo è M 11 = 2047 = 23 × 89 .
I numeri di Mersenne hanno le seguenti proprietà
P: M p è primo -: M p non è primo Ciano: Mersenne lo aveva previsto Rose: aveva previsto il contrario | ||||||||
p | 2 | 3 | 5 | 7 | 11 | 13 | 17 | 19 |
M p | P | P | P | P | - | P | P | P |
p | 23 | 29 | 31 | 37 | 41 | 43 | 47 | 53 |
M p | - | - | P | - | - | - | - | - |
p | 59 | 61 | 67 | 71 | 73 | 79 | 83 | 89 |
M p | - | P | - | - | - | - | - | P |
p | 97 | 101 | 103 | 107 | 109 | 113 | 127 | 131 |
M p | - | - | - | P | - | - | P | - |
p | 137 | 139 | 149 | 151 | 157 | 163 | 167 | 173 |
M p | - | - | - | - | - | - | - | - |
p | 179 | 181 | 191 | 193 | 197 | 199 | 211 | 223 |
M p | - | - | - | - | - | - | - | - |
p | 227 | 229 | 233 | 239 | 241 | 251 | 257 | 263 |
M p | - | - | - | - | - | - | - | - |
Se M n è primo, allora anche n . Marin Mersenne , un monaco del ordine del Minimes nei primi anni del XVII ° secolo , è l'autore della proposta che altrimenti dimostrato . Fornisce anche un elenco di numeri primi "Mersenne" fino all'esponente 257, che si rivelerà falso: includeva erroneamente 67 e 257 e ometteva 61, 89 e 107.
Il contrario è falso: M p può essere composto mentre p è primo; il più piccolo controesempio è M 11 = 2047 = 23 × 89: 11 è primo ma M 11 non lo è, come ricordato ancora nel 1732 da Eulero , che cita, che è anche il caso di p = 23, 83, 131, 179, 191 e 239.
Perché M n sia primo, n deve essere primo, il che già semplifica la ricerca dei numeri primi di Mersenne. Per verificare se un numero di Mersenne M p (con p primo) è primo, esiste un metodo relativamente molto veloce, originariamente sviluppato da Édouard Lucas nel 1878 e migliorato da Derrick Lehmer negli anni '30 . È grazie a questo test eccezionalmente semplice rispetto alla dimensione dei numeri considerati che per lungo tempo i più grandi numeri primi conosciuti sono stati i numeri primi di Mersenne.
I primi quattro numeri primi di Mersenne erano conosciuti dall'Antichità. Il quinto (2 13 - 1) fu scoperto prima del 1461 da uno sconosciuto. I due successivi furono ritrovati da Pietro Cataldi nel 1588 . Più di un secolo dopo, nel 1750 , Eulero ne trovò un altro. Il successivo in ordine cronologico (ma non numerico) fu trovato da Lucas nel 1876 , poi uno da Ivan Pervushin nel 1883 . Altri due sono stati trovati all'inizio del XX ° secolo da RE Powers (in) nel 1911 e 1914 .
La ricerca di Mersenne sui numeri primi fu rivoluzionata dall'introduzione dei computer elettronici. La prima identificazione di un numero di Mersenne con questo mezzo è avvenuta alle 22:00 in poi30 gennaio 1952da un computer SWAC presso l'Institute for Numerical Analysis presso il campus dell'Università della California a Los Angeles , sotto la direzione di Derrick Lehmer, con un programma scritto da Raphael Robinson .
È stato il primo numero primo di Mersenne identificato dopo 38 anni. Il successivo è stato trovato meno di due ore dopo dallo stesso computer, che ne ha trovati altri tre nei mesi successivi.
Nel dicembre 2018 erano noti 51 numeri primi di Mersenne, il più grande dei quali è M 82 589 933 , che alla stessa data è anche il più grande numero primo conosciuto. Come molti dei suoi predecessori, è stato scoperto da un calcolo distribuito sotto l'egida del progetto GIMPS , Great Internet Mersenne Prime Search (che significa "ampia ricerca su Internet di numeri primi di Mersenne").
Non sappiamo se l'insieme dei numeri primi di Mersenne sia finito o infinito (ma supponiamo che sia infinito). A dicembre 2018 erano noti 51 numeri primi di Mersenne (serie A000043 ( p ) e A000668 ( M p )).
Storicamente, non sono sempre stati scoperti in ordine crescente (esempi: il 12°, M 127 , il 29° M 4423 ...).
rango | p | M p | Valore M p in base dieci | Numero di cifre in base dieci |
Data di scoperta | Scopritore/i |
---|---|---|---|---|---|---|
1 | 2 | M 2 | 3 | 1 | antichità | notato (come numero primo) dai matematici greci |
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 | Medioevo ( XIII ° secolo ) | Ibn Fallo (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 | Eulero |
9 | 61 | M 61 | 2 305 843 009 213 693 951 | 19 | 1883 | pervushin |
10 | 89 | M 89 | 618970019… 449562111 | 27 | 1911 | Poteri (it) |
11 | 107 | M 107 | 162259276… 010288127 | 33 | 1914 | poteri |
12 | 127 | M 127 | 170141183… 884105727 | 39 | 1876 | Lucas |
13 | 521 | M 521 | 686479766… 115057151 | 157 | 30 gennaio 1952 | Robinson ( SWAC ) |
14 | 607 | M 607 | 531137992… 031728127 | 183 | 30 gennaio 1952 | Robinson (SWAC) |
15 | 1.279 | M 1279 | 104079321… 168729087 | 386 | 25 giugno 1952 | Robinson (SWAC) |
16 | 2.203 | M 2203 | 147597991… 697771007 | 664 | 7 ottobre 1952 | Robinson (SWAC) |
17 | 2 281 | M 2281 | 446087557… 132836351 | 687 | 9 ottobre 1952 | Robinson (SWAC) |
18 | 3 217 | M 3217 | 259117086… 909315071 | 969 | 8 settembre 1957 | Riesel ( BESK (it) ) |
19 | 4.253 | M 4253 | 190797007… 350484991 | 1.281 | 3 novembre 1961 | Hurwitz ( IBM ) |
20 | 4.423 | M 4423 | 285542542… 608580607 | 1332 | 3 novembre 1961 | Hurwitz (IBM) |
21 | 9 689 | M 9689 | 478220278… 225754111 | 2 917 | 11 maggio 1963 | Gillies (it) ( ILLIAC II) |
22 | 9 941 | M 9941 | 346088282… 789463551 | 2 993 | 16 maggio 1963 | Gillies (ILLIAC II) |
23 | 11,213 | M 11213 | 281411201… 696392191 | 3 376 | 2 giugno 1963 | Gillies (ILLIAC II) |
24 | 19 937 | M 19937 | 431542479… 968041471 | 6.002 | 4 marzo 1971 | Tuckerman (a) (IBM) |
25 | 21,701 | M 21701 | 448679166… 511882751 | 6 533 | 30 ottobre 1978 | Noll (it) e Nickel ( CDC ) |
26 | 23.209 | M 23209 | 402874115… 779264511 | 6.987 | 9 febbraio 1979 | Noll (CDC) |
27 | 44.497 | M 44497 | 854509824… 011228671 | 13.395 | 8 aprile 1979 |
Nelson (it) e Slowinski (it) ( Cray Research ) |
28 | 86.243 | M 86243 | 536927995… 433438207 | 25 962 | 25 settembre 1982 | Slowinski (Cray) |
29 | 110.503 | M 110503 | 521928313… 465515007 | 33 265 | 28 gennaio 1988 | Colquitt e gallese ( NEC ) |
30 | 132.049 | M 132049 | 512740276… 730061311 | 39.751 | 19 settembre 1983 | Slowinski (Cray) |
31 | 216.091 | M 216091 | 746093103… 815528447 | 65.050 | 1 ° settembre 1985 | Slowinski (Cray) |
32 | 756.839 | M 756839 | 174135906… 544677887 | 227 832 | 19 febbraio 1992 | Slowinski e Gage |
33 | 859 433 | M 859433 | 129498125… 500142591 | 258.716 | 10 gennaio 1994 | Slowinski e Gage |
34 | 1.257.787 | M 1257787 | 412245773… 089366527 | 378.632 | 3 settembre 1996 | Slowinski e Gage |
35 | 1.398.269 | M 1398269 | 814717564… 451315711 | 420 921 | 13 novembre 1996 | GIMPS / Joel Armengaud |
36 | 2 976 221 | M 2976221 | 623340076… 729201151 | 895 932 | 24 agosto 1997 | GIMPS / Gordon Spence |
37 | 3.021.377 | M 3021377 | 127411683… 024694271 | 909,526 | 27 gennaio 1998 | GIMPS / Roland Clarkson |
38 | 6.972.593 | M 6972593 | 437075744… 924193791 | 2.098.960 | 1 ° giugno 1999 | GIMPS / Nayan Hajratwala |
39 | 13.466.917 | M 13466917 | 924947738… 256259071 | 4.053.946 | 14 novembre 2001 | GIMPS / Michael Cameron |
40 | 20.996.011 | M 20996011 | 125976895… 855682047 | 6 320 430 | 17 novembre 2003 | GIMPS / Michael Shafer |
41 | 24.036.583 | M 24036583 | 299410429… 733969407 | 7 235 733 | 15 maggio 2004 | GIMPS / Josh Findley |
42 | 25 964 951 | M 25964951 | 122164630… 577077247 | 7 816 230 | 18 febbraio 2005 | GIMPS / Martin Nowak |
43 | 30 402 457 | M 30402457 | 315416475… 652943871 | 9.152.052 | 15 dicembre 2005 | GIMPS / Cooper e Boone |
44 | 32.582.657 | M 32582657 | 124575026… 053967871 | 9.808.358 | 4 settembre 2006 | GIMPS / Cooper e Boone |
45 | 37 156 667 | M 37156667 | 202254405… 308220927 | 11 185 272 | 6 settembre 2008 | GIMPS / Elvenich |
46 | 42 643 801 | M 42643801 | 169873516… 562314751 | 12 837 064 | 12 aprile 2009 | GIMPS / Strano Magnar Strindmo |
47 | 43 112 609 | M 43112609 | 316470269… 697152511 | 12 978 189 | 23 agosto 2008 | GIMPS / Smith |
48? | 57 885 161 | M 57885161 | 581887266… 724285951 | 17 425 170 | 25 gennaio 2013 | GIMPS / Cooper |
49? | 74 207 281 | M 74207281 | 300376418… 086436351 | 22 338 618 | 7 gennaio 2016 | GIMPS / Cooper |
50? | 77 232 917 | M 77232917 | 467333183 ... 762179071 | 23 249 425 | 3 gennaio 2018 | GIMPS / Jonathan Pace |
51? | 82.589.933 | M 82589933 | 148894445 ... 217902591 | 24 862 048 | 7 dicembre 2018 | GIMPS / Patrick Laroche |
Il nuovo piccolo non Mersenne numeri primi ma le prime indicazioni (dal fit tra il 1 ° e il 9 th numero di numeri primi di Mersenne, conosciuto alla fine del XIX ° secolo ) sono:
N o | p | M p | Valore M p in base dieci |
Numero di cifre in base dieci |
Decomposizione |
---|---|---|---|---|---|
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 | 2 199 023 255 551 | 13 | 13 367 × 164 511 353 |
6 | 43 | M 43 | 8 796 093 022 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 | 9 007 199 254 740 991 | 16 | 6.361 × 69.431 × 20.394.401 |
9 | 59 | M 59 | 576 460 752 303 423 487 | 18 | 179 951 × 3 203 431 780 337 |
Il numero M 67 , pari a 147 573 952 589 676 412 927 , compariva nell'elenco originario di Mersenne; tuttavia, Lucas dimostrò nel 1876 che questo numero non era primo, senza tuttavia poterne esibire i fattori. La fattorizzazione di questo numero (193.707.721 x 761.838.257.287) fu determinata da Frank Nelson Cole nel 1903.
I numeri di Mersenne (primi o meno) sono le risposte in base 2. La sequenza delle risposte in base b è la sequenza di Lucas U ( b + 1, b ). Ora, qualsiasi successione di Lucas U ( P , Q ) con P e Q primi tra di loro ha una forte divisibilità . Per lo stesso ragionamento della sequenza dei numeri di Mersenne ( vedi sopra ), una condizione necessaria (ma non sufficiente) perché l' n -esimo termine di tale sequenza sia primo è quindi che anche n sia primo .
I numeri primi di Solinas sono numeri primi della forma p = f (2 k ) dove f è un polinomio unitario a coefficienti interi di basso "peso di riduzione modulare" (condizione tecnica destinata alla riduzione modulo p veloce e che, per semplicità, è talvolta sostituito da: i coefficienti non nulli di f sono pochi e uguali ± 1). Solinas fornisce una serie di esempi, il primo dei quali è f ( t ) = t - 1, di "peso" 1 (che corrisponde ai numeri di Mersenne) e l'ultimo è f ( t ) = t 4 - t 3 + t 2 + 1, di “peso” 4, ma che comprende anche f ( t ) = t d - t d –1 + t d –2 -… + (–1) d , di “peso” 3.
Poiché i numeri di Mersenne sono le repunit in base 2, la loro scrittura binaria non include alcuno 0. In modo simile, possiamo studiare nelle basi superiori i numeri primi la cui scrittura non ha una certa cifra. Nel 2019 è stato dimostrato che esiste un'infinità di numeri primi la cui espansione in base 10 non include nessuna delle cifre da 0 a 9.
dove lui