Teorema di Euclide sull'infinità dei numeri primi
I numeri primi sono infiniti perché dato un numero primo P qualsiasi esiste sempre un numero primo maggiore.
Per dimostrare che i numeri primi sono infiniti, Euclide costruisce un nuovo numero che non può essere divisibile dai numeri primi esistenti, e da qui deduce l'esistenza di nuovi numeri primi.
La dimostrazione
L'idea principale di Euclide è di considerare l'ipotesi che un numero primo $ P $ sia maggiore di tutti gli altri.
Calcolo il prodotto dei numeri primi fino a P e aggiungo 1 .
$$ n = (2 \times 3 \times 5 \times... \times P)+1 $$
Questo nuovo numero $ n $ non è divisibile per nessuno dei primi fino a P, poiché dà sempre resto 1.
Inoltre $ n $ è sicuramente maggiore di $ P $ perché ho aggiunto 1.
$$ n > P $$
A questo punto ci sono due possibilità:
- Se $ n $ è un numero primo, allora $ P $ non può essere il numero primo più grande.
- Se $ n $ non è primo (è composto) allora deve essere divisibile almeno per un numero primo. Poiché so già che $ n $ non è divisibile per nessuno dei primi fino a $ P $, deduco che debba esistere almeno un altro numero primo $ P' $ maggiore di $ P $, il che contraddice l'ipotesi che P fosse il numero primo più grande
In entrambi i casi ho dimostrato che l'ipotesi iniziale è falsa: $ P $ non è il numero primo maggiore di tutti.
Pertanto, è vero il contrario. Dato un numero primo $ P $ qualsiasi esiste sempre un numero primo maggiore.
Da questo deduco che i numeri primi sono infiniti.
Nota. In alcune versioni della dimostrazione di Euclide si aggiunge 1 mentre in altre si sottrae 1. Il risultato è sempre lo stesso. In entrambi i casi si rompe la divisibilità per tutti i numeri primi fino a $ P $, ottenendo un numero $ n $ che non è divisibile per nessuno di questi.
Un esempio pratico
Considero per ipotesi che il numero 5 sia il numero primo più grande possibile.
Sapendo che i numeri primi minori o uguali a 5 sono: \( 2, 3, 5 \), calcolo il prodotto dei numeri primi fino a 5 e gli aggiungo 1.
$$ n = (2 \times 3 \times 5) + 1 = 30 + 1 = 31 $$
Il numero $ n = 31 $ non è divisibile per nessuno dei numeri primi fino a 5, perché la divisione darà come resto 1.
- 31 non è divisibile per 2, perché 31 diviso 2 è uguale a 15 con resto di 1.
- 31 non è divisibile per 3, perché 31 diviso 3 è uguale a 10 con resto di 1.
- 31 non è divisibile per 5, perché 31 diviso 5 è uguale a 6 con resto di 1.
Dato che 31 non è divisibile per nessuno dei numeri primi fino a 5, posso dedurre che ci sono due situazioni possibili:
- Se $ n = 31 $ è un numero primo, allora $ P=5 $ non è il numero primo maggiore di tutti gli altri primi.
- Se $ n = 31 $ non fosse un numero primo, allora dovrebbe esistere un numero primo che lo divida. Poiché $ n $ non è divisibile per nessuno dei primi fino $ P $, deduco che esista un numero primo $ P'>P$
In entrambi i casi, ho provato che il numero $ P=5 $ non è il numero primo più grande.
Nota. In questo esempio $ n $ è un numero primo. Tuttavia, anche se non lo fosse stato, la dimostrazione avrebbe comunque provato l'esistenza di un numero primo maggiore di $ P $. Ad esempio, con \( P = 13 \), ottengo: $$ n = (2 \times 3 \times 5 \times 7 \times 11 \times 13) + 1 = 30031 $$ Il numero \( n = 30031 \) non è primo, ma è divisibile per il numero primo \( P' = 59 \), che è maggiore di \( P = 13 \). Anche in questo caso, quindi, esiste un numero primo maggiore rispetto a \( P \).
Dimostrazione alternativa
Ho tre numeri primi a,b,c e devo dimostrare l'esistenza di un quarto numero primo.
$$ a,b,c \in P $$
Con questi formo un numero d.
$$ d = abc + 1 $$
Se il numero d è un numero primo ho dimostrato il teorema.
$$ d \in P $$
Se il numero d non è primo, allora esiste un numero primo d' che divide abc.
$$ d \notin P \rightarrow d' | abc $$
In quest'ultimo caso
- Se d' è diverso da a,b,c ho dimostrato il teorema.
$$ d' \ne (a ∧ b ∧ c ) $$ - Se d' è uguale a uno dei numeri primi a,b,c, allora dovrebbe dividere anche la differenza tra abc e abc+1, ossia 1. Tuttavia, questo è assurdo.
$$ d' = ( a ∨ b ∨ c ) \rightarrow \:\: assurdo $$
Pertanto, se il numero d' è primo, è necessariamente diverso dai numeri primi a,b,c.
Ho così dimostrato l'esistenza di un ulteriore numero primo.
Nota. Questo dimostra che la serie dei numeri primi è infinita. Lo stesso teorema può essere generalizzato prendendo n numeri primi dove $$ d=p_1+...+p_n+1 $$ e dimostrando l'esistenza di un ulteriore numero primo pn+1.
