L'infinita compagnia dei numeri primi

Sta uscendo in tutta Italia il film tratto dall'omonimo romanzo La solitudine dei numeri primi, che, lo confesso, non ho letto. Se il concetto dietro il titolo è che i matematici e gli scienziati sono in realtà soli con se stessi e con le loro ricerche, i numeri primi, al contrario, costituiscono una compagnia pressocché infinita che genera l'infinità dei numeri interi e reali che li circondano.
In effetti sappiamo che tra due numeri distinti esiste una infinità di altri numeri più piccoli, concetto che avevano intuito anche gli Antichi Greci, se è vero che Zenone giunse al paradosso della freccia, che scagliata non avrebbe mai potuto raggiungere il bersaglio. Però, come scritto nel titolo, oggi ci occupiamo non già di paradossi, ma di numeri primi. Quindi prima di proseguire è necessario definirli una volta per tutte:

Un numero intero è detto primo se non è il prodotto di due numeri più piccoli

Per convenzione il primo numero... primo è 2, anche perché tutti gli altri numeri, primo o meno che siano, vengono definiti a partire dall'1, quindi ha una sua logica non includerlo nell'elenco dei primi. A questo punto, a partire da 2, sappiamo che tutti i numeri pari non sono primi, in quanto tutti multipli di 2 per definizione, e quindi sappiamo anche che tutti i numeri primi sono dispari. La serie, quindi, prosegue come 3, 5, 7, 11 e così via.

Euclide secondo Raffaello Sanzio

Il primo a dimostrare che questo elenco è infinito fu Euclide. La sua dimostrazione è contenuta negli Elementi e parte da una collezione di $n$ numeri primi $p_1$, $p_2$, $\dots$, $p_n$. Facciamo il prodotto di tutti questi numeri primi (una sorta di fattoriale di numeri primi), ottenendo \[P = p_1 \cdot p_2 \cdot \dots \cdot p_{n-1} \cdot p_n\] Esaminiamo $P+1$: questi non è divisibile per 2, e la divisione dà resto 1; non è divisibile nemmeno per 3, essendo $P$ divisibile per 3; per lo stesso motivon non è divisibile per nessuno dei numeri primi successivi fino all'$n$-simo. Quindi si possono trarre due conclusioni:

1. o $P+1$ è primo, e quindi esiste un numero primo maggiore di $p_n$;
2. o $P+1$ non è primo, però non è nemmeno prodotto degli $n$ numeri primi di partenza, e per essere maggiore di $P$ uno dei suoi divisori primi deve essere superiore a $p_n$.

In entrambi i casi la conclusione è unica: $p_n$ non è il primo più grande, ma ne esiste sempre uno più grande.
A questo punto abbiamo anche definito una classe di numeri primi, i numeri di Euclide, numeri della forma $P+1$, che però non sono tutti numeri primi! Questa stranezza dipende dal fatto che al crescere di $p_n$ è sempre possibile trovare un divisore intero di $P+1$ tra $p_n$ e $\sqrt{P+1}$. E infatti il primo numero di Eulero non primo è $E_6 = 30031 = 59 \cdot 509$.
Conseguenza della dimostrazione di Euclide è la disuguaglianza \[p_{n+1} < p_n \cdot p_{n-1} \cdot \cdots \cdot 3 \cdot 2\] Questa disuguaglianza venne generalizzata nel 1907 da Bonse, che dimostrò prima questa \[p^2_{n+1} < p_n \cdot p_{n-1} \cdot \cdots \cdot 3 \cdot 2\] per $n > 3$, quindi \[p_{n+1} < p_n \cdot p^3_{n-1} \cdot \cdots \cdot 3 \cdot 2\] per $n > 5$.

Leonhard Euler

