Che i numeri primi siano infiniti è una delle poche cose sicure che sappiamo su questi numeri.

La dimostrazione più antica risale agli Elementi di Euclide e resta la più semplice, anche se si tratta di una dimostrazione per assurdo.

Una seconda famosa dimostrazione fu trovata da Eulero circa 2000 anni dopo Euclide.

Dimostrazione di Euclide

Supponiamo per assurdo che i numeri primi siano finiti. Allora esisterà un numero N che sarà il più grande dei numeri primi.

Consideriamo allora il prodotto di tutti i numeri primi P = 2.3.5.7.11.13 ... N, e aggiungiamo 1 a questo numero, ottenendo P + 1. Ora ...

• P + 1 non può avere 2 per divisore essendo di 1 maggiore di P che è multiplo di 2.
• P + 1 non può avere 3 per divisore essendo di 1 maggiore di P che è multiplo di 3.
• P + 1 non può avere 5 per divisore essendo di 1 maggiore di P che è multiplo di 5.
• ...
• P + 1 non può avere N per divisore essendo di 1 maggiore di P che è multiplo di N.

In definitiva i casi sono due:

• P + 1 è un numero primo e allora, essendo ovviamente P+1 > N, N non è il più grande dei numeri primi.
• P + 1 non è primo e quindi ha fattori primi maggiori di N e di nuovo N non è il più grande dei numeri primi.

In ogni caso non può esserci un N che sia il più grande dei numeri primi, e quindi i numeri primi sono infiniti.

Esempi

• Sia N = 7 il più grande dei numeri primi. Allora 2.3.5.7 + 1 = 211 che non ha 2,3,5,7 tra i suoi fattori ed è primo; dunque 7 non è il primo più grande.
• Se N = 11 si ha 2.3.5.7.11 + 1 = 2311 che è ancora primo; e 11 non è il primo più grande.
• Se N = 13 si ha 2.3.5.7.11.13 + 1 = 30031 = 59*509 che sono due numeri primi entrambi maggiori di 13. 30031 è il primo caso di P + 1 che non è primo.

Varianti

Si possono pensare diverse varianti di questa dimostrazione; p.es. invece di considerare P + 1 si potrebbe considerare P - 1 con le medesime conclusioni; oppure invece di P si potrebbe prendere il fattoriale N! con la dimostrazione è del tutto simile riguardo al numero N! + 1.

Dimostrazione di Eulero

Eulero considera la serie armonica:

che si dimostra essere divergente (tende a infinito).

e le seguenti serie di potenze dei numeri primi, tutte convergenti in base alle proprietà delle serie di potenze:

$ 1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \dots + {( {\frac{1}{2}})^n} + \dots = \frac{1}{1-\frac{1}{2}} = 2 $

$ 1 + \frac{1}{3} + \frac{1}{9} + \frac{1}{27} + \dots + {( {\frac{1}{3}})^n} + \dots = \frac{1}{1-\frac{1}{3}} = \frac{3}{2} $

$ 1 + \frac{1}{5} + \frac{1}{125} + \frac{1}{125} + \dots + {( {\frac{1}{5}})^n} + \dots = \frac{1}{1-\frac{1}{5}} = \frac{5}{4} $

$ 1 + \frac{1}{p} + \frac{1}{p^2} + \frac{1}{p^3} + \dots + {( {\frac{1}{p}})^n} + \dots = \frac{1}{1-\frac{1}{p}} = \frac{p}{p-1} $

Ora la serie armonica è la somma degli inversi di tutti numeri naturali, ognuno dei quali si scompone in modo unico in un prodotto di potenze di numeri primi. Queste potenze sono tutte presenti ai denominatori delle serie di potenze su riportate. In definitiva Eulero conclude che la serie armonica è uguale al prodotto di tutte le serie di potenze dei numeri primi. Infatti ogni termine della serie armonica è uguale a uno e uno solo tra i possibili prodotti di termini delle serie di potenze e viceversa.

Ma allora se i numeri primi fossero finiti, queste serie sarebbero in numero finito e finito sarebbe anche il loro prodotto, mentre la serie armonica tende a infinito. Se ne conclude nuovamente che i numeri primi devono essere infiniti.

Questa dimostrazione di Eulero ha portato un secolo dopo Riemann a definire la famosa funzione zeta di Riemann e a formulare quella congettura di Riemann che attende ancora una dimostrazione o una confutazione.