Teorema dell'infinità dei numeri primi

Il teorema dell'infinità dei numeri primi afferma che, per quanto grande si scelga un numero naturale n, esiste sempre un numero primo maggiore di n.

È stato dimostrato per la prima volta da Euclide nei suoi Elementi (libro IX, proposizione 20), ma ne sono state trovate circa altre cinquanta dimostrazioni, che usano una gran varietà di tecniche diverse: ad esempio Eulero lo ricavò dalla divergenza della serie armonica e dalla possibilità di scrivere ogni numero come prodotto di numeri primi; Christian Goldbach usò i numeri di Fermat, mentre Harry Furstenberg ideò una dimostrazione che sfrutta i metodi della topologia.^[1]

Alcune di queste dimostrazioni (quella di Euclide, quella di Goldbach e un'altra che usa i numeri di Mersenne) si basano su una strategia simile, ovvero dimostrare che esiste una successione infinita di numeri che sono a due a due coprimi, da cui segue necessariamente l'infinità dei numeri primi.

Dimostrazioni

Dimostrazione di Euclide

La dimostrazione, molto semplice in termini moderni, è esposta negli Elementi di Euclide e può a buon diritto essere considerata la prima dimostrazione di un teorema di teoria dei numeri.

La dimostrazione avviene per assurdo, con il seguente ragionamento:

Si supponga che i numeri primi non siano infiniti ma solo ${\textstyle P=\{2,3,\dots ,p_{n}\}}$ ; $p_{n}$ sarebbe allora il più grande dei numeri primi. Sia ${\textstyle a\in \mathbb {N} }$ il prodotto degli n numeri primi, $a+1$ non è divisibile per 2, perché lo è ${\textstyle a}$ e quindi ha resto 1. Non è divisibile per 3, per lo stesso motivo. In generale, detto $p_{i}$ l'i-esimo numero primo, la divisione ${\textstyle {\frac {a+1}{p_{i}}}}$ ha sempre resto 1: assumendo ${\textstyle (a+1)}$ come dividendo, $p_{i}$ come divisore, ${\textstyle q\in \mathbb {N} }$ come quoziente della divisione, è sufficiente dimostrare che ${\textstyle (a+1)-(q\cdot p_{i})=1}$ , cioè che $a=(q\cdot p_{i})$ assunto come ipotesi.

A questo punto, per il teorema fondamentale dell'aritmetica, sono possibili due casi:

$a+1$ è primo, e ovviamente essendo maggiore di $p_{n}$ quest'ultimo non è il più grande dei numeri primi;
$a+1$ , non essendo primo, è il prodotto di numeri primi che non possono figurare tra gli $n$ ipotizzati (in quanto, come abbiamo appena mostrato, nessun $p_{i}$ divide ${\textstyle (a+1)}$ ) e che devono quindi essere maggiori di $p_{n}$ ; anche in questo caso segue che $p_{n}$ non è il più grande dei numeri primi.

In entrambi i casi si perviene alla conclusione che non può non esistere un numero primo più grande di $p_{n}$ , dunque i numeri primi sono infiniti.

In realtà solo pochi dei numeri $a+1$ (detti numeri di Euclide) così trovati sono primi, perché il divario tra $p_{n}$ e $a$ cresce circa come il fattoriale, e quindi c'è sempre più possibilità che $a+1$ abbia un divisore tra $p_{n}$ e ${\sqrt {a+1}}$ .

Una conseguenza immediata di questa dimostrazione è la seguente disuguaglianza:

p_{n+1}<p_{1}p_{2}\cdots p_{n}

La disuguaglianza di Bonse e le sue generalizzazioni forniscono risultati più forti.

Corollario

Un interessante corollario, che è evidente rigirando la dimostrazione, è che si può sempre costruire un intervallo, lungo a piacere, di numeri consecutivi che non siano numeri primi. Infatti se vogliamo avere un intervallo di 99 numeri consecutivi senza primi, è possibile costruirlo prendendo, ad esempio, il fattoriale di 100, ossia ${\textstyle 100!}$ ≈ 9,33262154×10¹⁵⁷. Questo numero, enorme, è divisibile per tutti i numeri tra $2$ e $100$ , per costruzione. Se poniamo che $k$ sia uno di questi numeri tra 2 e 100, ${\textstyle 100!}$ e $100!+k$ sono entrambi divisibili per $k$ . Abbiamo quindi 99 numeri consecutivi senza primi, da $100!+2$ a $100!+100$ . Si noti che, data la lunghezza dell'intervallo, gli estremi dell'intervallo costruito in questo modo non sono i minimi possibili.

Dimostrazione di Eulero

La dimostrazione di Eulero parte dal fatto che la serie armonica:

S=1+{\frac {1}{2}}+{\frac {1}{3}}+\dots +{\frac {1}{n}}+\dots

è divergente.

Eulero osserva che la serie armonica può vedersi come il prodotto di queste serie geometriche, una per ogni numero primo:

$S_{2}=1+{\frac {1}{2}}+{\frac {1}{4}}+{\frac {1}{8}}+\dots +{\frac {1}{2^{n}}}+\dots =2$

$S_{3}=1+{\frac {1}{3}}+{\frac {1}{9}}+{\frac {1}{27}}+\dots +{\frac {1}{3^{n}}}+\dots ={\frac {3}{2}}$

$S_{5}=1+{\frac {1}{5}}+{\frac {1}{25}}+{\frac {1}{125}}+\dots +{\frac {1}{5^{n}}}+\dots ={\frac {5}{4}}$

...

Le serie si calcolano facilmente ricordando che $S_{n}={\frac {1}{1-{\frac {1}{n}}}}$ (vedi serie geometrica).

Infatti la serie armonica è la somma dei reciproci di tutti i numeri naturali e ogni numero naturale può rappresentarsi come il prodotto dei suoi fattori primi. Ci si convince allora facilmente che ogni elemento della serie armonica corrisponde a un possibile prodotto di elementi presi uno ad uno dalle serie suddette. Per esempio per l'elemento $1/15$ :

${\frac {1}{15}}=1\times {\frac {1}{3}}\times {\frac {1}{5}}\times 1\times 1\times \dots$

D'altra parte le serie $S_{2},S_{3},S_{5},S_{7},\ldots$ sono tutte finite. Ma allora se i numeri primi fossero finiti, il loro prodotto sarebbe anch'esso finito, mentre sappiamo che la serie armonica diverge.

Ne segue che i numeri primi devono essere infiniti.

Dimostrazione topologica

Per ogni coppia di interi $a$ e $b,$ con $a>0,$ si ponga $a\mathbb {Z} +b:=\{an+b:n\in \mathbb {Z} \}$ . La famiglia $\{a\mathbb {Z} +b:a,b\in \mathbb {Z} ,a>0\}$ è una base di una topologia di $\mathbb {Z}$ , detta topologia degli interi equispaziati: la prova dell'infinitudine dei numeri primi si cela dietro le sue proprietà topologiche. Gli aperti di tale topologia godono di tre proprietà:

ogni aperto $a\mathbb {Z} +b$ è chiuso;
ogni aperto non vuoto ha infiniti elementi;
$\mathbb {Z} \backslash \{-1,1\}=\bigcup _{p\in \mathbb {P} }p\mathbb {Z}$ , ove $\mathbb {P}$ è l'insieme dei numeri primi positivi.