Un'altra dimostrazione storica dell'infinità dei numeri primi la dobbiamo a quel genio di Leonhard Euler, che partì dalla serie armonica \[S = 1+\frac{1}{2}+\frac{1}{3}+ \cdots + \frac{1}{n} + \cdots\] Eulerò osservò che questa serie è in effetti il prodotto delle serie geometriche con ragione inversa di un numero primo. Quindi, detto $P$ l'insieme di tutti i numeri primi, la formula di Eulero è: \[\prod_{p \in P} \frac{1}{1-\frac{1}{p}} = \sum_n \frac{1}{n}\] e visto che la serie armonica diverge, allora i numeri primi devono essere infiniti.
E' su questa formula, comunque, che Bernhard Riemann basò il suo lavoro e la formulazione della sua famosa congettura (vedi L'ossessione dei numeri primi parte 1, parte 2).
Nel corso dei secoli sono state poi realizzate altre dimostrazioni del teorema, alcune recentissime come quella di Juan Pablo Pinasco del 2009, New Proofs of Euclid's and Euler's theorems (pdf), o quella di quest'anno di Junho Peter Whang, Another Proof of the Infinitude of the Prime Numbers. Più vecchia, invece, la dimostrazione di Hillel Furstenberg, On the infinitude of primes del 1955. L'interesse per tale dimostrazione, però, è che coinvolge concetti di topologia, ovvero mette insieme due mondi apparentemente separati come quest'ultima disciplina con la teoria dei numeri, cui il teorema dell'infinità dei numeri primi appartiene.
Oltre ai primi, che poi non sono tutti primi, di Euclide, ci sono anche i primi di Mersenne, che si calcolano a partire dalla formula \[2^n-1\] con $n$ primo. Non tutti i numeri di Mersenne, però, sono primi, anche in questo caso: come ha scoperto Hudalricus Regius nel 1536, per $n = 11$ si ottiene 2047 che non è primo in quanto prodotto di 23 e 89.

Christian Goldbach

Sui primi ci sarebbe anche la congettura di Goldbach, enunciata in uno scambio epistolare risalente al 1742 tra Eulero e Christian Goldbach: ogni numero intero pari è somma di due numeri primi. Esiste anche una congettura debole, che è automaticamente dimostrata una volta dimostrata questa, ovvero che ogni numero dispari è somma di al massimo tre numeri primi, ed è semplice dedurre la dimostrazione per quest'ultima congettura dalla prima, ricordando che se sottraiamo ad ogni dispari maggiore di 3, 3 stesso, otteniamo un numero pari.
La congettura è stata protagonista di un romanzo uscito nel 2000, Zio Petros e la congettura di Goldbach di Apostolos Doxiadis, matematico e uno dei due sceneggiatori di Logicomix. Per l'occasione l'editore Faber & Faber propose un concorso: un premio di un milione di dollari per la dimostrazione, con limite di tempo massimo aprile 2002. Non giunse alcuna soluzione, anche perché avanzare in questa materia è estremamente difficile, visto il legame con l'altro insoluto problema secolare dell'ipotesi di Riemann. Ad ogni modo il miglior passo avanti fatto fino ad ora è quello di Tomas Oliveira Silva del 2007 che, migliorando quanto fatto da Jean-Marc Deshouillers, Yannick Saouter e Herman te Riele nel 1998, è arrivato a verificare la congettura fino a 10¹⁸.
E avviamoci alla conclusione: se, come spesso viene detto, i numeri primi sono estremamente importanti nella crittografia (la fattorizzazione, infatti, è un procedimento estremamente complesso, e le chiavi di crittazione basate su tale concetto sono praticamente inviolabili), nel 1994 Thomas Nicely, studiando una particolare classe di numeri primi, scoprì un baco nel Pentium Intel. Nicely, infatti, stava studiando i primi gemelli, ovvero le coppie di primi che distano uno dall'altro di 2 unità, come 3 e 5, 5 e 7, 11 e 13 e così via. Alla fine dei suoi calcoli, scoprì una contraddizione con dei calcoli precedenti, e dopo aver approfondito ogni più piccolo dettaglio del suo lavoro, si rese conto dell'esistenza del problema nel processore di calcolo utilizzato, come potete leggere nell'e-mail originale.
E con questo è tutto, così, come si concludevano una volta le belle storie, vi lascio con il classico:
Stretta la foglia, larga la via, dite la vostra, ch'io ho detto la mia.

---

Bibliografia:

• La piccola bottega delle curiosità matematiche del professor Stewart di Ian Stewart;
• Teorema di Euclide (versione inglese) e pagine correlate;
• Gli Elementi (versione inglese);
• Euclide e i numeri primi.

P.S.: stavo ormai concludendo questo lungo articolo, quando su Division by Zero, ecco un po' la coincidenza, leggo di un articolo sulla dimostrazione di Furstenberg!