Définition : Un nombre entier naturel p est premier s'il n'admet que deux diviseurs distincts. (donc 1 n'est pas un nombre premier.)
Théorème : Le nombre de nombres premiers est infini.
Démonstration par l'absurde :
Soit P = {P1, P2, ..., Pn} l'ensemble complet fini des nombres premiers. Considérons alors le nombre suivant : Q = P1 * P2 * ... * Pn + 1
Supposons que ce nombre Q n'est pas premier : il possède donc au moins un diviseur, noté D. Or D ne peut pas appartenir à l'ensemble P, car la division euclidienne de Q par n'importe quel nombre de l'ensemble P crée un reste de 1.
Conclusion : L'hypothèse de départ est fausse, et le nombre Q est toujours premier. Par récurrence on prouve que le nombre de nombres premiers est infini.