Find all $x$ such that $x\mid 2^x+1$ .
Naturally, I tried looking for some observation and cyclicity and didn't really come across the solution. Somehow I tried $9$ and it seems it works so I tried to find a pattern for $3k$ (which failed ofc) but ended up with $3^k$ which seems to be right. Although this claim can be proved. I want a complete generalization for the possible solutions not just some sets of it. I tried FLT which doesn't really fit in where as concepts like CRT, Euler Totient, etc. are not very useful here. It would be helpful if I could get some insight on how to approach such problems as well.
P.S : The problem was pretty much a sequence on oeis with some advanced theory. Thanks!
Best Answer
Clearly x must be coprime with 2 so x is an odd number
We can prove for $x=3^k$ using euler's theorem and induction $k\gt1$
$$ \phi(3^k)=3^k(1-\frac{1}3)=2\cdot3^{k-1}\\ 2^{\phi(3^{k+1})}\equiv1 \bmod(3^{k+1})\\ (2^{3^k})^2\equiv1 \bmod(3^{k+1})\\ (3^k\lambda-1)^2\equiv1 \bmod(3^{k+1})\\ -2\cdot3^k\lambda\equiv0 \bmod(3^{k+1})\\ $$
So $3|\lambda$ which gives
$$ 2^{3^k}+1\equiv0\bmod(3^{k+1})\\ \text{cube on both sides}\\ 2^{3^{k+1}}+3\cdot2^{3^k}(2^{3^k}+1)+1\equiv2^{3^{k+1}}+3^{k+1}C\lambda+1\equiv2^{3^{k+1}}+1\equiv0\bmod(3^{k+1}) $$
This completes the induction and gives an elementary insight $3^{k+1}|2^{3^k}+1$
note:this is a partial solution but im working on a full one cant seem to quite get it ill edit if i do