Numero primo di Mersenne
# Numero primo di Mersenne

In matematica un numero primo di Mersenne è un numero primo inferiore di uno rispetto ad una potenza di due. È quindi esprimibile come:

    $M_{p}=2^{p}-1,$

con $p$ intero positivo primo. Tale numero $p$ è talvolta indicato come esponente di Mersenne (successione A000043 in OEIS). Si noti che $2^{11}-1=2047=23\cdot 89$ non è primo e che quindi non tutti i numeri primi corrispondono a un esponente di Mersenne, ma solo quelli per cui $M_{p}=2^{p}-1$ risulta anch'esso primo.

A volte nella definizione di numero primo di Mersenne $M_{n}$ non viene richiesto a priori che l'indice $n$ sia primo. L'equivalenza delle due definizioni segue dal fatto che se $M_{n}$ è primo, allora anche $n$ deve essere primo, come si vede facilmente dall'identità

    $2^{ab}-1=(2^{a}-1)\cdot \left(1+2^{a}+2^{2a}+2^{3a}+\cdots +2^{(b-1)a}\right).$

In generale un numero del tipo $M_{n}=2^{n}-1$ viene detto "numero di Mersenne" (anche quando non è un numero primo di Mersenne). Si conoscono diverse proprietà dei fattori primi degli $M_{p}$ composti con $p$ primo. Ad esempio (e Fermat fu il primo ad evidenziare e usare questa proprietà) si può dimostrare che ogni fattore primo di $M_{p}$ dev'essere del tipo $2kp+1$ con $k$ intero positivo.

I numeri primi di Mersenne prendono il nome dal matematico francese Marin Mersenne (1588-1648). Mersenne compilò una lista di numeri primi di questo tipo considerando tutti i valori di $n$ fino a $n=257$. Tale lista conteneva però alcuni errori: includeva $M_{67}$ e $M_{257}$ (che non sono primi), mentre non comparivano $M_{61}$, $M_{89}$ e $M_{107}$ (che sono primi).

I primi dodici numeri primi di Mersenne sono:

    $M_{2}=2^{2}-1=3$
    $M_{3}=2^{3}-1=7$
    $M_{5}=2^{5}-1=31$
    $M_{7}=2^{7}-1=127$
    $M_{13}=2^{13}-1=8191$
    $M_{17}=131071$
    $M_{19}=524287$
    $M_{31}=2147483647$
    $M_{61}=2305843009213693951$
    $M_{89}=618970019642690137449562111$
    $M_{107}=162259276829213363391578010288127$
    $M_{127}=170141183460469231731687303715884105727$

I numeri primi di Mersenne sono collegati con i numeri perfetti. Nel IV secolo a.C. Euclide dimostrò che se $M_{n}$ è un numero primo, allora ${M_{n}\cdot (M_{n}+1) \over 2}=2^{n-1}\cdot (2^{n}-1)$ è un numero perfetto.

Nel XVIII secolo Eulero provò che tutti i numeri perfetti pari hanno questa forma. Nessun numero perfetto dispari è conosciuto, ed è anche possibile che non ne esistano.

L'avvento dei calcolatori elettronici ha notevolmente accelerato la scoperta dei primi di Mersenne. I primi dodici numeri primi di Mersenne sono stati scoperti prima del XX secolo. Alla fine del millennio i primi di Mersenne conosciuti erano 38; oggi invece se ne conoscono 51 e i diciassette più recenti sono stati scoperti nell'ambito della GIMPS, la Great Internet Mersenne Prime Search, iniziativa che sfrutta le risorse disponibili di migliaia di computer in rete per cercare i primi di Mersenne. Il test di primalità usato dal GIMPS è il Test di Lucas-Lehmer che è molto più veloce dei test generici a parità di ordine di grandezza nel numero; ecco perché in assoluto i record dei più grandi numeri primi conosciuti sono ormai da tempo dei numeri primi di Mersenne. Il più grande numero primo conosciuto (al 21 dicembre 2018) è $M_{82589933}$. Ha più di 24 milioni di cifre decimali ed è stato anch'esso trovato nell'ambito GIMPS:

    $M_{82589933}=2^{82589933}-1$

