Numeri di Mersenne
Cosa sono i numeri di Mersenne
I numeri di Mersenne sono una serie numerica nella forma $$ M_k=2^k-1 $$ dove k è un numero intero maggiore di 1.
I numeri di Mersenne si indicano con il simbolo Mk e prendono il nome dal matematico Marin Mersenne che li studiò nel XVII secolo.
Alcuni numeri di Mersenne sono numeri primi mentre altri sono numeri composti.
Un esempio pratico
$$ M_2 = 2^2 - 1 = 3 \\ M_3 = 2^3 - 1 = 7 \\ M_4 = 2^4 - 1 = 15 \\ M_5 = 2^5 - 1 = 31 \\ M_6 = 2^6 - 1 = 63 \\ \vdots $$
Un numero di Mersenne che è anche primo è conosciuto come un "numero primo di Mersenne"
In generale, se Mk è un numero primo, allora anche il numero k lo è. Quindi, i numeri primi di Mersenne andrebbero ricercati considerando solamente gli indici che sono dei numeri primi.
$$ M_2 = 2^2 - 1 = 3 \\ M_3 = 2^3 - 1 = 7 \\ M_5 = 2^5 - 1 = 31 \\ M_{7} = 2^7 -1 = 127 \\ \vdots $$
Per questa ragione si dà particolare attenzione ai numeri di Mersenne con esponente $ k $ primo.
Tuttavia, non vale l'inverso. Se $ k $ è un numero primo, non è detto che anche il numero di Mersenne $ M_k $ lo sia.
Ad esempio $ M_{11} = 2^{11}-1 = 2047 $ è un numero composto $ 2047 = 23 \times 89 $.
Per verificare se un numero di Mersenne con $ k $ primo è a sua volta primo, posso usare il test di Lucas-Lehmer.
Nota. I numeri primi di Mersenne sono particolarmente interessanti per la ricerca dei numeri primi, perché hanno portato alla scoperta di alcuni dei numeri primi più grandi conosciuti. Ad esempio, uno dei più grandi numeri primi conosciuti è 282,589,933−1, scoperto nel 2018, è un numero di Mersenne. Sono particolarmente importanti anche nel campo della teoria dei numeri e delle applicazioni informatiche come la crittografia.
I numeri primi di Mersenne
Se Mk è un numero primo allora k è un numero primo $$ M_k \in P \rightarrow k \in P $$
Esempio
Il numero M2=3 è un numero primo.
Anche k=2 è un numero primo.
Nota. Non vale però l'inverso, se k è un numero primo non è detto che lo sia anche Mk. Ad esempio, M11 non è un numero primo anche se k=11 è un primo. $$ M_k=2^{11}-1=2047=23 \cdot 89 $$
Dimostrazione
Dimostro che se k non è primo, allora Mk non è primo.
Per ipotesi k è uguale al prodotto di due fattori a e b.
$$ k =ab $$
Quindi
$$ 2^k-1= 2^{ab}-1 = 2^a \cdot 2^b - 1 $$
che posso riscrivere in questa forma come prodotto di due fattori
$$ (2^a-1) \cdot (1+2^a+2^{2a}+...+2^{(b-1)a} ) $$
Pertanto, se k non è un numero primo, nemmeno Mk può essere un numero primo.
Esempio. Il numero k=4 non è un primo. Il numero M4 è $$ M_4 = 4^2-1= 15 $$ Riscrivo M4 con l'identità precedente usando i parametri a=2 e b=2 dove k=ab. $$ M_4 = (2^2 -1) \cdot (1+2^2) = 3 \cdot 5 = 15 $$ Ho così ottenuto una fattorizzazione del numero 15. Pertanto, il numero 15 non è un numero primo.
Teorema di Lucas
Un numero p-esimo di Mersenne Mp maggiore di 2 è un numero primo se Mp è un divisore di Lp-1.
Dove Lp è una successione ricorsiva creata da Lucas a partire da L1=4.
$$ L_{n+1} = L_n^2 - 2 $$
Ecco un esempio della successione ricorsiva di Lucas
$$ L_1 = 4 \\ L_2 = (4)^2-2 =14 \\ L_3 = (14)^2-2 =194 \\ L_4 = (194)^2-2 =37634 \\ L_5 = (37634)^2-2 =1416317954 $$
Esempio 1
Il numero di mersenne M3 è uguale a 7.
$$ M_3 = 2^3 -1 = 7 $$
Secondo Lucas è un numero primo se M3 è un divisore di L2.
$$ L_2 = 14 $$
In effetti, M3=7 divide L2=14.
Pertanto M3 è un numero primo.
