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.