Familia de GCDs todos iguales al $2$

Question

Es cierto que $$\gcd\left(5^{2^n} + 1, 13^{2^n} + 1\right) = 2$$ para todos los $n \in \mathbf{Z}_{\geq 0}$?

---

Estoy continuamente sorprendido con este y verificar numéricamente es bastante caro muy rápidamente (alrededor de $n = 20$).

Anteriormente he blogueado acerca de los orígenes del problema y se incluyó una prueba de una versión más fácil, pero esto sigue tocón de mí.

---

Dejando $F_n = 5^{2^n} + 1$ $T_n = 13^{2^n} + 1$ es claro que ambos satisfacen la recurrencia: $$f(n) \left(f(n) - 2\right) = f(n + 1) - 2$$ pero hasta ahora, he sido incapaz de utilizar este. Sin embargo, puede ser útil en la reducción de la cantidad de cálculo para atacar numéricamente. Concretamente, a partir de un conocido de salida del algoritmo de Euclides $$a_n F_n + b_n T_n = 2$$ la recurrencia puede ser útil en la determinación de $a_{n + 1}, b_{n + 1}$ en formas menos costosas. (Por supuesto, necesitamos definir estos de tal manera que ellos son únicos, por ejemplo,$0 \leq b_n < F_n$.)

---

[ACTUALIZACIÓN]: he comprobado @Zander's respuesta que tanto $F_{2206}$ $T_{2206}$ son divisibles por el valor de $p = 3 \cdot 2^{2208} + 1$ con el fragmento corto de Python a continuación. Esto muestra claramente que el mcd no es $2$. Yo también era capaz de demostrar que $p$ es primo (aunque esto no es necesario) mediante el uso de Proth del teorema y $a = 11$ como testimonio de primalidad. Por último, me quedo claro en la forma en que un $n$ (y con un $p$) puede ser encontrado.

n = 2206
modulus = 3 * (2 ** (n + 2)) + 1

f_residue = 5**(2**0) + 1
t_residue = 13**(2**0) + 1

for _ in xrange(n):
  f_updated = f_residue * (f_residue - 2) + 2
  f_residue = f_updated % modulus

  t_updated = t_residue * (t_residue - 2) + 2
  t_residue = t_updated % modulus

print '(5^(2^2206) + 1) MODULO (2^(2208) + 1):'
print f_residue
print '(13^(2^2206) + 1) MODULO (2^(2208) + 1):'
print t_residue

Answer 1

No, no es cierto. $p=3\cdot 2^{2208}+1$ divide el MCD al $n=2206$.

Si $p=3\cdot 2^{n+d}+1$ $d>0$ $x^{2^n}+1\equiv 0\pmod{p}$ $2^n$ distintas raíces en $[1,p-1]$. Para $d=1$ esto significa $1/6$ de todos los residuos son raíces, y si usted se imagina que su aparición en esta clase se ve "al azar" en cierto sentido, a continuación, para hablar $1/36$ de tales primos de ambos $5$ $13$ será raíces.

Del mismo modo al $d>1$ y también para los números primos de la forma $k\cdot 2^{n+d}+1$ podemos esperar con optimismo una fracción fija de números primos en el patrón para dar contraejemplos.

No hay ninguna garantía, porque puede haber algunos de los secretos de la estructura, pero creo que es probable que yo podría encontrar un pequeño-ish contraejemplo. Lamentablemente no pude encontrar uno con $d=1$.