Il existe une infinité de nombres premiers, démonstration
Les nombres premiers
Un nombre premier est un entier supérieur à 1 dont les seuls diviseurs sont 1 et et lui-même.
Ainsi, les nombres suivants sont premiers:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, ...
En d'autres termes, un nombre \( n \) n'est pas premier si et seulement s'il possède (au moins) un diviseur \( d \) tel que \( 1 \lt d \lt n \). Ainsi les nombres suivants ne sont pas premiers:
\[ \begin{array}{rcl} 4&=& 2 \times 2 \\ 6&=& 2 \times 3 \\ 8&=& 2 \times 2 \times 2 \\ 9&=& 3 \times 3 \\ 10&=& 2 \times 5 \\ 12&=& 2 \times 2 \times 3 \end{array} \]Démonstration de ≪ Il existe une infinité de nombres premiers ≫
Supposons par l'absurde qu'il n'existe qu'un nombre fini de nombres premiers \( \{ p_1, p_2, ..., p_n \} \).
Formons le produit de ces nombres augmenté de 1, c'est-à-dire \( p = p_1 p_2 ... p_n +1 \).
Le reste de la division de \( p \) par \( p_1 \) est \( 1 \);
le reste de la division de \( p \) par \( p_2 \) est \( 1 \);
... ;
le reste de la division de \( p \) par \( p_n \) est \( 1 \).
Puisque \( p \) n'est divisible par aucun nombre premier, \( p \) est premier, ce qui contredit l'hypothèse que la liste \( \{ p_1, p_2, ..., p_n \} \) contient tous les nombres premiers.
C'est donc le contraire qui est vrai, à savoir ≪ Il existe une infinité de nombres premiers ≫.
Mise en garde
La proposition suivante est fausse: ≪ Considérons la liste des \( n \) premiers nombres premiers \( \{ p_1, p_2, ..., p_n \} \). Alors le produit de ces nombres augmenté de 1, c'est-à-dire \( p = p_1 p_2 ... p_n +1 \), est un nombre premier. ≫
Voici un contre-exemple. Pour \( n = 6 \), la liste des nombres premiers est \( \{ 2, 3, 5, 7, 11, 13 \} \) et le nombre
\[ \begin{array}{rcl} p&=&2 \times 3 \times 5 \times 7 \times 11 \times 13 + 1 \\ &=&30031 \\ &=&59 \times 509 \end{array} \]n'est pas premier !