Casella di testo: Tra tutti i numeri naturali acquistano un posto particolare quelli primi, cioè quelli che non si possono ottenere come prodotto di altri numeri interi, non considerando 1 come fattore.
Dovendoci occupare dei numeri primi una domanda che inevitabilmente ci poniamo è:
Quanti sono i numeri primi?
E’ possibile che da un certo punto in poi, nella sequenza dei numeri naturali, non ci siano altri numeri primi, oltre a quelli già trovati? 

Una brillante soluzione a questo dilemma è stata data fin dall’antichità da Euclide, vediamola.
(Chi pensa di essere una insignificante unità tra miliardi di persone, si rincuori vedendo quanto sia determinante una sola unità nella dimostrazione seguente)

Supponiamo che i numeri primi non siano infiniti, ma soltanto:   p1, p2 ,…., pn
Sia M il numero ottenuto moltiplicando tra di loro tutti questi numeri primi:
M = p1·p2 ·…. ·pn
Aggiungiamo 1 ad M e poniamo:  
G = M + 1        cioè,      G = p1·p2 ·…. ·Pn + 1
Ci chiediamo:  il numero G è primo o multiplo?
Poiché abbiamo supposto di avere esaurito tutti i numeri primi nell’ottenere il prodotto M, dovremo rispondere che G è necessariamente multiplo.
Ma se G è multiplo sarà divisibile per uno dei fattori primi p di M, perché non ci sono altri fattori primi oltre questi. 
Dividiamo per p:
G/p = M/p+1/p
Da questa uguaglianza risulta però che p non può essere divisore di G, perché altrimenti sarebbe divisore anche di 1. 
Poiché siamo caduti in una evidente contraddizione, la nostra ipotesi iniziale che i numeri primi siano in quantità finita non può essere vera, per cui dovremo concludere che indubbiamente i numeri primi sono infiniti.   
(Nel libro “n esp1 - Un ordinamento possibile dei numeri primi” io sostengo che i numeri primi non solo sono infiniti, ma addirittura è possibile  associare ad ogni intero n della successione dei numeri naturali uno o più numeri primi, sempre diversi da quelli trovati precedentemente. In questo modo si arriva al paradosso che i numeri primi sono più numerosi degli stessi numeri interi di cui fanno parte.  Risultati di questo tipo si ottengono quando si mettono a confronto insiemi numerici infiniti).

Riflettiamo sul teorema appena dimostrato con qualche esempio pratico.
Dati i numeri primi:  2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 , moltiplichiamo alcuni di questi, presi in successione a cominciare dal più piccolo, e aggiungiamo 1 al loro prodotto. 
Facciamoci una domanda: il numero G che si ottiene in questo modo è un numero primo? 
Se ci affrettassimo nella risposta, potremmo essere indotti dalla dimostrazione del teorema di Euclide a fare una deduzione errata e rispondere con una affermazione. Del resto, avendo a disposizione un numero limitato di numeri primi, possiamo fare delle prove pratiche che ci aiutino nei nostri ragionamenti.

 2·3+1 = 7                                                            		numero primo
 2·3·5+1 = 31                                                       		numero primo
 2·3·5·7+1 = 211                                                  		numero primo
 2·3·5·7·11+1 = 2311                                           		numero primo  
 2·3·5·7·11·13+1 = 30031                                   		numero composto:  (30031 = 59·509)                 
 2·3·5·7·11·13·17+1 = 510511                            		numero composto:  (510511 = 19·97·277)        
 2·3·5·7·11·13·17·19+1 = 9699691                     		numero composto:  (9699691 = 347·27953)
 2·3·5·7·11·13·17·19·23+1 = 223092871            		numero composto:  (223092871 = 317·703763)
 2·3·5·7·11·13·17·19·23·29+1 = 6469693231     		numero composto:  (6469693231 = 331·571·34231)
 2·3·5·7·11·13·17·19·23·29·31+1 = 200560490131  	numero primo

Nel caso in cui ci fossimo fermati ai primi 4 risultati la risposta affermativa sarebbe risultata vera, ma, avendo continuato, ci siamo accorti che invece è falsa, perché 30031 non è un numero primo!
Il teorema di Euclide infatti non dice che G è primo e neppure che è multiplo; dimostra invece che:
- se G è primo, esso è diverso da tutti i numeri primi che erroneamente si supponevano presi nella loro totalità;
- se G è multiplo, i suoi fattori primi sono necessariamente tutti diversi dai fattori primi presi per ottenere G. 
In entrambi i casi comunque ci dobbiamo convincere che, oltre a tutti quelli che possiamo pensare di utilizzare per ottenere G, ci saranno sicuramente ancora degli altri numeri primi.

Il concetto di infinito formulato nel teorema di Euclide è quello di infinito potenziale, ma l’argomento è complesso e richiede una trattazione particolareggiata, perché ci sono diversi tipi di infinito. 
La distinzione tra i vari tipi di infinito è spiegata bene dal nostro amico Maurizio Codogno, lo potete trovare all'indirizzo:     http://xmau · com   (digitare il tutto per accedere al sito)
Noi invece continuiamo la trattazione con altri interrogativi:
In che modo si possono riconoscere i numeri primi? 
Esiste un metodo per stabilire se un numero intero è primo o multiplo?
A questi quesiti rispondono:
- il teorema di Wilson  ,  in modo deterministico
- il Piccolo teorema di Fermat  ,  in modo probabilistico  
- il teorema VTL -Wn      (è una mia proposta, sono graditi critiche e commenti)
- il test di Lucas-Lehemer
- il test di Rabin-Miller      
Casella di testo: Pubblicazione web del  17 – 05 – 2008
Teorema di Euclide

Teorema di Euclide