Euclides formuló la primera demostración en la proposición 20 del libro IX de su obra Una adaptación común de esta demostración original sigue así:
Se toma un conjunto arbitrario pero finito de números primos p1, p2, ···, pn, y se considera el producto de todos ellos más uno, q=p1p2 ··· pn+1. Este número es obviamente mayor que 1 y distinto de todos los primos pi de la lista. El número q puede ser primo o compuesto. Si es primo tendremos un número primo que no está en el conjunto original. Si, por el contrario, es compuesto, entonces existirá algún factor p que divida a q. Suponiendo que p es alguno de los pi, se deduce entonces que p divide a la diferencia q-p1p2 ··· pn=1, pero ningún número primo divide a 1, es decir, se ha llegado a un absurdo por suponer que p está en el conjunto original. La consecuencia es que el conjunto que se escogió no es exhaustivo, ya que existen números primos que no pertenecen a él, y esto es independiente del conjunto finito que se tome.
Existen numerosas demostraciones parecidas a ésta, que se formulan a continuación:
Reformulación de Kummer
Supóngase que existe una cantidad finita de números primos p1 < n =" p1·p2·p3·...·pr"> 2. El entero N-1, al ser producto de primos, tiene un divisor pi que también es divisor de N; así que pi divide a N - (N-1) = 1. Esto es absurdo, por lo que tiene que haber infinitos números primos.
Demostración de Hermite
Sea n=1, 2, 3, ... y qn el factor primo más pequeño de n! + 1 para cada n. Como qn tiene que ser mayor que n, se deduce que esta sucesión contiene infinitos elementos distintos, y que por tanto existen infinitos números primos.
Demostración de Stieltjes
Supóngase que existe un número finito de números primos. Sea Q el producto de todos los números primos, y sean m y n dos enteros positivos con Q = mn.Se tiene que todo número primo p divide, o bien a m, o bien a n, pero no a ambos, es decir, m y n son primos entre sí. Entonces m+n no puede tener ningún divisor primo, pero como es estrictamente mayor que 1, debe ser un número primo que no divide a Q: contradicción
