Factorización prima de secuencia

Question

Estoy investigando la Factorización de Enteros y he encontrado un patrón interesante que no puedo explicar.

Para un número compuesto $N$, donde $N = PQ$.
Todos los factores de $(P + Q)$ se encuentran entre los factores de $(Nx^2 + 1)$ para $x$ entero y $x > 0$.

Por ejemplo $5713 = 29\cdot197$
$(P + Q) = 226 = 2 \cdot 113$

La secuencia $(5713 x^2 + 1)$ es:
$5714, 22853, 51418, 91409, 142826\cdots$

La factorización prima única de esta secuencia es:
$2, 17, 19, 43, 47, 53, 67, 71, 73, 89, 103, 109, 113, 127, 139, 151, 163\cdots$

Observa que no se listan todos los números primos, faltan $3, 5, 7, 11, 13\dots$
Sin embargo, los factores primos de $(P + Q)$ están (en este caso $2$ y $113$).

¿Alguien puede arrojar algo de luz sobre
1. ¿Por qué faltan algunos números primos en la factorización prima única de la secuencia?
2. ¿Por qué los factores de $(P + Q)$ están contenidos en la factorización de esta secuencia?

---

Los números altamente factorizables también funcionan.
$3795 = 3 \cdot 5 \cdot 11 \cdot 23$

$(P + Q)$ puede ser cualquiera de $(124, 148, 188, 268, 356, 764, 1268)$ y los factores de todos ellos se pueden encontrar entre la factorización prima única de $(3795 x^2 + 1)$.

El único ejemplo que encontré donde esto no funciona es cuando N es un cuadrado (por ejemplo $4, 9, 16$) o un múltiplo de un cuadrado (por ejemplo $12, 75, 98$).

---

Pido disculpas por cualquier problema de terminología, mi conocimiento de matemáticas no es excelente.
Me sugirieron math.stackexchange en lugar de stackoverflow.

Answer 1

¡Muy buena observación! Nunca había visto esto antes, pero aquí hay una prueba simple.

Supongamos que $p|P+Q$ donde $p$ es un número primo.

Entonces $Q = -P$ mod $p$, y $PQ = -P^2$ mod $p.

Para que $p$ factorice un elemento de la secuencia necesitamos que $p|(PQx^2 + 1)$ para algún $x$. Es decir, $PQx^2 = -1$ mod $p$.

Combinando estas dos relaciones obtenemos $$ P^2x^2 = 1 \quad mod \space p $$ lo cual se cumple cuando $x = \pm P^{-1}$ mod $p$

Para entender por qué faltan algunos primos en los factores de la secuencia, necesitas aprender sobre residuos cuadráticos. Estos están cubiertos en cualquier texto introductorio sobre teoría de números. La respuesta simple es que para que un primo $p$ exista en la secuencia, $-PQ$ debe ser un residuo cuadrático módulo $p$.