All positive integers $n$ such that $n \mid 2^{n-1}+1$

Question

How can one find all positive integers $n$ for which $n \mid 2^{n-1}+1$?

Answer 1

The idea behind this solution is that if $n>1$ then $n$ must be odd, so $2^{n-1}+1$ is a sum of coprime squares, and we get $n\equiv 1 \bmod{4}$, so that $2^{n-1}+1$ is a sum of coprime fourth powers and $n\equiv 1 \bmod{8}$, etc...

We claim that if $p$ is an odd prime such that $p\mid x^{2^k}+1$ for some natural $k$ and integer $x$, then $p\equiv 1 \bmod{2^{k+1}}$. Because $p\mid x^{2^k}+1$ implies that $x^{2^{k+1}}\equiv 1 \bmod{p}$ and $x^{2^k}\equiv -1 \not \equiv 1 \bmod{p}$, then the order of $x$ modulo $p$ divides $2^{k+1}$ and doesn't divide $2^k$. We conclude that it's $2^{k+1}$, and using Fermat's little theorem we get that $2^{k+1}\mid p-1$, as we wanted.

Back to the original problem, we claim that $n=1$ is the only solution. It's clearly a solution so suppose that $n>1$. Then $n$ is necessarily odd, so let $k$ be the greatest integer such that $n\equiv 1 \bmod{2^k}$. Using the lemma proved before with $x=2^{\frac{n-1}{2^k}}$, we get that all prime factors of $n$ must be $1\bmod{2^{k+1}}$ (because they're odd). This immediately implies that $n\equiv 1 \bmod{2^{k+1}}$, contradicting the maximality of $k$, as desired.

Answer 2

$If\ n|(2^{n-1}+1)$

Clearly, n is odd.

$2^{n-1}≡-1\pmod{n}$

$2^{2(n-1)}≡1\pmod{n}$

=> $\mathrm{ord}_n2|2(n-1)$, but $\mathrm{ord}_n2∤(n-1)$ and $\mathrm{ord}_n2∤2$ as n-1 is even.

=>$\mathrm{ord}_n2=2(n-1)$ which is impossible as $\mathrm{ord}_n2$ must divide $\phi(n) ≤ n-1 $