Cosa devi sapere sui numeri primi

I numeri primi sono infiniti?

Una volta scoperto che i numeri primi sono gli "atomi dell'aritmetica" viene spontaneo chiedersi: esiste un massimo tra i numeri primi? Ovvero la sequenza dei numeri primi è finita o infinita? Vediamo con quale frequenza sono presenti i numeri primi nella sequenza dei numeri naturali:

• Nei primi 10 numeri naturali ci sono 4 numeri primi che rappresentano il 40% del totale.

• Nei primi 100 numeri naturali ci sono 25 numeri primi che rappresentano il 25% del totale.

• Nei primi 1000 numeri naturali ci sono 168 numeri primi che rappresentano il 16,8% del totale.

• Nei primi 10.000 numeri naturali ci sono 1.229 numeri primi che rappresentano il 12,29% del totale.

• Nei primi 100.000 numeri naturali ci sono 9.592 numeri primi che rappresentano il 9,592% del totale.

Come si vede i numeri primi diminuiscono man mano che si considera un intervallo di numeri naturale sempre più grande. Tutto ciò fa supporre che i numeri primi finiscono per esaurirsi completamente e quindi la sequenza dei numeri primi sia finita. Ma contrariamente alla nostra supposizione Euclide dimostrò che i numeri primi sono infiniti. Si tratta di una dimostrazione per assurdo. In una dimostrazione per assurdo si fa vedere che se si presuppone vera l'ipotesi opposta a quella che si vuol dimostrare, questa determina un risultato incoerente in quanto contraddice l'ipotesi iniziale e si conclude che l'ipotesi deve essere vera e non falsa altrimenti si ottiene un assurdo. Supponiamo, per assurdo, che i numeri primi non siano infiniti e che essi siano:

dove p_n è il numero primo più grande.

Consideriamo il numero

ovvero il successore del prodotto di tutti i numeri primi. Il numero m non è divisibile per alcun numero primo della lista poichè tale divisione fornisce, in ogni caso, resto 1. Pertanto ci sono due possibilità:

• m è un numero primo ed essendo maggiore di p_n non è vero che p_n è il più grande dei numeri primi.

• m è un numero composto e quindi è il prodotto di due numeri primi che non possono essere presenti nella sequenza finita dei numeri primi. Pertanto anche in questo caso non è vero che p_n è il più grande dei numeri primi.

In ogni caso si perviene a una contraddizione: esisterebbe infatti almeno un numero primo non presente nella lista contro l'ipotesi e quindi i numeri primi sono infiniti. Consideriamo due esempi concreti di una sequenza finita di numeri primi, applichiamo il procedimento della dimostrazione per assurdo e vediamo che in entrambi casi si ottiene una contraddizione.

1. Supponiamo che i numeri primi siano finiti e siano 2, 3, 5, 7, 11.
   
   Consideriamo

   m = 2 ⋅ 3 ⋅ 5 ⋅ 7 ⋅ 11 + 1 = 2311

   Il numero 2311 è primo e non è presente nella lista iniziale.

2. Supponiamo che i numeri primi siano finiti e siano 2, 3, 5, 7, 11, 13.
   
   Consideriamo

   m = 2 ⋅ 3 ⋅ 5 ⋅ 7 ⋅ 11 ⋅ 13 + 1 = 30031

   Il numero 30031 è composto e la sua fattorizzazione in numeri primi è:

   30031 = 59 ⋅ 509

   59 e 509 non sono presenti nella lista iniziale.