Un numero primo è un numero intero divisibile solo per due numeri interi differenti: 1 e se stesso. Questa definizione è la più corretta, poiché in questo modo si esclude il numero 1 (non è divisibile per due interi differenti). I primi numeri primi sono: 2-3-5-7-11-13-17 eccetera.

Fu Euclide a dimostrare che i numeri primi sono infiniti (quindi dello stesso ordine di grandezza dei numeri naturali). La sua dimostrazione è semplice.

Se i numeri primi fossero finiti, ne esisterebbe uno più grande di tutti, che potremmo chiamare Pn. Moltiplichiamo allora tutti i numeri primi fra di loro e sommiamo a questo numero 1. In formule matematiche:

M = 2*3*5*7*11*13*17* ... *Pn + 1

Il numero M che abbiamo così ottenuto non è divisibile per 2, dato che è dispari.

Il numero M non è divisibile nemmeno per 3, dato che è un multiplo di 3 a cui abbiamo sommato 1.

Il numero M non è divisibile nemmeno per 5, dato che è un multiplo di 5 a cui abbiamo sommato 1.

Possiamo continuare con queste considerazioni fino a Pn.

Il numero M non è divisibile nemmeno per Pn, dato che è un multiplo di Pn a cui abbiamo sommato 1.

A questo punto i casi sono due:

1- M è un numero primo, e allora ne abbiamo trovato uno nuovo, maggiore di Pn.

2- M non è primo, ma allora ha fattori primi maggiori di Pn, quindi Pn non era il più grande numero primo.

In ogni caso, Pn non era il maggiore dei numeri primi, quindi i numeri primi sono infiniti.

Facciamo un esempio, immaginando che sia 7 il numero primo più grande.

M = 2*3*5*7 + 1 = 211 che è primo, quindi 7 non era il primo più grande.

Proviamo a usare 13.

M = 2*3*5*7*11*13 + 1 = 30031 che non è primo. Infatti, si può scomporre in 59 * 509, che sono due numeri primi più grandi di 13, quindi 13 non era il più grande.

Eulero trovò una dimostrazione diversa, ma oggi se ne conoscono almeno sei.

Per ora non è stato trovato nessun algoritmo capace di generare tutti i numeri primi. Tuttavia, Eratostene di Cirene, matematico greco vissuto nel II secolo a.C., ideò un sistema che prese il nome di Crivello di Eratostene (mostrato in figura). Il crivello funziona come un setaccio. Infatti, permette di determinare i numeri primi grazie a eliminazioni successive.

Il procedimento è semplice: si scrivono i numeri fino a un dato numero N, poi si cancellano tutti i numeri pari, poi i multipli di 3, poi quelli di 5 e via così, finché non sono stati eliminati tutti i numeri composti. In questo modo è facile ottenere i 25 numeri primi inferiori a100:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.

I più grandi numeri primi finora scoperti sono chiamati numeri primi di Mersenne e sono numeri che rispettano la formula:

Mp = 2^p - 1

Il numero di Mersenne “piesimo”, dove “p” è un numero primo, è dato da 2 elevato a “p” - 1.

Logicamente, non tutti i numeri primi “p” generano un numero di Mersenne.

I numeri di Mersenne che sono generati da un “p” inferiore a 100 sono:

M2 = 3

M3 = 7

M5 = 31

M7 = 127

M13= 8.191

M17= 131.071

M19= 524.287

M31= 2.147.483.647

M61= 2.305.843.009.213.693.951

M89= 618.970.019.642.690.137.449.562.111

Nel 1982 il più grande numero primo conosciuto di Mersenne era M44497 (quindi 2^44497 - 1).

Nel 2001 fu trovato: M13466917 (quindi 2^13466917 - 1).

Oggi si conoscono 51 numeri di Mersenne e gli ultimi diciassette sono stati scoperti grazie al progetto G.I.M.P.S. (Great Internet Mersenne Prime Search), un’iniziativa che sfrutta la capacità di calcolo inutilizzata di migliaia di computer di volontari in rete. Nel 2018 è stato scoperto il più grande numero primo mai calcolato: M82589933, un numero che ha 24.862.048 cifre