If $n$ divides $2^{2^{n} +1}+1$ $\to$ $n$ divides $2^{n}+1$? Find a counterexample to show that the following implication is not valid.
if $n$ divides $2^{2^{n} +1}+1$ $\to$ $n$ divides $2^{n}+1$
And show how to use it.
This question appeared on the topic Does $n \mid 2^{2^n+1}+1$ imply $n \mid 2^{2^{2^n+1}+1}+1$?
UPDATE: Sorry, I made a mistake when typing the implication. I typed if $n$ divides $2^{2^{n} +1}+1$ $\to$ $n$ divides $2^{n}+n$ but the correct is if $n$ divides $2^{2^{n} +1}+1$ $\to$ $n$ divides $2^{n}+1$
 A: $n=3$ does the trick:
$$3 \ |\ 2^9 + 1 = 513$$
but
$$3 \not |\ 2^3 + 3 = 11$$
A: The post you linked bounced around $n = 57$, and it happens to be a counterexample.
First, I'll show that $57\ |\ 2^{2^{57} + 1} + 1$. To do this, I'll show that it is divisble by 19 and 3.
$\phi(3) = 2$, so $2^{2^{57} + 1} \equiv 2^1 \bmod{3}$, and thus, we know that $2^{2^{57} + 1} + 1 \equiv 2^1  + 1 \equiv 0\bmod{3}$.
$\phi(19) = 18$ and $\phi(18) = 6$, so $2^{57} + 1 \equiv 2^3 + 1 = 9\bmod{18}$, and $2^{2^{57} + 1} + 1 \equiv 2^9 + 1 = 513 \bmod{19}$. $513 = 19 \times 27$, so $2^{2^{57} + 1} + 1$ is also divisible by 19.
From these, we can conclude that $57\ |\ 2^{2^{57} + 1} + 1$.
Now, $\phi(57) = 36$, so $2^{57} + 1 \equiv 2^{21} + 1 = 2097153 \bmod{57}$. Doing out the division, you can see that this actually leaves a remainder of 9 (For the lazy, $2097144 = 57 \times 36792$).
Hence, $57\ |\ 2^{2^{57} + 1} + 1$, but $57\not|\ 2^{57} + 1$.
(See Euler's theorem for how I reduced all those exponents.)

As for "how to use it", what specific use case did you want?
