PGCD et nombres premiers

il y a 2300 ans, Euclide démontre que l'ensemble des nombres premiers est infini. C'est l'une des premières preuves de l'histoire qui repose sur un raisonnement par l'absurde.

Pour montrer que l'ensemble des nombres premiers est infini, on va prendre un nombre premier \(p\) quelconque et fabriquer un nouveau nombre premier qui lui est supérieur. Cela voudra bien dire qu'il y a une infinité de nombres premiers.

construisons \(q = (2\times 3\times 5\times 7\times \ldots \times p) +1\)

Si \(q\) est premier : alors nous avons construit un nombre premier plus grand que \(p\) ce qui est notre objectif.

Si \(q\) n'est pas premier, il est divisible par un nombre premier \(a\).

Si \(a>p\), alors nous avons construit un nombre premier plus grand que \(p\) ce qui est notre objectif.

Si \(2\leqslant a\leqslant p\), alors a divise \(2\times 3\times 5\times 7\times \ldots \times p\) car il figure dans cette liste de facteurs. Mais il divise aussi \((2\times 3\times 5\times 7\times \ldots \times p)+1\) donc il divise 1.

Cela est impossible car \(a\geqslant 2\). On aboutit donc à une contradiction.

Nous avons donc construit un nombre premier supérieur à \(p\). L'ensemble des nombres premiers est infini.