<s>[INST] How to solve $n^2+1 \mid 2^n+1$ for positive integer $n$? 
How to solve following divisibility relation: $$n^2+1 \mid 2^n+1$$ for positive integer $n$?

You might have seen the similar IMO problem. Find all positive integers $n$ such that $\frac{2^n+1}{n^2}$ is an integer.
But I am sure that the extra $1$ has made this problem difficult. $n$ must be even. Let $p$ be the smallest prime divisor of $n^2+1$, then
$$p \mid \gcd \left(2^{p-1}-1, 2^{2n}-1 \right)=4^{\gcd \left((p-1)/2, n \right)}-1$$
Can we say something about $\gcd \left((p-1)/2, n \right)$? Any ideas?
 [/INST] Here is a partial solution, leaving out the case when the remainder of the division in question is 1 more than a multiple of 16 (Which I cannot solve!).
The only solutions for $n \leq 5$ are $n=2,4$, so let's consider the equation for $n \geq 6$. First rewrite as $2^n +1 = a(n^2+1) \ $with$\ a\geq1$. Now clearly n must be even so let $n=2m, \ m \geq 3$. Equation now becomes$ \ 4^m+1=a(4m^2+1) \ $so we must have $a \equiv 1 \mod4 \ $. Now begins a series of successive substitutions that eventually lead to something useful. $$ a=4b-3, \ b\geq 1 \\ \implies 4^{m-1} +1=(4b-3)m^2+b \\ \implies 3m^2+1 \equiv b \mod 4 \\ \implies b \equiv 0,1 \mod 4$$
This last line is because the quadratic residues modulo 4 are 0 and 1. Considering the case where b is 1 mod 4:
$$b=4c-3, \ c\geq 1 \\ \implies 4^{m-1}+1=16(c-1)m^2+4c-3 \\ \implies 4^{m-2}=(c-1)(4m^2+1)$$
There are no solutions for $c \geq 2$ ince the RHS has on odd factor ($4m^2+1$) but the LHS does not. Clearly c=1 yields no solutions.
So for $n \geq 6$ we must have $b \equiv 1 \mod 4$ (Or equivalently $a \equiv 1 \mod 16$).
</s>