Come dimostrare l'infinità dei numeri primi
Introduzione
Euclide fu il primo a dimostrare l?infinità dei numeri per la prima volta nella storia. Egli, infatti, dimostrò che non esiste il numero più grande di tutti, perché ne esisterà sempre uno più grande di un altro. Successivamente a questa scoperta, nacque la definizione di numero primo: In matematica un numero primo è un numero naturale che sia divisibile esclusivamente per 1 e per sé stesso. L'obbiettivo di questa guida è quello di dimostrare l'infinità dei numeri primi, ovverosia il fatto che pur crescendo di grandezza, esistono sempre numeri che non possono essere generati come prodotti fra interi. L'utilità della conoscenza di questa proprietà dei numeri interi, in realtà ha grande utilità nella realizzazione di chiavi cifrate ad elevata sicurezza e nello sviluppo di algoritmi per la codifica della protezione. Vediamo quindi come dimostrare l'infinità dei numeri primi.
Dimostrazione euclidea
Il procedimento di Euclide per dimostrare quest'infinità comincia con un ragionamento per assurdo: se i numeri primi non sono infiniti, sono finiti. Significherebbe quindi che da un certo punto in poi, ogni numero sarebbe necessariamente generato da un prodotto di due interi. Quindi avrà senso la seguente scrittura: P=[2,3...... Pn] che è la lista completa degli n numeri primi. In questo caso, indichiamo con P l?insieme dei numeri primi, mentre con pn il numero massimo dei numeri primi. È importante ricordare che in aritmetica, il " Massimo" è il più grande numero di una serie. Il ragionamento per assurdo comincia considerando proprio che pn è il massimo dei numeri primi. Esistono anche altri teoremi che dimostrano l'infinità dei numeri primi, basati sul principio topologico degli interi equispaziati, introdotta da Fürstenberg
ma questa dimostrazione richiede una conoscenza approfondita delle serie matematiche e sicuramente non è la più semplice.
Principio del resto
Il principio del resto è piuttosto semplice, ed apparentemente anche poco utile, ma è uno strumento utile. Se addizioniamo 1 ad un numero e lo dividiamo per un numero ottenuto per i fattoriali del primo, il risultato della divisione sarà sempre 1. Il seguente esempio dimostrerà questa tesi:12 = 4 x 3; 12 + 1 = 13; 13/4= 3 con resto di 1; 13/3= 4 con resto di 1; Tenete in mente questa brevissima dimostrazione, perché essa servirà per il passaggio successivo. Lo strumento base del principio del resto è la base per la generazione di numeri probabilmente primi, perché purtroppo per noi, nonostante tutto l'impegno profuso nei secoli dai matematici, non siamo ancora arrivati ad avere in mano un algoritmo per generare i numeri primi.
Dimostrazione dell'infinità
Riferendoci alla tesi precedente, diremo che pn è il più grande tra i numeri primi. Questo però sappiamo che non è vero, dato che esisterà sicuramente un numero P più grande di pn. Quindi, si procede in questo modo: P>pn. Questa considerazione è la stessa che si fa per dimostrare l'infinità dei numeri. Se addizioniamo 1 a P avremo ancora: P + 1>pn Per il teorema fondamentale dell'aritmetica che afferma che un numero o è primo o si ricava dal prodotto di numeri primi, esistono due sole possibilità: P+1 è PRIMO, P+1 è COMPOSTO. Se P è dispari, P+1 è pari e se non è 2 è ovviamente un numero composto, per definizione. Nel primo caso, P+1 è primo, abbiamo ottenuto una contraddizione: infatti P+1 è maggiore di pn, il che va contro l'ipotesi per cui pn è il maggiore dei numeri naturali, e avendo noi generalizzato con l'utilizzo di un'incognita, esisterà sempre un numero primo maggiore di pn. Allora l'insieme di P è infinito. Nel secondo caso, p+1 è composto e contraddice il discorso che abbiamo dimostrato precedentemente. Infatti per costruzione P+1 non è divisibile né da pn né da un fattoriale, perché come risultato darà sempre 1 in base a questi fattori. Un numero composto è divisibile per i fattoriali dato che è composto da essi, come possiamo ricavare dal teorema fondamentale dell?aritmetica. Detto ciò, noterete che il secondo caso non è dimostrabile perché contraddittorio, mentre il primo caso dimostra perfettamente che P è infinito e potrà sempre essere più grande di pn.