Infinità
I numeri primi sono infiniti. Questa scoperta fondamentale è dovuta ad Euclide (o perlomeno Euclide è quello che ce l'ha tramandata). La proposizione 20 del libro IX dei suoi Elementi afferma infatti:
I numeri primi sono di più di ogni assegnata moltitudine di numeri primi.
La dimostrazione di questa proposizione da parte di Euclide è ancora oggi considerata un insuperato modello di eleganza e semplicità. Essa procede nei seguenti termini: siano a, b, c numeri primi dati e consideriamo il loro prodotto aumentato di una unità, d = a·b·c+1. Allora ci sono due possibilità: o d stesso è primo, e quindi ho trovato un primo diverso da quelli dati, o non lo è. Se d non è primo, esso non è divisibile né per a, né per b, né per c, quindi deve essere divisibile per un numero primo diverso da quelli dati.
La dimostrazione può essere ulteriormente semplificata. Supponiamo che i primi siano in numero finito: p1<p2<...<p k. Consideriamo il numero d = p1·p2·...· pk + 1, che chiaramente non può essere primo perché più grande di tutti i pi, d'altra parte d deve essere primo perché non divisibile per nessuno dei primi noti. Assurdo.
Come ebbe a dire Godfrey Harold Hardy in Apologia di un matematico, «I numeri primi sono la materia grezza che serve a costruire l'aritmetica e il teorema di Euclide ci assicura che per tale compito noi disponiamo di gran quantità di materiale.»
Osserviamo esplicitamente che il procedimento di Euclide (con la sua idea geniale di aumentare di una unità il prodotto dei primi conosciuti) non fornisce un metodo pratico per trovare direttamente nuovi numeri primi a partire da quelli dati, ma solo un metodo teorico per costruire una successione infinita di numeri primi. Partiamo dal numero 2 e applichiamo il procedimento di Euclide:
2
2+1 = 3 (primo)
2·3+1 = 7 (primo)
2·3·5+1 = 31 (primo)
2·3·5·7+1 = 211 (primo)
2·3·5·7·11+1 = 2311
(primo)
2·3·5·7·11·13+1 = 30031 (che
non è primo e si scompone in 59·509).
Questa tabella prova che alcuni dei "numeri di Euclide" sono in effetti primi, ma certamente non tutti: oggi noi non sappiamo nemmeno se i numeri primi di questo tipo siano o no infiniti. La cosa che conta è che, comunque, essi ci permettono di provare che esistono infiniti primi.