Perché i numeri primi non finiscono mai? La dimostrazione di Euclide

Che cosa rende primo un numero

Un numero primo è un intero maggiore di 1 divisibile senza resto soltanto per 1 e per se stesso. I primi iniziano con 2, 3, 5, 7, 11 e 13. Il 6, invece, è composto perché si può scrivere come 2 × 3; il 12 è composto perché, fra le altre possibilità, vale 3 × 4. Il numero 1 non è primo: escluderlo permette di scomporre ogni intero maggiore di 1 in fattori primi in modo essenzialmente unico.

Questa scomposizione fa dei numeri primi una sorta di alfabeto moltiplicativo. Per esempio 84 = 2 × 2 × 3 × 7. Possiamo cambiare l’ordine dei fattori, ma non sostituirli con un altro insieme di primi che dia ancora 84. Il risultato è noto come teorema fondamentale dell’aritmetica ed era già presente, in forma antica, negli Elementi di Euclide.

L’idea decisiva: costruire un numero che sfugge all’elenco

Immaginiamo, per assurdo, di avere scritto tutti i numeri primi esistenti in un elenco finito: p₁, p₂, fino a pᵣ. Non importa quanto sia lungo l’elenco. Moltiplichiamo tutti i suoi elementi e aggiungiamo 1. Chiamiamo N il risultato: N = p₁ × p₂ × … × pᵣ + 1.

Ora proviamo a dividere N per uno qualunque dei primi elencati. Il grande prodotto è divisibile esattamente per quel primo; dopo aver aggiunto 1 resta sempre un resto di 1. Dunque nessuno dei primi della lista può dividere N. Eppure N è maggiore di 1: o è primo, oppure, se è composto, deve avere almeno un fattore primo. In entrambi i casi compare un primo che non era nell’elenco iniziale.

Questo contraddice l’ipotesi di avere già raccolto tutti i primi. Il ragionamento vale per qualsiasi elenco finito, anche immenso. Perciò non esiste un ultimo numero primo: i primi sono più numerosi di qualunque lista finita che possiamo preparare.

Un esempio piccolo, passo dopo passo

Prendiamo l’elenco 2, 3 e 5. Il loro prodotto è 30; aggiungendo 1 otteniamo 31. Nessuno tra 2, 3 e 5 divide 31, che in questo caso è esso stesso primo. Abbiamo trovato un primo fuori dall’elenco.

Ma non bisogna concludere che il prodotto dei primi più 1 sia sempre primo. Se prendiamo 2, 3, 5, 7, 11 e 13, il prodotto più 1 è 30.031, che è composto: 30.031 = 59 × 509. La prova funziona lo stesso, perché 59 e 509 sono fattori primi non presenti nella lista di partenza. Serve l’esistenza di almeno un nuovo fattore primo, non che N sia necessariamente primo.

Infiniti, ma sempre più radi

Sapere che i primi non finiscono non dice che siano distribuiti a intervalli regolari. All’inizio ne incontriamo molti; andando verso numeri più grandi diventano in media più rari. Il teorema dei numeri primi descrive questa tendenza: vicino a un numero grande n, la probabilità approssimativa che un intero sia primo è circa 1 diviso il logaritmo naturale di n.

Questa è una legge statistica su grande scala, non una ricetta capace di indicare il prossimo primo. Possono comparire tratti relativamente affollati e lunghi intervalli senza primi. L’ordine generale convive quindi con un’irregolarità locale che continua ad alimentare la ricerca. Domande semplici da formulare, come l’esistenza di infinite coppie di primi gemelli distanti 2, restano aperte.

Come si trovano i primi senza provare ogni divisore

Per elencare i primi fino a una soglia piccola si può usare il crivello di Eratostene. Si scrivono gli interi a partire da 2, si conserva il primo numero non cancellato e si eliminano tutti i suoi multipli; poi si ripete con il successivo numero rimasto. I multipli di 2 scompaiono, poi quelli di 3, di 5 e così via. Quelli che resistono sono primi.

I computer che cercano numeri primi enormi impiegano metodi molto più sofisticati, ma la distinzione di base non cambia: bisogna stabilire se un numero possiede fattori non banali. La prova dell’infinità, invece, non richiede di completare questa ricerca. Garantisce logicamente che, oltre qualsiasi raccolta già trovata, esiste ancora almeno un altro primo.

Perché i numeri primi contano anche fuori dalla teoria

I primi non sono soltanto una curiosità. Alcuni sistemi crittografici a chiave pubblica, come RSA, sfruttano una forte differenza pratica: moltiplicare due grandi primi è relativamente facile, mentre ricavare quei fattori conoscendo soltanto il prodotto può essere estremamente difficile per i computer convenzionali. Non tutta la crittografia dipende da questo problema, e gli standard moderni stanno introducendo anche algoritmi resistenti ai futuri computer quantistici.

La dimostrazione di Euclide non rende sicuro un messaggio e non fornisce un metodo rapido per trovare primi giganteschi. Mostra però qualcosa di più fondamentale: per quanto lontano ci spingiamo, la materia prima dell’aritmetica non si esaurisce. Da una domanda elementare nasce un ragionamento generale, breve e ancora valido dopo oltre duemila anni.