Numero primo di Mersenne

In matematica un numero primo di Mersenne è un numero primo inferiore di uno rispetto ad una potenza di due. I numeri primi di Mersenne sono esprimibili come:

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

con ${\displaystyle p}$ intero positivo primo; infatti, si può dimostrare che se ${\displaystyle n}$ non è primo, allora ${\displaystyle 2^{n}-1}$ non è primo. Tale numero ${\displaystyle p}$ è talvolta indicato come esponente di Mersenne (successione A000043 in OEIS). Si noti che ${\displaystyle 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 ${\displaystyle M_{p}=2^{p}-1}$ risulta anch'esso primo.

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

${\displaystyle 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 ${\displaystyle 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 ${\displaystyle M_{p}}$ composti con ${\displaystyle p}$ primo. Ad esempio (e Fermat fu il primo ad evidenziare e usare questa proprietà) si può dimostrare che ogni fattore primo di ${\displaystyle M_{p}}$ dev'essere del tipo ${\displaystyle 2kp+1}$ con ${\displaystyle k}$ intero positivo^[1].

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 ${\displaystyle n}$ fino a ${\displaystyle n=257}$. Tale lista conteneva però alcuni errori: includeva ${\displaystyle M_{67}}$ e ${\displaystyle M_{257}}$ (che non sono primi), mentre non comparivano ${\displaystyle M_{61}}$, ${\displaystyle M_{89}}$ e ${\displaystyle M_{107}}$ (che sono primi).

I primi dodici numeri primi di Mersenne sono:

${\displaystyle M_{2}=2^{2}-1=3}$

${\displaystyle M_{3}=2^{3}-1=7}$

${\displaystyle M_{5}=2^{5}-1=31}$

${\displaystyle M_{7}=2^{7}-1=127}$

${\displaystyle M_{13}=2^{13}-1=8191}$

${\displaystyle M_{17}=131071}$

${\displaystyle M_{19}=524287}$

${\displaystyle M_{31}=2147483647}$

${\displaystyle M_{61}=2305843009213693951}$

${\displaystyle M_{89}=618970019642690137449562111}$

${\displaystyle M_{107}=162259276829213363391578010288127}$

${\displaystyle M_{127}=170141183460469231731687303715884105727}$

I numeri primi di Mersenne sono collegati con i numeri perfetti. Nel IV secolo a.C. Euclide dimostrò che se ${\displaystyle M_{n}}$ è un numero primo, allora ${\displaystyle {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) è ${\displaystyle M_{82589933}}$. Ha più di 24 milioni di cifre decimali ed è stato anch'esso trovato nell'ambito GIMPS:

${\displaystyle M_{82589933}=2^{82589933}-1}$^[2]

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₁₀ = 11₂

7₁₀ = 111₂

31₁₀ = 11111₂

127₁₀ = 1111111₂

8191₁₀ = 1111111111111₂.

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 ${\displaystyle 2^{p}-1}$ , deve essere ${\displaystyle p}$ numero primo, questo deve essere dispari tranne nel caso di ${\displaystyle 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.