Sobre la prueba de Euclides de la infinitud de los primos y los primos generadores

Question

Así que mirando la prueba de Euclides dice 1)tomamos una familia finita de primos (F) 2)multiplicar todos los primos y añadir uno 3)este nuevo número tiene al menos 1 nuevo factor primo

Así que me preguntaba qué tipo de primos se obtiene alimentando recursivamente este proceso en sí mismo.

Como el número que hay que factorizar crece exponencialmente, es difícil obtener muchas pruebas numéricas de lo que ocurre.
He calculado unos cuantos:

[2]-> [2,3]-> [2,3,7]->[2,3,7,43]->[2,3,7,43,13,139]->[2,3,7,43,13,139,3263443] ->[2,3,7,43,13,139,3263443,547,607,1033,31051]-> no puede factorizar 113423713055421844361000443

[5] (x5)-> [5,2,3,31,7,19,37,3343,79,193662529] -> no puede factorizar 234069798025176583891

Obviamente faltan bastantes primos, 5,11,19,etc de la primera lista, pero podrían aparecer más adelante.

Así que mi pregunta es ¿existe una familia finita de primos que genere finalmente todos los primos? Me imagino que esto probablemente no tenga una respuesta fácil, pero cualquier información relacionada con este proceso sería apreciada, o incluso por qué no se puede hacer.

Answer 1

He aquí la razón por la que mantener primos con multiplicidad hace que la respuesta sea "no". Si $p_n$ denota el producto de todos los números que tienes hasta ahora, donde $p_1$ es el producto de los primos con los que empiezas, entonces $p_n = p_1 ... p_{n-1} + 1$ . Pero podemos reescribirlo como $p_n = p_{n-1}(p_{n-1} - 1) + 1 = f(p_{n-1})$ donde $f(x) = x^2 - x + 1$ y es bien sabido que cualquier divisor primo de $f(n)$ para un número entero $n$ debe ser $2, 3$ o congruente con $1 \bmod 3$ es decir, los primos $5, 11, 17, ...$ se nunca aparecen (a menos que dividan $p_1$ para empezar).

(Esquema: si $q | x^2 - x + 1$ entonces $q | x^3 + 1$ Por lo tanto $x$ tiene orden $6 \bmod q$ ou $q = 2, 3$ . Dado que el grupo multiplicativo $\bmod q$ tiene orden $q - 1$ esto es posible si y sólo si $6 | q-1$ .)

Answer 2

Muchos han considerado esta cuestión, y variantes de la misma, en su estudio de la teoría de números. Es una buena pregunta porque es fácil de plantear y es divertido pensar en ella. No es tan buena porque parece que se sabe muy poco sobre ella.

Quizás la variante más común de su construcción es no echar en cada etapa todos los factores primos de p ₁ *...*p _n + 1 pero sólo el factor primo más pequeño. A esto lo llamo "secuencia de Euclides", siendo "semilla" el conjunto finito inicial no vacío de números primos con el que se empieza. Si su semilla es {2}, esto se llama la secuencia de Euclides-Mullin. Véase

http://en.wikipedia.org/wiki/Euclid%E2%80%93Mullin_sequence

para más información y enlaces.

Véase el problema 6 de

http://alpha.math.uga.edu/~pete/NT2009HW1.pdf

para algunas cuestiones, en su mayoría sin resolver, sobre estas secuencias. (El enlace es al primer conjunto de problemas de un curso avanzado de licenciatura en teoría de números que imparto periódicamente en la UGA).

Answer 3

Siguiendo con lo dicho por Qiaochu Yuan sobre f(x), se deduce que vamos a nunca conseguir esos primos a menos que empecemos, incluso si ne incluyen multiplicidades. Como empezamos con 'n', entonces estamos tomando los factores primos de 'n+1', entonces estamos tomando los factores primos de f(n+1), entonces f(f(n+1)), entonces f(f(f(n+1))) etc, incluso si obtenemos, digamos, un 7 2 ahí dentro, nuestro número es [f(f(f(n+1)))] / 7, que luego entra en f(x). Así que no, a menos que empieces con el producto infinito $p_1 = \prod_{n=1}^\infty 6n-1$ nunca conseguirás ninguno de esos números.

Es curioso; había empezado toda una demostración para demostrar que nunca se obtiene una multiplicidad al tomar f(f(...f(2)...)), pero esto es más sencillo. En cuanto a la secuencia de Euclid-Mullin, no tengo ni idea.