¿Cómo resolver $n^2+1 \mid 2^n+1$ para $n$ un entero positivo?

Question

¿Cómo resolver la siguiente relación de divisibilidad: $$n^2+1 \mid 2^n+1$$ para un entero positivo $n$?

Puede que hayas visto un problema similar en la IMO. Encuentra todos los enteros positivos $n$ tales que $\frac{2^n+1}{n^2}$ sea un entero.

Pero estoy seguro de que el $1$ adicional ha hecho que este problema sea difícil. $n$ debe ser par. Sea $p$ el menor divisor primo de $n^2+1$, entonces

$$p \mid \gcd \left(2^{p-1}-1, 2^{2n}-1 \right)=4^{\gcd \left((p-1)/2, n \right)}-1$$

¿Podemos decir algo sobre $\gcd \left((p-1)/2, n \right)$? ¿Alguna idea?

Answer 1

Aquí hay una solución parcial, dejando fuera el caso en que el resto de la división en cuestión es 1 más que un múltiplo de 16 (¡Que no puedo resolver!).

Las únicas soluciones para $n \leq 5$ son $n=2,4$, así que consideremos la ecuación para $n \geq 6$. Primero reescriba como $2^n +1 = a(n^2+1) \ $con$\ a\geq1$. Ahora claramente n debe ser par así que dejemos $n=2m, \ m \geq 3$. La ecuación ahora se convierte en $ \ 4^m+1=a(4m^2+1) \ $así que debemos tener $a \equiv 1 \mod4 \ $. Ahora comienza una serie de sustituciones sucesivas que eventualmente conducen a algo útil. $$ a=4b-3, \ b\geq 1 \\ \implies 4^{m-1} +1=(4b-3)m^2+b \\ \implies 3m^2+1 \equiv b \mod 4 \\ \implies b \equiv 0,1 \mod 4$$ Esta última línea es porque los residuos cuadráticos módulo 4 son 0 y 1. Considerando el caso donde b es 1 mod 4:

$$b=4c-3, \ c\geq 1 \\ \implies 4^{m-1}+1=16(c-1)m^2+4c-3 \\ \implies 4^{m-2}=(c-1)(4m^2+1)$$ No hay soluciones para $c \geq 2$ ya que el RHS tiene un factor impar ($4m^2+1$) pero el LHS no. Claramente c=1 no produce soluciones. Por lo tanto, para $n \geq 6$ debemos tener $b \equiv 1 \mod 4$ (o equivalentemente $a \equiv 1 \mod 16$).