Démonstration de l'infinité du nombre de nombres premiers.

Nous allons procéder par l'absurde:
Supposons que l'on ait trouvé tous les nombres premiers, que leur nombre soit fini.
Appelons n ce nombre.
Nous pouvons donc noter  p₁, p₂, p₃, ... , p_n  ces n premiers (et supposés seuls) nombres premiers.

Démontrons que l'on peut en "fabriquer" un autre:

Soit P = p₁ x p₂ x p₃ x ... x p_n + 1

On admettra le théorème de Gauss (bien plus difficile à démontrer):
"Tout nombre réel s'exprime de façon unique sous la forme d'un produit de facteurs premiers."

Une conséquence de ce théorème: Pour déterminer si un nombre est premier, il suffit de tester la division euclidienne de ce nombre par les nombres premiers qui le précèdent.

La division euclidienne de P par les nombres premiers p₁, p₂, p₃, ... , p_n ne tombe jamais juste (le reste est toujours 1):
Pour tout nombre entier i de 1 à n, on a:

pi = ( p₁ x ... x p_i-1 x p_i+1 x ... x p_n ) x p_i + 1

p_n n'était donc pas le dernier nombre premier puisqu'on a pu en trouver un de plus.

De ce fait on ne peut pas trouver de 'dernier' nombre premier.
Il est toujours possible d'en trouver un de plus.
Le nombre de nombres premiers est donc infini.

C.Q.F.D.

Attention: ce procédé permettrait de trouver un nombre premier de plus si l'on connaissait tous ceux qui précèdent, mais il ne permettrait pas de toute façon de déterminer tous les nombres premiers de façon exhaustive:

Les 4 premiers nombres premiers sont 2, 3, 5, 7.
Si on exprime P:
P = 2 x 3 x 5 x 7 +1 = 210 + 1 = 211
Ce nombre est premier, mais entre 7 et 211, on a laissé passer un grand nombre de nombres premiers (11, 13, 17, 19,...) qui ne peuvent s'exprimer sous la forme:
p₁ x p₂ x p₃ x ... x p_n + 1.

Par ailleurs, nous n'avons pas démontré que ce procédé permet d'obtenir de nouveaux nombres premiers car on ne trouve jamais tous les nombres premiers qui précèdent celui que l'on calcule.

Le procédé est assez vite invalidé par un contre-exemple:

2, 3, 5, 7, 11, 13 sont les 6 premiers nombres premiers.

Appliquons le procédé: 2 x 3 x 5 x 7 x 11 x 13 + 1 = 30 031

Mais 30 031 n'est pas un nombre premier:

30 031 = 59 x 509

59 et 509 sont deux des nombreux nombres premiers qui n'on pas été pris en compte dans le calcul de 30 031. Nous n'étions donc pas dans les conditions de départ du raisonnement par l'absurde.