Prueba de Euclides de que existen infinitos números primos:

Euclides descubrió que existe una infinidad de números primos hace más de 2.200 años.

Es una prueba clásica y muy bella:

Primero Euclides asumió que la lista de números primos es finita y llegó a una contradicción, luego la lista debe ser infinita.

Imaginemos una lista que contiene (todos) los primos: P₁, P₂, P₃, ... P_n.  Entonces se puede generar otro número Q (mucho mayor) tal que:

Q=(P₁ x P₂ x P₃ x ... x P_n) + 1

Este nuevo número Q puede ser primo o no.  Si es primo, ya tenemos un nuevo primo que no pertenece a la lista original, y por tanto esa lista no era completa. En el caso de que Q no sea primo, forzosamente tendrá que ser divisible por algún número primo que no puede ser uno de los de la lista, ya que al dividir Q por cualquiera de los primos de la lista siempre obtendremos 1 como resto.  Por lo tanto, tiene que existir otro primo P_n+i

En cualquiera de los dos casos hemos encontrado un número primo que NO estaba en la lista original.  Ahora podemos añadir este nuevo primo a la lista y repetir el proceso un infinito número de veces.  Siempre encontraremos un primo que no está en la lista.

El número de primos es infinito.