Cómo demostrar que hay infinitos números primos

La más fácil es una prueba por contradicción:

  1. Supongamos que tenemos una lista finita de cada primo individual (que sería posible allí donde no haya un número infinito de primos).
  2. Usando esta lista, podemos construir un nuevo número p que no está en la lista al multiplicar todos los elementos de la lista (así que cada número primo) y agregar uno.
  3. Este número p es relativamente primo para cada número primo, por lo tanto, es un primo nuevo. * También podemos demostrar que no está ya en la lista porque debe ser mayor que la lista, ya que se construyó como el producto de todos los elementos. en la lista.
  4. Tenemos un primo p que no está en nuestra lista de todos los primos, por lo tanto, ninguna lista finita de primos puede contener todos los primos.
  5. Por lo tanto, hay primos infinitos. QED

* Si no es primo, entonces algún primo en la lista debe dividirlo, lo que significa que el primo debe dividir tanto el producto de la lista como el producto de la lista + 1, por lo que debe dividir uno, lo cual es imposible. Por lo tanto, ningún primo en la lista lo divide.

Euclides hizo esto hace mucho tiempo. Es una prueba por contradicción, pero se puede afirmar que es una prueba constructiva.

Deje p ser cualquier primo. (Tenga en cuenta que 1 no es primo por definición, por lo que p> 1.)

Luego defina Q como el producto de p y todos los primos menores que él.

Entonces Q + 1> Q, y Q + 1> p.

Como cualquier primo menor que Q ya divide a Q, no puede dividir Q + 1, por lo que Q + 1, que es mayor que p, no puede ser compuesto, por lo tanto es primo. Ahora repita, sustituyendo Q + 1 por p, y tiene una secuencia estrictamente creciente de primos distintos sin límite, por lo que la secuencia (de primos) es infinita.

Editado

Solo puede conformarse con la prueba de Euclides y todas las reformulaciones de la misma. Sin embargo, aquí hay uno que no leerá en ningún libro de texto (y es un bosquejo de cómo sería una prueba):

Cardinalidad determinísticamente desigual

No puede haber una función biyectiva entre el conjunto de números impares y el conjunto de soluciones impares para ecuaciones lineales.

Esto es cierto para cada conjunto de enteros positivos iguales o mayores que el intervalo entre dos cuadrados (y por extensión hasta el infinito).

Considere ecuaciones lineales con pendientes impares para las cuales [matemática] m> \ sqrt {y} [/ matemática] y [matemática] b = 2m [/ matemática]. Algunas de las soluciones para impares [matemáticas] m [/ matemáticas] deben ser pares [matemáticas] y [/ matemáticas] s (66, 68, 72, 74, 76, 78). De esto se deduce que el conjunto de soluciones impares para [math] y [/ math] (65, 69, 75, 77) no puede tener el mismo número de elementos, o cardinalidad, que el conjunto de números que son impares.

En este caso, los elementos restantes del conjunto (67, 71, 73, 79) deben ser primos.

Si es cierto para un conjunto de números, un intervalo cuadrado perfecto o mayor, debería ser cierto para el conjunto de todos los números naturales. (Ahora puede haber notado que al elegir el intervalo entre [matemática] x ^ 2 [/ matemática] y [matemáticas] (x + 1) ^ 2 [/ matemáticas], también estoy sugiriendo que una conjetura famosa debe ser cierta).

Deje que [math] \ mathbb P [/ math] denote el conjunto de números primos en [math] \ mathbb N [/ math].

Si [math] \ mathbb P [/ math] es finito, entonces

[matemáticas] \ displaystyle 0 \ lt \ prod_ {p \ in \ mathbb P} \ sin \ left (\ frac {\ pi} {p} \ right) = \ prod_ {p \ in \ mathbb P} \ sin \ left (\ frac {\ pi} {p} \ left (1 + 2 \ displaystyle \ prod_ {p ‘\ in \ mathbb P} p’ \ right) \ right) = 0 [/ math]

QED

No, no inventé la prueba (ha), se puede encontrar aquí: Biblioteca de Fermat | Una prueba de una línea de la infinitud de los primos

Prueba de Euclides:

Suponga que hay muchos primos finitos, y los enumeramos en orden ascendente como [matemática] \ left \ {p_1, p_2, p_3, \ cdots, p_n \ right \} [/ math]. Ahora construimos un nuevo número

