Il teorema dei numeri primi

Il teorema dei numeri primi

A cura di Flavio Cimolin (ultimo aggiornamento: 20/02/2008)

Pubblicato su Matematicamente.it Magazine n. 5, gennaio 2008

Introduzione

Da millenni i numeri primi e le loro bizzarre proprietà stuzzicano la curiosità di matematici e appassionati. I problemi in cui essi vengono tirati in ballo appaiono infatti talmente semplici nel modo in cui possono essere espressi da risultare un continuo sberleffo nei confronti degli eminenti matematici di tutto il mondo che tentano invano di risolverli.

Basti pensare alle famosissime congetture tuttora irrisolte di Goldbach (ogni numero pari maggiore di due si può esprimere come somma di due primi) e dei primi gemelli (esistono infinite coppie di primi a distanza due).

Solo recentemente e con grande clamore è stata annunciata la dimostrazione del cosiddetto Ultimo Teorema di Fermat (non esistono “terne pitagoriche” con esponenti maggiori di due), la quale tuttavia si basa su artifici matematici talmente complessi da richiedere mesi e mesi di studio ai più esperti matematici solo per intuire il percorso della dimostrazione!

I numeri primi non sono altro che una “base moltiplicativa” dell’insieme dei numeri naturali, alternativa a quella additiva sulla quale esso è definito (la definizione formale dei numeri naturali segue infatti il principio di induzione: ad ogni numero N ne segue un altro N+1, dato dalla somma del precedente più uno. Così nascono i numeri 1, 2, 3, 4, 5, …, N, N+1, …).

Nonostante i primi compaiano in maniera assolutamente lineare non appena si introduca nell’insieme dei naturali l’operazione di moltiplicazione, per qualche oscura ragione essi sono come avvolti da un alone di mistero che impedisce di comprendere a fondo i loro speciali intrecci.

Fra i numerosissimi problemi che si possono formulare riguardo ai numeri primi, ci occupiamo qui di presentarne uno che ha a che fare con il loro “conteggio”: quanti sono i numeri primi? E, se sono infiniti, con quale tipo di legge crescono?

La risposta a questa domanda è stata trovata e va sotto il nome di Teorema dei Numeri Primi. L’avventura che ha condotto eminenti matematici dei tre secoli scorsi, come Gauss, Riemann, Hadamard e De la Vallée Poussin, verso la dimostrazione del tutt’altro che semplice risultato è stata talmente trasversale da chiamare in causa addirittura i numeri complessi e le più avanzate tecniche analitiche che operano su di essi, tanto da condurre a formulare un altro celebre problema, passato alla storia col nome di Ipotesi di Riemann.

L’infinità dei numeri primi

Anzitutto è ragionevole domandarsi quanti siano i numeri primi, nel caso essi fossero solo un numero finito. Su questo punto già Euclide nel IV secolo a.C. sollevò il primo velo, mostrando che esistono infiniti numeri primi.

La sua dimostrazione classica (a cui ne sono seguite decine di altre nel corso dei secoli) è talmente semplice da poter essere esposta per intero.

Supponiamo per assurdo che esista solo un numero finito di numeri primi. Allora li possiamo elencare tutti dal più piccolo al più grande: chiamiamoli p 1, p 2, p 3, …, p n.

Adesso andiamo a calcolare il numero

N = p 1 · p 2 · p 3 · ⋅⋅⋅ · p n + 1

K

N è divisibile per p 1? No, perché la parte ove c’è il prodotto lo è, ma ad essa è aggiunto un 1, quindi dà resto 1.

È divisibile per p 2? No, per lo stesso motivo di prima, in quanto la divisione di N per p 2 dà resto 1. Questo vale evidentemente per tutti i p i, quindi N non può essere divisibile per nessuno dei numeri primi che abbiamo elencato.

