I numeri primi sono infiniti. Di questo fatto sono
state date varie dimostrazioni.
La prima dimostrazione conosciuta è dovuta
ad Euclide (300 a.C).

Il più semplice test di primalità è il
noto Crivello di Eratostene,
ma al di la del fatto che è piú semplice del metodo
delle divisioni successive, è adatto solo per numeri
relativamente piccoli.

Quando i numeri si fanno grandi, occorre
utilizzare altri test che però non sono generali. Si
applicano cioè a particolari forme di numeri (ad esempio
i numeri di Mersenne), oppure
sono validi per numeri non maggiori di un dato massimo.
Ad esempio esiste un test di primalità molto migliore
che non le divisioni successive o il Crivello di
Eratostene, ma vale “solo” per numeri minori di
341550071728321.

Le dimostrazioni di tali test sono piuttosto
complesse, per chi volesse approfondirle esiste una vasta
letteratura disponibile ed anche documentazione in
rete.

Il sito più completo e alla URL: http://www.utm.edu/research/primes/
e contiene numerose informazioni e link (in maggioranza
in Inglese e di complessità spesso a livello di ricerca)
specifici sui numeri primi.

Per quanto riguarda la regolarità dei numeri
primi la risposta è, in assoluto: No, non esiste alcuna
regolarità dei numeri primi.

Tuttavia, il numero di numeri primi non maggiori
di un dato numero x, funzione che è chiamata pi(x), ha
delle sorprendenti proprietà:

Il “teorema dei numeri primi” afferma
che:

                  pi(x)
        lim     ---------   = 1
        x->inf   x/(log x)

in parole povere x/(log x) è una buona
approssimazione di pi(x).

Da questo teorema (la cui dimostrazione ometto
per pietà del lettore) si ricavano due
conseguenze:

1. l’ ennesimo (n-esimo) numero primo è,
   all’incirca uguale a: n (log n)
2. 
   
3. La probabilità che un numero x sia primo è:
   1/(log x)

Queste non sono regolarità di tipo funzionale (ovvero
non ci consentono di ricavare un numero primo come
funzione di altri numeri), ma di tipo sostanzialmente
“statistico”.

Esistono infiniti numeri primi

Dimostrazione (Euclide, circa 300 A.C.):

Siano p₁,p₂,…,p_r Tutti i numeri primi

minori o uguali a p_r

sia P = p₁p₂p₃…p_r

+ 1 (il prodotto di tutti i numeri primi fino a p_r, più

uno)

Allora o P è a sua volta primo, e si giunge subito alla

conclusione sotto riportata, oppure esiste almeno un numero p divisore

primo di P.

Se p esiste deve essere diverso da un qualunque p_i compreso

nell’insieme {p₁,p₂,…,p_r} , altrimenti

poiché esso è fattore sia di P che del prodotto p₁p₂p₃…p_r

deve essere necessariamente fattore anche della loro differenza ossia di:

P – p₁p₂p₃….p_r = 1; e ciò

è impossibile.

Conclusione:

Dato un qualunque insieme di tutti i numeri primi fino ad un dato massimo

esiste almeno un altro numero primo maggiore del massimo. Di conseguenza

il numero di numeri primi è infinito.

Crivello di Eratostene (circa 240 A.C.)

Algoritmo che consente di individuare tutti i numeri primi minori di un
certo numero dato.

Supponiamo di voler trovare tutti i numeri primi minori o uguali ad N.

Si inzia scrivendo un elenco dei numeri da 2 ad N.

L’algoritmo procede come segue:

1. Si prende il numero più piccolo nella lista. Questo è un numero primo
   (all’inizio è 2, ed è ovvio che sia primo, ma come vedremo la regola
   continua a valere anche alle successive iterazioni) e fa parte della
   soluzione.

2. Si cancella il numero primo trovato e tutti i suoi multipli.

   Se il numero trovato è minore della radice quadrata di N, si torna
   al passo 1)

   altrimenti
   

   L’algoritmo è terminato. I numeri primi sono tutti quelli trovati,
   più quelli che rimangono non cancellati nella lista.

I numeri di Mersenne

Sono numeri della forma 2^N-1 e sono divenuti noti, inizialmente,

grazie ad un errore: molti matematici prima del ‘500 ritenevano che tutti

i numeri di Mersenne con esponente primo fossero primi. A partire dal ‘500

sono stati invece trovati molti numeri di Mersenne ad esponente primo non

primi (ad esempio 2¹¹-1, 2²³-1, 2²⁹-1).

Tuttavia i numeri di Mersenne rimangono “interessanti”, soprattutto

perché esistono test di primalità per numeri di questa forma

che hanno reso possibile verificare la primalità di numeri molto

grandi. Anzi i numeri primi più grandi che si conoscono sono tutti

numeri di Mersenne, ad esempio è stato dimostrato che sono primi

i numeri:

2¹²⁵⁷⁷⁸-1, 2^1398269-1 e 2^2976221-1.

I primi due sono, rispettivamente il 34-esimo e 35-esimo numero primo

di Mersenne, mentre il terzo (il più grande conosciuto alla data

del 5 dicembre 1997) è candidato al posto di 36-esimo (non è

ancora provato che non ci sia un numero primo di Mersenne maggiore del

35-esimo, ma minore di questo). L’ultimo dei tre numeri, se scritto in

decimale, avrebbe più di 895000 cifre.

ritorna all’inizio