[matemáticas] p = p_1 \ veces p_2 \ veces p_3 \ cdots p_n + 1 \ tag * {} [/ matemáticas]

Podemos ver que este número no es divisible por ninguno de los números primos [math] p_1, p_2, \ cdots p_n [/ math], eso está en nuestra lista, porque dividiendo [math] p [/ math] por [math] p_1 , p_2 [/ math] o combinaciones de sus productos siempre darán como resultado un resto de [math] 1 [/ math]. Si [math] p [/ math] hubiera sido un número compuesto entonces, al menos uno de nuestros primos enumerados habría podido dividirlo.

Esto significa que debe haber algunos primos [matemática] p_ {n + 1} [/ matemática] [matemática]> [/ matemática] [matemática] p_n [/ matemática], de modo que [matemática] p_ {n + 1} \ mid p [/ math] que significa que no está incluido en nuestra lista de primos. Esto es una contradicción.

Por lo tanto, hay infinitos números primos.

Los números primos son enteros sin divisores enteros exactos excepto 1 y ellos mismos.

  1. Para probar: “No hay mayor número primo” por contradicción.
  2. Suponga: hay un número primo más grande, llámelo p .
  3. Considere el número N que es uno mayor que el producto de todos los números primos menores o iguales a p . N = 2 * 3 * 5 * 7 * 11… * p + 1 . ¿Es primo?
  4. N es al menos tan grande como p + 1 y, por lo tanto, es más grande que p y, por lo tanto, en el Paso 2, no puede ser primo.
  5. Por otro lado, N no tiene factores primos entre 1 yp porque todos dejarían un resto de 1 . No tiene factores primos mayores que p porque el Paso 2 dice que no hay primos mayores que p . Por lo tanto, N no tiene factores primos y, por lo tanto, debe ser primo (ver la nota a continuación).
  6. Hemos llegado a una contradicción ( N no es primo en el Paso 4 y N es primo en el Paso 5) y, por lo tanto, nuestra suposición original de que hay un primo más grande debe ser falsa. Prueba por contradicción

Hay muchas pruebas para hacer esto. Vienen en todas las formas y tamaños y en todas las áreas de las matemáticas. Muchos de ellos son limpios y merecen una lectura completa, pero voy a elegir el más simple que la mayoría de la gente aprende primero.

Supongamos por un momento que hay un número finito de números primos, y los encontramos todos. Entonces, colóquelos en una lista grande y tome el producto de esa lista. Este producto es un número (grande) que es divisible por cada primo en la lista. Agregue uno al producto y obtendrá un número (grande) que no puede ser divisible por ningún primo en la lista. Pero el número debe tener algún factor primo, por lo que debe tener un factor primo que no esté en la lista. Pero, afirmamos que cada primo estaba en nuestra lista. Esta contradicción implica que es imposible crear una lista finita de todos los números primos, porque si pudieras, siempre podrías encontrar otro número primo que no esté en la lista.

Querías un ejemplo *, así que aquí tienes.

Suponga que encontró “todos” los números primos [math] \ {2,3,5,7,11 \} [/ math]. Tome el producto de su lista para encontrar [math] 2 \ cdot 3 \ cdot 5 \ cdot 7 \ cdot 11 = 2310 [/ math]. Claramente, 2310 es divisible por cada primo en la lista. Agregue uno y tenga en cuenta que 2311 no puede dividir ninguna prima en la lista. Por lo tanto, 2311 debe tener un factor primo que no esté en su lista original (efectivamente, 2311 es primo).

Entonces, ahora sabe que en realidad no tenía todos los números primos, y actualiza su lista a la nueva lista “completa” [matemáticas] \ {2,3,5,7,11,2311 \} [/ matemáticas]. Sin embargo, puede hacer lo mismo una y otra vez para encontrar más y más nuevos números primos. No importa cuán grande sea la lista, siempre puede encontrar más con el mismo proceso. Por lo tanto, la lista nunca puede ser “completa”. Siempre hay otro prime por ahí. Por lo tanto, hay un número infinito de primos.

* Otra pregunta quería un ejemplo, y esa pregunta se fusionó con esta.

