Anche noi matematici abbiamo i nostri record; anche a noi piace battere primati e spostare in avanti i confini. Il record di cui parliamo oggi riguarda una notizia di pochi giorni fa: è stato trovato un nuovo numero primo di Mersenne, mooolto piú grande del precedente. Ce ne parla, come al solito, Alessandro Zaccagnini. 

Se vogliamo essere precisi, la notizia è che da oggi sappiamo che \(N = 2^{136\,279\,841} – 1\) è un numero primo; non è difficile vedere che \(N\) ha 41 024 320 cifre decimali, e al suo confronto il record precedente, il numero \(M = 2^{82\,589\,933} – 1\), con “solo” 24 862 048 cifre decimali appare un lillipuziano … Questo numero primo è stato trovato da Luke Durant il 12 ottobre scorso, e la sua scoperta è stata confermata una settimana dopo da un calcolo indipendente.

È piuttosto difficile dare un’idea della grandezza di un numero come questo: si stima che nell’universo ci possano essere \(10^{80}\) atomi, approssimativamente \(2^{265}\). Se l’universo fosse una gigantesca scacchiera e ad ogni mossa dovessimo scegliere mezzo milione di pezzi (atomi) da muovere, \(2^{136\,279\,841} – 1\) sarebbe piú o meno il numero delle mosse possibili.

L’interesse per i numeri primi del tipo \(N = 2^p – 1\) nasce con Euclide, perché ha dimostrato che se \(M_p = 2^p – 1\) è primo allora \(2^{p – 1} (2^p – 1)\) è un numero perfetto, cioè uguale alla somma dei suoi divisori propri (dette “parti” nella terminologia di Euclide: un numero è perfetto se è uguale alla somma delle sue parti). Lasciamo ai lettori la verifica che \(M_2 = 3\), \(M_3 = 7\), \(M_5 = 31\) sono numeri primi e di conseguenza \(6\), \(28\) e \(496\) sono numeri perfetti. La notazione \(M_p\) è in onore di Marin Mersenne, di cui parlerò piú avanti. Eulero ha dimostrato che i numeri perfetti pari sono tutti ottenuti in questo modo, e una delle piú antiche congetture della matematica, forse la piú antica di tutte, è che non esistano numeri perfetti dispari.

Il numero \(M_n\) è sicuramente composto per \(n\) composto; per esempio, se \(n = 2 m\) è pari allora \(M_n = 2^{2 m} – 1 = (2^m – 1)(2^m + 1)\), che può essere primo solo se \(m = 1\). Analogamente, \(M_{3 m} = 2^{3 m} – 1 = (2^m – 1)(2^{2 m} + 2^m + 1)\), che può essere primo solo se \(m = 1\); i “prodotti notevoli” ci aiutano a riconoscere che una condizione necessaria affinché \(M_n\) sia un numero primo è che \(n\) sia primo a sua volta. Possiamo dare anche una dimostrazione “visuale” della necessità della condizione: supponiamo che \(n\) sia un numero composto e che \(n = a b\), con \(a\), \(b > 1\). Il numero \(2^n – 1\) scritto in base 2 è una sequenza di \(n\) bit: dunque \[\underbrace{1 \dots 1}_{n \text{ bit}}
=
\underbrace{1 \dots 1}_{a \text{ bit}} \dots
\underbrace{1 \dots 1}_{a \text{ bit}}\] dove la sequenza al secondo membro deve essere ripetuta \(b\) volte. Di conseguenza \(2^a – 1\), che scritto in base \(2\) è una sequenza di \(a\) bit, deve dividere \(n\) e quindi \(2^n – 1\) è composto. Per esempio \(31 = 2^5 – 1 = (11111)_2\) divide \(2^{10} – 1 = (1111111111)_2\) e infatti \((1111111111)_2 = (11111)_2 \cdot (100001)_2\), cioè \(2^{10} – 1 = (2^5 – 1)(2^5 + 1)\).

La condizione non è sufficiente: in effetti \(M_{11} = 2043 = 23 \cdot 89\). Lo stesso Eulero ha dimostrato che gli eventuale fattori primi \(q\) di \(M_p\) sono di forma speciale, e in particolare che \(q \equiv 1 \bmod 2 p\); la dimostrazione non è particolarmente complicata: si usa il “Piccolo” Teorema di Fermat e qualche altra proprietà dei numeri primi.

Marin Mersenne, matematico e filosofo, teologo e prete cattolico, è un personaggio piuttosto curioso: nella prima metà del XVII secolo ha fatto da intermediario tra decine di corrispondenti scientifici i piú famosi dei quali sono Galileo Galilei, Cartesio, Fermat, diffondendo le loro idee fra i colleghi. Insomma, ha fatto il lavoro certosino che oggi affideremmo ad un server su Internet … Mersenne ha dato una lista di numeri primi \(p\) per cui \(M_p\) è a sua volta primo, ma questa lista contiene qualche errore e qualche omissione, corretti solo dopo l’avvento dei computer digitali.

Il calcolo vero e proprio è stato distribuito su migliaia di processori che lavorano in parallelo: alcuni volontari “regalano” il tempo macchina di cui non hanno bisogno per fare un pezzettino del calcolo. I dettagli della “Great Internet Mersenne Prime Search” (GIMPS) si possono consultare nel loro sito. Vale la pena di osservare che i recenti progressi sono dovuti alle GPU (Graphics Processing Units) progettate per le applicazioni grafiche e “dirottate” su ogni tipo di problema grazie alla loro grande efficienza. In conclusione, una nota sugli algoritmi: naturalmente non è possibile verificare la definizione di numero primo mediante una successione di divisioni, ma esiste un criterio ad hoc scoperto da Édouard Lucas nella seconda metà dell’Ottocento che riconduce la primalità di \(M_p\) alla verifica di una condizione notevolmente piú semplice da controllare. La dimostrazione della correttezza di questo criterio richiede di saper gestire estensioni quadratiche dei numeri razionali.

Immagine di copertina: Foto di Gerd Altmann da Pixabay

Alessandro Zaccagnini