Se scritti in base 2, tutti i numeri primi di Mersenne sono repunit primi, ovvero sono rappresentati da stringhe di p cifre unitarie, dove p è l'esponente primo di Mersenne. Negli esempi qui di seguito l'indice denota la base in cui il numero viene espresso:

    $3_{10}$ = $11_2$
    $7_{10}$ = $111_2$
    $31_{10}$ = $11111_2$
    $127_{10}$ = $1111111_2$
    $8191_{10}$ = $1111111111111_2.$

Si noti che questa proprietà è posseduta quando si sottrae 1 da tutte le potenze di 2 aventi per esponente un numero primo. In sostanza tutti i candidati a essere numeri primi di Mersenne (chiamati come detto sopra semplicemente "numeri di Mersenne") in notazione binaria sono primi repunit.

Si può osservare scorrendo la lista più sotto, che a parte il 3, tutti i numeri primi di Mersenne terminano con 1 o con 7. Questo è dovuto al fatto che le potenze di 2 terminano ciclicamente per 2, 4, 8, 6, quando l'esponente è rispettivamente della forma 1+4k, 2+4k, 3+4k e 4+4k (k numero naturale positivo). Per questa ragione soltanto le potenze di 2 terminanti per 2 e 8 hanno esponenti della forma 1+4k e 3+4k, ovvero hanno esponenti dispari, mentre quelle terminanti per 4 e 6 hanno esponenti pari. Dato infine, che in un numero primo di Mersenne $2^{p}-1$ , deve essere $p$ numero primo, questo deve essere dispari tranne nel caso di $p=2$ corrispondente all'unico numero di Mersenne terminante con 3 (il numero 3 appunto).

I primi di Mersenne, scritti in base 2, sono anche primi palindromi, primi permutabili e primi di Gauss.

## Lista numeri primi di Mersenne