Puedes probarlo por contradicción.

Suponga que hay un número finito de números primos, [matemática] p_1, p_2, …, p_k [/ matemática].

Deje que [math] m [/ math] sea el producto de todos los números primos, de modo que [math] m = p_1 p_2 … p_k [/ math].

Sea [math] n = m + 1 [/ math].

Como [math] n> 1 [/ math], [math] n [/ math] debe ser divisible por algún número primo [math] p_i [/ ​​math], en [math] p_1, p_2,…, p_k [/ math ]

Pero como [math] p_i [/ ​​math] está en [math] p_1, p_2, …, p_k, [/ math] [math] p_i [/ ​​math] también divide [math] m [/ math].

Esto implica que [math] p_i [/ ​​math] divide [math] n – m [/ math]. Pero esto es imposible, porque [matemáticas] n – m = 1 [/ matemáticas]. Por lo tanto, no puede haber muchos primos finitos.

donde el lado izquierdo es igual a la función zeta de Riemann:

y el producto en el lado derecho se extiende sobre todos los números primos p :

Prueba:

Restando el segundo del primero, eliminamos todos los elementos que tienen un factor de 2:

Repitiendo para el próximo término:

Restando de nuevo obtenemos:

donde todos los elementos que tienen un factor de 3 o 2 (o ambos) se eliminan.
Se puede ver que el lado derecho está siendo tamizado. Repitiendo infinitamente obtenemos:

Dividiendo ambos lados por todo menos las ζ ( s ) que obtenemos:

Esto se puede escribir de manera más concisa como un producto infinito sobre todos los primos p :

Prueba de la fórmula del producto Euler para la función zeta de Riemann – Wikipedia

La prueba estándar se debe a Euclides y se basa en la observación de que si [math] n | k [/ math] (es decir, n divide k), entonces n no divide k + 1, a menos que n sea uno y, en particular, no sea primo .

Sabemos que el conjunto de todos los números primos no está vacío, ya que podemos encontrar un elemento, digamos 2.

Supongamos, por contradicción, que el conjunto de todos los primos S es finito. Entonces, si [math] k = \ Pi_ {p \ in S} p [/ math] es el producto de todos estos números primos, entonces no hay [math] p \ in S [/ math] que divida k + 1.

Claramente, sin embargo, debe haber un primer divisor k + 1 (por el teorema fundamental de la aritmética) y este primo no puede estar contenido en S, por lo tanto S estaba incompleto.

Quizás valga la pena mencionar que la razón por la que este argumento ya no funciona cuando S es infinito (es decir, no es simplemente imposible tener un conjunto completo de primos) es porque no podemos tomar significativamente el producto infinito de todos los primos en el de la manera que podríamos si fuera finito.

Supongamos que hubiera un número finito de primos, podríamos escribirlos como

[matemáticas] p_1 ~ p_2 ~ p_3 ~… ~ p_n [/ matemáticas]

Multipliquemos todos juntos y hagamos un nuevo número, pero también agreguemos uno.

[matemáticas] (p_1 × p_2 × p_3… × p_n) +1 [/ matemáticas]

Esto nos dará un número. Sin embargo, no cualquier número, un número que no divide primos. Debido a este nuevo número, llámelo [math] R [/ math] será igual a [math] 1 ([/ math] mod [math] p) [/ math] para cualquier primo [math] p [/ math]. Pero el teorema fundamental de la aritmética dice que cualquier número compuesto puede escribirse como un producto único de primos. Pero ningún primo divide este número, por lo que no puede ser compuesto. Lo que significa que este nuevo número tiene que ser primo.

XKCD respondió en forma de haiku:
xkcd: prueba de Haiku

Hice una prueba de la infinidad de números primos en Quora hace unos días. Aquí hay un enlace: Una prueba de la infinitud de los números primos por Manny Condas

El siguiente enlace consiste en pruebas de infinitud de números primos por tres métodos diferentes, usando topología, teoría de grupos y usando números de fermat.

Página en cmu.edu

La prueba que generaliza es la prueba de Euler usando su fórmula de producto para la función zeta de Riemann: Prueba de la fórmula del producto de Euler para la función zeta de Riemann

