Prueba de infinitos números primos

Question

Aquí está la prueba del libro que estoy leyendo que demuestra que hay infinitos primos:

Queremos demostrar que no es el caso que sólo hay finitamente muchos primos. Supongamos que hay un número finito de números primos. Demostraremos que esta suposición conduce a una contradicción. Sea $p_1, p_2,...,p_n$ sean todos los primos que hay. Sea $x = p_1...p_n$ sea su producto y que $y=x+1$ . Entonces $y \in \mathbb{N}$ y $y \neq 1$ por lo que existe un primo $q$ tal que $q \mid y$ . Ahora $q$ debe ser uno de $p_1,...,p_n$ ya que estos son todos los primos que hay. Por lo tanto $q \mid x$ . Desde $q \mid y$ y $q \mid x$ , $q \mid (y-x)$ . Pero $y-x=1$ . Así $q \mid 1$ . Pero como $q$ es primo, $q \geq 2$ . Por lo tanto $q$ no divide 1. Así hemos llegado a una contradicción. Por tanto, nuestra suposición de que sólo hay un número finito de números primos debe ser errónea. Por tanto, debe haber infinitos números primos.

Tengo un par de preguntas/comentarios sobre esta prueba. Utilizaré un ejemplo sencillo para ilustrar mis preguntas:

Supongamos que sólo existen 6 números primos: $2, 3, 5, 7, 11, 13$

Sea $x = p_1p_2p_3p_4p_5p_6=30,030$

Sea $y = x + 1 = 30,030+1 = 30,031$

Preguntas/Comentarios:

1. La prueba afirma que existe un primo $q$ tal que $q \mid y$ y que $q$ debe ser $p_1, p_2, p_3, p_4, p_5,$ o $p_6$ . Sin embargo, ninguno de los 6 primos de la lista, $(2,3,5,7,11,13)$ divide $30,031$ . De hecho, los únicos divisores para $30,031$ son $1, 59, 509$ y $30,031$ . ¿No se rompe entonces la prueba aquí ya que no hay primo $q$ que divide $y$ ?

2. La factorización en primos de $30,031$ es $59 \times 509$ . Estos dos números son factores de $30,031$ y son en realidad los propios primos, ya que sólo son divisibles por sí mismos o por 1. ¿He demostrado que existe $\gt 6$ ¿Primas? En caso afirmativo, ¿qué puedo concluir ahora que lo he demostrado?

3. No entiendo por qué la contradicción $q$ divide $1$ y $q$ no divide $1$ nos llevan a la suposición de que los primos finitos deben ser erróneos. Entiendo cómo llegamos a la contradicción. No entiendo por qué la contradicción nos lleva a la conclusión muestra que son suposición de que sólo hay finitamente muchos primos es incorrecta.

---

Mis disculpas por el largo post. Gracias por cualquier ayuda.

Answer 1

Se trata de un excelente ejemplo de una demostración que tradicionalmente se formula como una demostración por contradicción, pero que se entiende mucho mejor desde un punto de vista constructivo. Desde un punto de vista constructivo, la demostración muestra que dada cualquier lista de primos $p_1, \ldots, p_n$ hay un primo $q$ (cualquier divisor primo de $p_1p_2\ldots p_n + 1$ ) distinta de cada $p_i$ . Por tanto, dado cualquier conjunto finito de primos, podemos encontrar un primo que no esté en ese conjunto.

Answer 2

1. La prueba se rompe en cierto sentido. Se ha llegado a una contradicción, lo que significa que la hipótesis de que hay un número finito de números primos no puede ser cierta.

2. Así que pensabas que tenías 6 primos y encontraste 2 extra. ¿Puedes añadir estos dos a tu lista y obtener todos los números primos? Si repites el proceso con estos 8 números primos, descubrirás que tendrás incluso MÁS números primos si consideras el producto + 1. Puedes seguir y seguir y nunca te quedarás sin primos. Esta es la idea de la prueba. Utiliza la contradicción porque se puede hacer todo en un solo paso y evitar el problema potencial de hacer el proceso infinitas veces.

Answer 3

Supongamos que sólo existen 6 números primos: 2,3,5,7,11,13

Sin embargo, ninguno de los 6 primos enumerados, (2,3,5,7,11,13), divide 30,031.

Entonces ya tenemos una contradicción. Como sólo hay 6 primos (lo suponíamos al principio) y ninguno de ellos divide a 30,031, entonces 30,031 debe ser primo. Sin embargo, 30,031 no es uno de los 6 únicos primos que existen. Así que 30.031 no puede ser primo, y sin embargo debe serlo.

Así que la prueba funciona. De hecho, funciona exactamente igual independientemente del conjunto de números que supongamos que son los únicos primos que existen. Por lo tanto, ningún conjunto finito de números puede incluir todos los números primos que existen. Por lo tanto, hay un número infinito de números primos.

Answer 4

Usted pregunta en #1 si la prueba se rompe. No. Lo que se rompe es la suposición de que no hay más primos. Asumiste que tenias una lista completa de primos. Entonces construiste un número que no es divisible por ninguno de los primos de tu lista. Sólo quedan dos posibilidades: O el número que has construido es primo, o es divisible por un número que no está en tu lista. En cualquier caso, tu lista no está completa, lo que contradice tu suposición inicial.

En pocas palabras, has asumido que tenías una lista completa y al usar esa suposición has demostrado que la lista no estaba completa. Por lo tanto, la suposición debe ser errónea.

La respuesta a #3 es básicamente la misma. Al encontrar una contradicción cuando hiciste una suposición, demostraste que la suposición era incorrecta.

La respuesta a #2 es no, no has demostrado nada al observar que 59 y 509 son primos. Estás intentando demostrar que existe una lista finita de números primos. Si eliges un conjunto particular de números primos como {2, 3, 5, 7, 11, 13} y demuestras que ese conjunto particular no contiene todos los números primos, un escéptico simplemente diría que necesitas añadir más números primos (como 59 y 509) porque tu conjunto no es lo suficientemente grande. La demostración tiene que ser más general, por eso no dice cuántos números primos hay en el conjunto finito. La prueba está escrita para que funcione independientemente del tamaño del conjunto finito.

Answer 5

Punto 1: Es un teorema que cualquier número natural $n>1$ tiene un factor primo. La prueba es fácil: para cualquier número $n>1$ el menor número natural $a>1$ que divide $n$ es primo (si no fuera primo, no sería el más pequeño).

Punto 2: Sí, has demostrado que hay más de seis primos. ¿Y entonces? La prueba por contradicción no supone que sólo haya seis, sino que hay un número finito de ellos.

Punto 3: En realidad, no es una prueba por contradicción. stricto sensu . Se demuestra que cualquier lista finita de primos en incompleta.