Hace $n \mid 2^{2^n+1}+1$ implica $n \mid 2^{2^{2^n+1}+1}+1$ ?

Question

Hay dos formas de intentar demostrarlo. Una está en el título, la otra es su contraparte de Morgan: $n \nmid 2^{2^{2^n+1}+1}+1 \implies n \nmid 2^{2^n+1}+1$ . Para refutarlo sólo hace falta un ejemplo, por supuesto.

Intenté usar $\gcd(2^a+1, 2^b+1) = 2^{\gcd(a, b)}+1$ (donde $a$ y $b$ son enteros positivos Impares), pegados en ambos extremos. Me di cuenta de que si $n$ divide $2^n+1$ entonces n divide a ambos $2^{2^n+1}+1$ y $2^{2^{2^n+1}+1}+1$ pero esta implicación no funciona al revés (por ejemplo $n=57$ ).

Agradecería un poco de ayuda.

EDICIÓN1 El puntero de Eric no fue suficiente para mí. Tratando de golpe por la edición en lugar de volver a publicar (lo siento, no estoy seguro de cómo).

EDIT2 Esto no es mucho, pero podría ahorrarle tiempo a alguien. Usando la notación de user101140 y el $a^n+b^n$ identidad

$f(n) = 2^n+1 = 3 \sum\limits_{k=0}^{n-1} (-2)^k$

$f(f(n)) = 3 \sum\limits_{k=0}^{2^n} (-2)^k$

$f(f(f(n))) = 3 \sum\limits_{k=0}^{2^{2^n+1}} (-2)^k$

También, $n \mid f(n) \implies n \mid f(f(n))$ se debe a $n \mid f(n) \implies f(n) \mid f(f(n))$ por lo que la prueba podría ser algo parecido a $n \mid f(f(n)) \implies f(f(n)) \mid f(f(f(n)))$ . (Por favor, no me golpeen si es una estupidez).

Answer 1

Mi ordenador encontró el contraejemplo $n=520809$ .

Curiosamente $520809=57\times9137$ pero no pude encontrar ninguna "explicación" clara para ello, ni una forma natural de que $520809$ aparecería.

Otros pocos contraejemplos son $2343441, 15622617, 15622617...$ De hecho, se puede demostrar que hay infinitos de entonces ya que si $n$ funciona, $f(n)$ también funciona (ya que $a|b \Leftrightarrow f(a)|f(b)$ )

En caso de que alguien esté interesado en mi código python:

def factor(n): #Factors n, and returns a list with its factors (possibly repeated) in increasing order
 k=2
 v=\[\]
 while n>1:
  if n%k==0:
   v.append(k)
   n=n/k
  else:
   k=k+1
  if k\*k>n:
   v.append(n)
   return v

def phi(n): #Calculates the totient function using the prime factorization
 v=factor(n)
 prod=1
 a=1
 for b in v:
  if b==a:
   prod\*=b
  else:
   prod\*=b-1
   a=b
 return prod 

def f2(n): # Calculates f(f(n)) mod n
 a=pow(2,n,phi(n))+1
 return (pow(2,a,n)+1)%n

def f3(n): # Calculates f(f(f(n))) mod n
 a=pow(2,n,phi(phi(n)))+1
 b=pow(2,a,phi(n))+1
 return (pow(2,b,n)+1)%n

n=11
while 1: #Tries all odd n
 if f2(n)==0:
  if f3(n)!=0:
   print n
   break
 n=n+2

Answer 2

No soy matemático, así que corrígeme si he hecho algo mal...

Dejemos que

$f(n) = 2^{n} + 1$

Entonces

$f(a \cdot b) = (2^{a} + 1)(1 - 2^{a} + 2^{2a} - 2^{3a} + ... + (-1)^{b-1}2^{(b-1)a})$ , para $a$ y $b$ enteros.

Así que $f(a \cdot b) = f(a)g(a, b)$ y $g(a, b)$ también es un número entero.

Dejemos que $f(n) = n \cdot p$ . Es decir, $f(n)$ es divisible por $n$ .

Entonces

$f(f(n)) = f(n \cdot p) = f(n)g(n, p) = n \cdot p \cdot g(n, p) = n \cdot p_2$

Así que $f(f(n))$ es divisible por $n$ .

Y

$f(f(f(n))) = f(n \cdot p_2) = f(n)g(n, p_2) = n \cdot p_2 \cdot g(n, p_2)$

Así que $f(f(f(n)))$ es divisible por $n$ .

Pero $f(f(f(n))) = 2^{2^{2^n + 1} + 1} + 1$

Recordando, supuse que $f(f(n))$ es divisible por $n$ y obtuvo que $f(f(f(n)))$ también es divisible por $n$ .

Creo que eso está demostrado.