Hay una prueba “constructiva” en la siguiente línea de razonamiento: Dame tu supuesta lista finita de números primos. Los multiplicaré todos juntos, luego agregaré “1” a la suma. Ese nuevo número obviamente no es divisible por ninguno de los primos listados y obviamente no está en esa lista, por lo que es un primo “nuevo, no listado” que su lista finita> no pudo Este argumento es probablemente euclidiano o aristotélico o similar.

Hay una simple prueba de contradicción:

supongamos que solo hay primos finitos.

Luego considere una lista finita arbitraria de primos en orden ascendente [math] pl = \ {[/ math] [math] 2,3,5,7, \ ldots, p \} [/ math] y supongamos que está completo (lo que significa que contiene todos los números primos que hay).

Luego mire [math] q = \ prod \ limits_ {l \ in pl} l + 1 [/ math].

Hay dos posibilidades para [math] q [/ math] o es primo de lo que no está en la lista o es compuesto de lo que debe ser divisible a través de un primo que no está en nuestra lista. La implicación es la misma para ambos casos: hay una prima que no está en nuestra lista. Pero eso es cierto para cualquier lista finita de números primos que podamos encontrar (recuerde que elegimos la lista arbitrariamente), por lo que nuestra suposición inicial de que existe una lista tan finita debe estar equivocada porque llegamos a una contradicción. [matemáticas] \ blacksquare [/ matemáticas]

Hay números infinitos, así que hay números primos infinitos. No tengo un ejemplo (no lo suficientemente inteligente como para crear una fórmula compleja)

Asume que hay un número finito de primos, por lo tanto, debe haber uno mayor. Luego construyes uno más grande. Hecho.

More Interesting

Dado que [matemática] x = 2a ^ 5 = 3b ^ 2 [/ matemática] donde [matemática] a [/ matemática] y [matemática] b [/ matemática] son ​​enteros positivos. ¿Cuál es el menor valor posible de [math] b [/ math]?

Teoría de números: ¿Qué es un módulo?

¿Por qué es tan importante la hipótesis de Riemann?

¿Cómo se muestra que [matemáticas] (2 ^ a-1) (2 ^ b-1) = 2 ^ {2 ^ c} +1 [/ matemáticas] es imposible en enteros no negativos [matemáticas] a, b, [/ matemáticas] y [matemáticas] c [/ matemáticas]?

Un estudiante notó que en una lista de cinco enteros, la media, la mediana y la moda eran enteros consecutivos en orden ascendente. ¿Cuál es el rango más grande?

¿Hay un nombre (o prueba) para esta conjetura: para todos los números naturales N, 1 menos que cualquier potencia de N es un múltiplo de N-1?

¿Cómo podemos excluir números no primos mientras generamos a través de 6n + 1 y 6n-1, donde n> 1? Por ejemplo, para n = 4 6n + 1, da 25 que no es primo, ¿cómo podemos excluirlo?

¿Cuál es el significado del teorema de Friedlander-Iwaniec?

Dado un polinomio secreto con coeficientes enteros posiblemente negativos, y la capacidad de consultar el valor del polinomio en cualquier número entero, ¿qué tan eficientemente se puede calcular el polinomio exacto?

¿Es cierto que para todos los enteros [matemáticas] a, b> 3 [/ matemáticas], el poder [matemáticas] a ^ b> b ^ a \ iff b> a [/ matemáticas]? ¿Hay alguna prueba de esto?

¿Por qué el producto de tres enteros consecutivos es divisible por 6?

Cómo demostrar que si [matemática] a (1) = \ sqrt {2} [/ matemática], [matemática] a (n + 1) = \ sqrt {2 + a (n)} [/ matemática], entonces [ matemática] \ lim_ {n \ rightarrow \ infty} 2 ^ {n + 1} \ sqrt {2-a (n)} = \ pi [/ math]

¿La prueba del último teorema de Fermat supone que la enésima raíz de 2 es irracional?

¿Cuál es el número de elementos distintos en el conjunto [matemáticas] \ {(1+ \ omega + \ omega ^ 2 +… + \ omega ^ n) ^ m: m, n = 1,2,3,… \} [ / math] donde [math] \ omega [/ math] es una raíz cúbica de la unidad?

¿Cuál es el resto cuando [matemática] 9 ^ {101} [/ matemática] se divide por [matemática] 125 [/ matemática]?