I NUMERI PRIMI SONO INFINITI

La più antica dimostrazione pervenutaci è quella di Euclide. La sua dimostrazione parte da un qualunque insieme di numeri primi p1,p2,...,pn, e costruisce un numero primo diverso da tutti i pi. Si inizia moltiplicando tra di loro tutti questi numeri e sommando un'unità, ottenendo come risultato un nuovo numero q che potrà essere o non essere primo. Se q è primo, la dimostrazione è terminata; altrimenti esso dovrà avere almeno un divisore d primo. Per costruzione, d non può essere nessuno dei pi. Pertanto, d è l'ulteriore numero primo cercato.
Ecco alcuni esempi numerici. Partendo da 2 e 3, otteniamo (2*3)+1 = 7 che è un numero primo; aggiungendolo agli altri arriviamo a (2*3*7)+1 = 43 che è ancora primo; invece (2*3*7*43)+1 = 1807 che non è primo ma ha il fattore primo 13.