Relación entre el primer factorizations de $n$$n+1$?

Question

Hay teoremas que nos da ninguna información acerca de la factorización en primos de un número entero $n+1$, si ya sabemos que la factorización de $n$?

Recordando Euclides la famosa prueba de la infinitud del conjunto de los números primos, supongo que sabes que si $n = p_1 p_2 p_3$, $n+1$ no tiene $p_1$, $p_2$, o $p_3$ como factores. Pero, ¿hay alguna manera de que podamos utilizar la información sobre $n$'s de la factorización para determinar algo más preciso sobre la factorización de $n+1$?

Answer 1

En la actualidad se sabe muy poco acerca de este problema y parece intratable por métodos conocidos, aunque es de gran interés. Más generalmente, un aditivo de la teoría de números, asume el reto de estudiar la estructura aditiva de los números primos, que está obligado a ser difícil debido a su inherente naturaleza multiplicativa.

Algunos de los problemas que se beneficiaría enormemente de saber cómo la adición de efectos de primer factorizations incluyen: El Gemelo Primer Conjetura y La Conjetura de Collatz.

Answer 2

Mientras que la factorización de $N$ podría no ayudar mucho con la factorización de $N+1$, en circunstancias especiales, esto puede ayudar a determinar la primalidad de $N$.

Famosos ejemplos de esto incluyen Pépin el Test de primalidad de los números de la forma $2^{2^n}+1$, y Proth del Teorema de primalidad de los números de la forma $k \times 2^n+1$ donde $k<2^n$ (Proth de los números primos en la parte superior de 20 conocidos de los números primos).

Hay más general de las pruebas de primalidad para $N+1$ basado en (parcial) conocimiento de la factorización de $N$, pero tienden a ser menos elegante. Por ejemplo, esta fue cortada de "Factorizations de $b^n \pm 1$, b = 2, 3, 5, 6, 7, 10, 11, 12 Hasta Altas Potencias" por Brillhart, Lehmer, Selfridge, Tuckerman, y Wagstaff, Jr.:

Teorema 11. Deje $N-1=FR$ donde $F$ es completamente factorizado y $(F,R)=1$. Supongamos que existe una $a$ que $a^{N-1} \equiv 1 \pmod N$ $(a^{(N-1)/q}-1,N)=1$ para cada factor primordial $q$$F$. Vamos $R=rF+s$, $1 \leq s < F$, y supongamos que $N<2F^3+2F$, $F>2$. Si $r$ es impar, o si $r$ es incluso y $s^2-4r=t^2$, $N$ es primo. De lo contrario, $s^2-4r=t^2$ $$N = [\frac{1}{2}(s-t)F+1][\frac{1}{2}(s+t)F+1].$$

Answer 3

Como escribí cuando esta pregunta se planteó en MathOverflow, sabiendo que el de la factorización de $n$ dijo mucho acerca de la factorización de $n+1$, los números de Fermat $2^{2^n}+1$ sería fácil --- pero, no lo son.