Euclides pudo haber sido el primero en dar una prueba de que hay infinitos números primos. Incluso después de 2000 años se presenta como un excelente modelo de razonamiento. A continuación, seguimos la declaración de Ribenboim sobre la prueba de Euclides…
- Teorema: Hay infinitos primos.
- Prueba:
- Supongamos que p1=2 < p2 = 3 < … < pr son todos los números primos.
- Sea P = p1p2…pr+1 y sea p una división prima de P; entonces p no puede ser cualquiera de p1p2…pr, de lo contrario, p dividiría la diferencia P-p1p2…pr=1, lo cual es imposible.
- Entonces este primo p es otro primo, y p1p2…pr no serían todos los primos.
Es un error común pensar que esta prueba dice que el producto p1p2…pr +1 es primo. La prueba en realidad solo utiliza el hecho de que existe una división prima que divide este producto (ver números primos primorial).
La prueba anterior es realmente bastante diferente de lo que escribió Euclides. Ahora entendemos los enteros como objetos abstractos, pero los antiguos griegos los entendieron como recuentos de unidades (la unidad, uno, no era un número, dos era el primero) y los representaban con longitudes de segmentos de línea (múltiplos de un segmento de línea unitaria). Donde hablamos de divisibilidad, Euclides escribió sobre «medir«, viendo un número (longitud) x como midiendo (dividiendo) otra longitud y si algún número entero de segmentos de longitud x hace una longitud total igual a y.
Los antiguos griegos tampoco tenían nuestra noción moderna de infinito. Los escolares ahora entienden fácilmente las líneas como infinitas, pero los antiguos volvieron a ser más concretos (en este sentido). Por ejemplo, vieron las líneas como segmentos que podrían extenderse indefinidamente (no algo infinito de lo que vemos solo una parte). Por esta razón, Euclides no pudo haber escrito «hay infinitos números primos«, sino que escribió que «los números primos son más que cualquier cantidad asignada de números primos«. Euclides (~325 – 265 a.C)
Finalmente, Euclides algunas veces escribió sus «pruebas» en un estilo que hoy sería inaceptable, dando un ejemplo en lugar de manejar el caso general. Estaba claro que entendía el caso general, simplemente no tenía la notación para expresarlo. Su prueba de este teorema es uno de esos casos.
A continuación hay una prueba más cercana a la que escribió Euclides, pero que sigue usando nuestros conceptos modernos de números y pruebas. Vea las páginas de David Joyce para una traducción al inglés de la prueba real de Euclides .
Teorema real de Euclides
- Teorema: Hay más primos que los encontrados en cualquier lista finita de primos.
- Prueba: Llame a los primos en nuestra lista finita p1, p2, … ,pr. Sea P un múltiplo común de estos primos más uno (por ejemplo, P = p1p2…pr+1). Ahora P es primo o no lo es.
- Si es primo, entonces P es un primo que no estaba en nuestra lista.
- Si P no es primo, entonces es divisible por algún primo, llámelo p. Aviso de que p no puede ser cualquiera de p1, p2, … ,pr, de lo contrario, p dividiría 1, lo cual es imposible. Entonces este número primo p es un primo que no estaba en nuestra lista original. De cualquier manera, la lista original estaba incompleta.
Tenga en cuenta que lo que se encuentra en esta prueba es otro primo, uno que no está en el conjunto inicial dado. No hay restricción de tamaño en este nuevo primo, puede ser incluso más pequeño que algunos de los del conjunto inicial. Por ejemplo, si comenzamos con el conjunto:
{2, 3, 7, 13, 43, 139, 3263443},entonces la opción más pequeña de P es el producto de estos siete primos más 1, entonces P = 10650056950807 ó 547 x 607 x 1033 x 31051. El nuevo primo encontrado sería 547, 607, 1033 o 31051, todos los cuales son más pequeños que el último primo en el conjunto original.