| # | p | $M_p$ | Cifre in $M_p$ | Data scoperta | Scopritore |
| - | - | - | - | - | - |
| 1 | 2 | 3 | 1 | Antichità | Ignoto |
| 2 | 3 | 7 | 1 | Antichità | Ignoto |
| 3 | 5 | 31 | 2 | Antichità | Ignoto |
| 4 | 7 | 127 | 3 | Antichità | Ignoto |
| 5 | 13 | 8191 | 4 | 1456 | Ignoto |
| 6 | 17 | 131071 | 6 | 1588 | Cataldi |
| 7 | 19 | 524287 | 6 | 1588 | Cataldi |
| 8 | 31 | 2147483647 | 10 | 1772 | Eulero |
| 9 | 61 | 2305843009213693951 | 19 | 1883 | Pervushin |
| 10 | 89 | 618970019642690137449562111 | 27 | 1911 | Powers |
| 11 | 107 | 162259276829213363391578010288127 | 33 | 1914 | Powers |
| 12 | 127 | 170141183460469231731687303715884105727 | 39 | 1876 | Lucas |
| 13 | 521 | 686479766…115057151 | 157 | 30 gennaio 1952 | Robinson |
| 14 | 607 | 531137992…031728127 | 183 | 30 gennaio 1952 | Robinson |
| 15 | 1.279 | 104079321…168729087 | 386 | 25 giugno 1952 | Robinson |
| 16 | 2.203 | 147597991…697771007 | 664 | 7 ottobre 1952 | Robinson |
| 17 | 2.281 | 446087557…132836351 | 687 | 9 ottobre 1952 | Robinson |
| 18 | 3.217 | 259117086…909315071 | 969 | 8 settembre 1957 | Riesel |
| 19 | 4.253 | 190797007…350484991 | 1281 | 3 novembre 1961 | Hurwitz |
| 20 | 4.423 | 285542542…608580607 | 1.332 | 3 novembre 1961 | Hurwitz |
| 21 | 9.689 | 478220278…225754111 | 2.917 | 11 maggio 1963 | Gillies |
| 22 | 9.941 | 346088282…789463551 | 2.993 | 16 maggio 1963 | Gillies |
| 23 | 11.213 | 281411201…696392191 | 3.376 | 2 giugno 1963 | Gillies |
| 24 | 19.937 | 431542479…968041471 | 6.002 | 4 marzo 1971 | Tuckerman |
| 25 | 21.701 | 448679166…511882751 | 6.533 | 30 ottobre 1978 | Noll e Nickel |
| 26 | 23.209 | 402874115…779264511 | 6.987 | 9 febbraio 1979 | Noll |
| 27 | 44.497 | 854509824…011228671 | 13.395 | 8 aprile 1979 | Nelson e Slowinski |
| 28 | 86.243 | 536927995…433438207 | 25.962 | 25 settembre 1982 | Slowinski |
| 29 | 110.503 | 521928313…465515007 | 33.265 | 28 gennaio 1988 | Colquitt e Welsh |
| 30 | 132.049 | 512740276…730061311 | 39.751 | 20 settembre 1983 | Slowinski |
| 31 | 216.091 | 746093103…815528447 | 65.050 | 6 settembre 1985 | Slowinski |
| 32 | 756.839 | 174135906…544677887 | 227.832 | 19 febbraio 1992 | Slowinski e Gage in Harwell Lab Cray-2 |
| 33 | 859.433 | 129498125…500142591 | 258 716 | 10 gennaio 1994 | Slowinski e Gage |
| 34 | 1.257.787 | 412245773…089366527 | 378.632 | 3 settembre 1996 | Slowinski e Gage |
| 35 | 1.398.269 | 814717564…451315711 | 420.921 | 13 novembre 1996 | GIMPS / Joel Armengaud (PC Pentium 90) |
| 36 | 2.976.221 | 623340076…729201151 | 895.932 | 24 agosto 1997 | GIMPS / Gordon Spence (PC Pentium 100) |
| 37 | 3.021.377 | 127411683…024694271 | 909.526 | 27 gennaio 1998 | GIMPS / Roland Clarkson (Pentium 200) |
| 38 | 6.972.593 | 437075744…924193791 | 2.098.960 | 1º giugno 1999 | GIMPS / Nayan Hajratwala (Pentium II 350) |
| 39 | 13.466.917 | 924947738…256259071 | 4.053.946 | 14 novembre 2001 | GIMPS / Michael Cameron (800 MHz AMD T-Bird PC) |
| 40 | 20.996.011 | 125976895…855682047 | 6.320.430 | 17 novembre 2003 | GIMPS / Michael Shafer (2 GHz Pentium 4 Dell Dimension PC) |
| 41 | 24.036.583 | 299410429…733969407 | 7.235.733 | 15 maggio 2004 | GIMPS / Josh Findley (2.4 GHz Pentium 4 Windows XP PC) |
| 42 | 25.964.951 | 122164630…577077247 | 7.816.230 | 18 febbraio 2005 | GIMPS / Martin Nowak (2.4 GHz Pentium 4 Windows XP PC) |
| 43 | 30.402.457 | 315416475…652943871 | 9.152.052 | 15 dicembre 2005 | GIMPS / Curtis Cooper e Steven Boone |
| 44 | 32.582.657 | 124575026…053967871 | 9.808.358 | 4 settembre 2006 | GIMPS / Curtis Cooper e Steven Boone |
| 45 | 37.156.667 | 202254406…308220927 | 11.185.272 | 6 settembre 2008 | GIMPS / Hans-Michael Elvenich, George Woltman, Scott Kurowski et al |
| 46 | 42.643.801 | 169873516…562314751 | 12.837.064 | 12 aprile 2009 | GIMPS / Odd M. Strindmo |
| 47 | 43.112.609 | 316470269…697152511 | 12.978.189 | 23 agosto 2008 | GIMPS / Edson Smith, George Woltman, Scott Kurowski et al |
| 48 | 57.885.161 | 581887266…724285951 | 17.425.170 | 25 gennaio 2013 | GIMPS / Curtis Cooper, George Woltman, Scott Kurowski et al |
| 49? | 74.207.281 | 300376418084…391086436351 | 22.338.618 | 7 gennaio 2016 | GIMPS / Curtis Cooper |
| 50? | 77.232.917 | 467333183359…069762179071 | 23.249.425 | 26 dicembre 2017 | GIMPS / Jonathan Pace |
| 51? | 82.589.933 | 148894445742…325217902591 | 24.862.048 | 7 dicembre 2018 | GIMPS / Patrick Laroche |