Allora deve essere un numero primo esso stesso (oppure il prodotto di altri numeri primi diversi da quelli elencati), ma ciò va contro la nostra ipotesi iniziale di aver potuto elencare tutti i numeri primi.

Conclusione: esistono infiniti numeri primi!

Vale la pena osservare che la tecnica di Euclide serve a dimostrare che, dato un insieme di numeri primi, esiste sempre un numero più grande che sia coprimo con essi (ovvero che non abbia fattori comuni con alcuno di essi).

Questo non significa che il numero N così costruito sia esso stesso primo, come mostra chiaramente il seguente controesempio:

2 · 3 · 5 · 7 · 11 · 13 + 1 = 30031 = 59 · 509

http://www.matematicamente.it

Flavio Cimolin – Il teorema dei numeri primi

Il conteggio dei numeri primi

Bene, ora che abbiamo dimostrato che i numeri primi sono infiniti, ha senso chiederci quanti siano rispetto ai numeri naturali, nel senso che andremo subito a precisare.

Ci sono vari modi di confrontare tra loro insiemi infiniti, ad esempio seguendo la teoria di Cantor si potrebbe dimostrare che i numeri primi hanno la stessa cardinalità dei numeri naturali; questo tuttavia ci sarebbe di poco aiuto, in quanto per conoscere effettivamente qualcosa in più sulla distribuzione dei primi abbiamo bisogno di un risultato quantitativo.

Occorre cioè trovare un modo formale per indicare che, ad esempio, i numeri pari sono “la metà” dei naturali, i multipli di tre sono “un terzo”, e così via, in modo da poter dire anche “quanti sono” i quadrati perfetti, i cubi o i numeri primi appunto.

Il modo corretto di affrontare la questione dal punto di vista matematico è quello di definire un “contatore” della tipologia di numeri che si vuole considerare, ovvero una funzione che indichi quante occorrenze di numeri di quella specie ci sono fino ad un valore dato.

Chiamiamo ad esempio S (n) la funzione che indica quanti sono i numeri pari da 1 fino ad n. Se n è pari, S pari (n) = n/2, se n è dispari S pari (n) = (n-1)/2.

Supponendo ora che n diventi sempre più grande si può approssimare considerando solo l’ordine di grandezza principale e dire che S pari (n) ≍ n/2.

Una procedura di questo genere è detta in gergo una “stima asintotica”, in quanto non fornisce il valore esatto, ma fornisce un valore che è tanto più prossimo a quello giusto quanto più i numeri coinvolti crescono.

Questo modo di procedere costituisce esattamente la formalizzazione matematica di quello che abbiamo in mente quando pensiamo che “i numeri pari sono la metà dei naturali”.

È semplice osservare che per i numeri dispari varrà analogamente S dispari (n) ≍ n/2, per i multipli di tre varrà S tre (n) ≍ n/3, e così via.

Seguendo le regole delle stime asintotiche, non è difficile mostrare che per i quadrati perfetti vale S quadrati (n) ≍ sqrt(n) e per le potenze di due S potenze2 (n) ≍ log₂(n).

La funzione inversa

Un modo perfettamente speculare di vedere la stessa cosa è quello di chiedersi quanto valga l’n-esimo numero di un certo tipo. Chiamiamo N pari (n) l’n-esimo numero pari.

Invertendo la relazione per S pari (n) avremo che N pari (n) ≍ 2n.

Volutamente non abbiamo inserito il simbolo di uguaglianza, ma quello di approssimazione, in quanto, nell’ottica di sostituire i pari con i numeri primi, non pretendiamo di conoscere esattamente il valore dell’n-esimo numero, ma ci accontentiamo di averne una sua stima.

Ecco perché, facendo lo stesso con i dispari, avremmo N dispari (n) ≍ 2n; e poi N tre (n) ≍ 3n, N quadrati (n) ≍ n, N potenze2 (n) ≍ 2ⁿ.

Le funzioni S xxx sono esattamente le inverse delle funzioni N xxx.