¿Por qué es Euclides prueba de la infinitud de los números primos considerar una prueba?

Question

He expresado Euclides prueba de la infinitud de los números primos en Mathematica:

f[x_] := Product[Prime[n], {n, 1, x}] + 1
TableForm[Table[{f[x], PrimeQ[f[x]]}, {x, 1, 20}]]

Que se traduce en:

$\begin{array}{ll} 3 & \text{True} \\ 7 & \text{True} \\ 31 & \text{True} \\ 211 & \text{True} \\ 2311 & \text{True} \\ 30031 & \text{False} \\ 510511 & \text{False} \\ 9699691 & \text{False} \\ 223092871 & \text{False} \\ 6469693231 & \text{False} \\ 200560490131 & \text{True} \\ 7420738134811 & \text{False} \\ 304250263527211 & \text{False} \\ 13082761331670031 & \text{False} \\ 614889782588491411 & \text{False} \\ 32589158477190044731 & \text{False} \\ 1922760350154212639071 & \text{False} \\ 117288381359406970983271 & \text{False} \\ 7858321551080267055879091 & \text{False} \\ 557940830126698960967415391 & \text{False} \\ \end{array}$

La prueba de fallas para todos esos valores, ¿cómo es considerada una prueba, entonces? Supongo que hay infinitos números primos de acuerdo a la prueba, pero ¿cuál es la garantía de que en algún momento no va a fallar de forma indefinida?

Answer 1

Euclides prueba difiere de lo que muchos matemáticos dicen que es. Él dijo esto:

Tomar cualquier conjunto finito de números primos. (No piensen que es el conjunto de todos los números primos; no realizar una prueba por contradicción; no asuma que se trata de la primera $n$ de los números primos; por ejemplo, podría ser $\{2,7,31\}$.)

Multiplicar y agregar $1$. A continuación, mostrar (y esta parte fue realizada por la contradicción) de que los factores primos del número resultante no están en el conjunto finito con el que comenzó.

Así, cada conjunto finito de números primos puede ser extendido a un mayor conjunto finito de números primos.

Nada en el argumento da ninguna razón para pensar que si se multiplica la primera $n$ primos y agregar $1$, el resultado es primo. Esa es una confusión resultante de la falta de atención a lo que Euclides escribió.

Tuve un documento conjunto con Catherine Woodgold acerca de esto en el Mathematical Intelligencer en otoño de 2009. "Prime La Sencillez"

Un extracto de nuestro papel:

Sólo la premisa de que un conjunto contiene a todos los números primos podría hacer cualquier persona a la conclusión de que si un número no es divisible por ninguno de los números primos en ese conjunto, entonces no es divisible por ninguno de los números primos.

Sólo la afirmación de que $p_1\dots p_n+1$ no es divisible por ninguno de los números primos hace que cualquier persona a la conclusión de que ese número "es, por tanto, en sí prime", la cita no menos de un número teórico de G. H. Hardy [que] en realidad se atribuye a esa conclusión de Euclides! (Euclides declaración "sin Duda [número] es primo o no" [...] muestra claramente que Euclides el razonamiento de no seguir ese camino.)

El error de pensar que $p_1\dots p_n+1$ ha demostrado ser un primo que lo hace más tentador por el hecho obvio de que, lo que supondría el resultado para ser probado.

[ . . . ]

En cualquier prueba por contradicción, una vez que la contradicción es alcanzado, uno puede preguntarse cuál de los siguientes enunciados afirmado que han demostrado a lo largo de la manera que realmente puede ser probado sólo en la forma dada (ya que el argumento a favor de ellos no se basan en la suposición inicial más tarde resultaron ser falsas), que es correcta, pero debe ser probado en alguna otra forma (ya que el argumento a favor de ellos no dependen de la suposición inicial) y cuáles son falsas. Es fácil descuidar la tarea. La consecuente ignorancia de las respuestas a esas preguntas pueden llevar a la confusión: después de todo, cuando uno recuerda la lectura de una prueba de una proposición, podría uno no cree que la propuesta ha sido probado y por lo tanto se conoce para ser verdad? G. H. Hardy probablemente era consciente de que, debido a la conclusión de que $p_1\dots p_n+1$ "es, por tanto, en sí prime" era contingente en una hipótesis más tarde resultaron ser falsas, no podía ser llevado a ser probado. Pero no dijo explícitamente. Parece difícil justificar una similar confianza en que todos sus lectores evitar el error en el que inadvertidamente se les invitó.

Answer 2

No se reclama la $p_1 \cdots p_n + 1$ es el prime; de hecho, como su tabla muestra, a menudo no es un primo. Creo que es seguro asumir que Euclides podría computar también que no siempre prime.

El punto es que no tienen al menos un factor primo, ya que es $> 1$, y este primer factor no puede ser cualquiera de $p_1, \ldots,p_n$.

Answer 3

La idea clave es que no se que Euclides de la secuencia de la $\ f_1 = 2,\,\ \color{#0a0}{f_{n}} = \,\color{#c00}{\bf 1} + f_1\cdots f_{n-1}$ es una secuencia infinita de números primos , sino que más bien es una secuencia infinita de coprimes, es decir,$\,{\rm gcd}(f_k,f_n) = 1\,$, ya que si $\,k<n,\,$, entonces cualquier divisor común de a $\,\color{orange}{f_k},\,\color{#0a0}{f_n}$ debe dividir $\ \color{#c00}{\bf 1} = \color{#0a0}{f_n} - f_1\cdots \color{orange}{f_k}\cdots f_{n-1}.$

Cualquier secuencia infinita $\,f_n > 1 \,$ de coprimes los rendimientos de una secuencia infinita de distintos números primos $\, p_n $ obtenido por la elección de $\,p_n$ a cualquier factor principal de $\,f_n,\,$ por ejemplo, al menos el primer factor.

Comentario $\ $ Un camino más corto para presentar Euclides de la prueba es de notar que recorrer el mapa de la $\, n\mapsto n^2\!+n$ genera enteros con un número ilimitado de factores primos, porque $\,n(n+1)\,$ incluye todos los factores primos $\,n\,$ además de algunos (¡nuevo!) el primer factor de $\,n+1.$

Answer 4

Si usted lee Euclides prueba de sí mismo-es la Proposición 20 en el Libro IX , se verá que él dice explícitamente que el postulado producto de números primos $1$ "o primos o no" [énfasis añadido].

Answer 5

Si $p_k$ fueron el mayor número primo, entonces $p_1 p_2 \ldots p_k + 1$ sería el primer. Dado que ninguno de los valores que se han utilizado para $p_k$ es el más grande de prime, construido número no necesita ser el primer.