¿Cómo se demuestra que existen infinitos números primos?

Euclides lo demostró así:

Sean A, B, Γ los números primos propuestos.

Digo que hay más números primos que A, B, Γ.

Pues tómese el número menor medido por A, B, Γ y sea ΔE y añádase a ΔE la unidad EZ. Entonces EZ o es primo o no lo es. Sea primo en primer lugar; entonces han sido hallados los números primos A, B, Γ, EZ, (que son) más que A, B, Γ.

—————————- A —————H

———————————- B

—————————————— Γ

Δ ———————————————E——- Z

Pero ahora no sea primo EZ; entonces es medido por algún número primo; sea medido por el número primo H.

Todo número compuesto es medido por algún número primo; sea medido por el número primo H.

[Sea A un número compuesto. ———————————A

Digo que A es medido por algún número primo. ——————B

Pues como A es compuesto, algún número lo medirá. ———Γ

Mídalo y sea B. Ahora bien, si B es primo se habría dado lo propuesto. Pero si es compuesto, algún número lo medirá. Mídalo y sea Γ. Pues bien, como Γ mide a B y B mide a A, entonces Γ mide también a A. Y si Γ es primo, se habría dado lo propuesto. Pero si es compuesto, algún número lo medirá. Siguiendo así la investigación se hallará un número primo, que lo medirá. Pues, si no se halla, una serie infinita de números medirán el número A, cada uno de los cuales es menor que otro; lo cual es imposible en el caso de los números. Luego se hallará un número primo que medirá al anterior a él mismo, que también medirá a A.

Por consiguiente, todo número compuesto es medido por algún número primo.

Libro VII, Proposición 31]

Digo que H no es el mismo que ninguno de los números A, B, Γ. Pues, si fuera posible, séalo. Pero A, B, Γ miden a ΔE; entonces H medirá también a ΔE. Pero mide asimismo a EZ; y H, siendo un número, medirá también a la unidad restante ΔE; lo cual es absurdo. Luego H no es el mismo que ninguno de los números A, B, Γ. Y se ha supuesto que es primo. Por consiguiente, han sido hallados más números primos que la cantidad propuesta de los números A, B, Γ. [Libro noveno, proposición 20 de Los Elementos de Euclides]

Redactada de otra manera, más del siglo XXI, esta hermosa demostración de Euclides podemos presentarla de esta otra forma:

Supongamos que P es el mayor número primo.

Pensemos en el número N = (2 x 3 x 5 x … x P) + 1.

O N es primo o no lo es.

Si N es primo, hemos generado un primo mayor que P, lo que contradice nuestra propia suposición. Si N no es primo tiene que ser divisible por algún primo, por ejemplo 3, 5 … P.

Esto significa que p divide a N – (2 x 3 x 5 x … x P). Pero este número es igual a 1 y por tanto p divide a 1. Esto no puede ser ya que todos los primos son mayores que 1. Por lo tanto, sea cual sea la naturaleza de N, llegamos a una contradicción. Nuestra suposición original de que hay un máximo número primo P es errónea.

Conclusión: el número de primos es ilimitado.

Aunque los primos se extienden hasta el infinito, este hecho no ha impedido que haya gente empeñada en encontrar el mayor número primo que se conozca.

Uno que ostentó el récord fue el descomunal primo de Mersenne 2^24036583 – 1, que es aproximadamente 7.236 x 10^12 (unos 7 millones de millones).