# 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$

## 2 Answers

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?

• Thank you. That was all I wanted to know. – Eduardo Oct 16 '13 at 20:47

$n=3$ does the trick: $$3 \ |\ 2^9 + 1 = 513$$ but $$3 \not |\ 2^3 + 3 = 11$$

• 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$ – Eduardo Oct 16 '13 at 20:11