I numeri di Euclide. Il teorema dell'infinità dei numeri primi

---

Teorema
L'insieme Π dei numeri primi è infinito numerabile.
Dim.

Dalla fig. 1

Ne seguono due possibilità: a) ν_n è primo; b) ν_n non è primo. Il caso a) contraddice l'assunto iniziale, come anche il caso b) giacché ν_n risulterebbe divisibile per un primo maggiore di p_n, onde l'asserto.

Il teorema appena dimostrato consente di definire i numeri di Euclide:

che compongono una successione di elementi di N:

Esplicitiamo alcuni termini:

La natura ricorsiva dei numeri di Euclide è più evidente ridefinendoli in questo modo:

dove

A questo punto possiamo utilizzare il software Mathematica per generare una lista di numeri di Euclide e numeri primi di Euclide, ottenendo il grafico (in scala logaritmica) di fig.

da cui vediamo che i primi di Euclide tendono a rarefarsi. La cardinalità dell'insieme dei primi di Euclide è un problema aperto.