Si $n$ divide $2^{2^{n} +1}+1$ $\to$ $n$ divide $2^{n}+1$ ?

Question

Encuentra un contraejemplo para demostrar que la siguiente implicación no es válida.

si $n$ divide $2^{2^{n} +1}+1$ $\to$ $n$ divide $2^{n}+1$

Y mostrar cómo usarlo.

Esta pregunta apareció en el tema En $n \mid 2^{2^n+1}+1$ implica $n \mid 2^{2^{2^n+1}+1}+1$ ?

ACTUALIZACIÓN: Perdón, me he equivocado al escribir la implicación. Escribí si $n$ divide $2^{2^{n} +1}+1$ $\to$ $n$ divide $2^{n}+n$ pero lo correcto es que $n$ divide $2^{2^{n} +1}+1$ $\to$ $n$ divide $2^{n}+1$

Answer 1

$n=3$ hace el truco: $$3 \ |\ 2^9 + 1 = 513$$ pero $$3 \not |\ 2^3 + 3 = 11$$

Answer 2

El post que enlazaste rebotó $n = 57$ y resulta que es un contraejemplo.

Primero, mostraré que $57\ |\ 2^{2^{57} + 1} + 1$ . Para ello, demostraré que es divisible por 19 y 3.

$\phi(3) = 2$ Así que $2^{2^{57} + 1} \equiv 2^1 \bmod{3}$ y, por lo tanto, sabemos que $2^{2^{57} + 1} + 1 \equiv 2^1 + 1 \equiv 0\bmod{3}$ .

$\phi(19) = 18$ y $\phi(18) = 6$ Así que $2^{57} + 1 \equiv 2^3 + 1 = 9\bmod{18}$ y $2^{2^{57} + 1} + 1 \equiv 2^9 + 1 = 513 \bmod{19}$ . $513 = 19 \times 27$ Así que $2^{2^{57} + 1} + 1$ también es divisible por 19.

A partir de esto, podemos concluir que $57\ |\ 2^{2^{57} + 1} + 1$ .

Ahora, $\phi(57) = 36$ Así que $2^{57} + 1 \equiv 2^{21} + 1 = 2097153 \bmod{57}$ . Haciendo la división, se puede ver que esto realmente deja un resto de 9 (Para los perezosos, $2097144 = 57 \times 36792$ ).

Por lo tanto, $57\ |\ 2^{2^{57} + 1} + 1$ pero $57\not|\ 2^{57} + 1$ .

(Ver Teorema de Euler para saber cómo he reducido todos esos exponentes).

---

En cuanto a "cómo usarlo", ¿qué caso de uso concreto querías?