The answers are all positive integers $k^4$ which is true by taking $d = k$. We'll now prove that there are no other integers that have this property. Let $n = da$ for an integer $a$. We then have \[ d^3 a + 1 \mid a^2 + 1 \]From here, by size reasons we get that $a \ge d^3$. But notice that \[ d^3 a + 1 \mid d^6(a^2 + 1) - (d^6 a^2 - 1) = d^6 + 1 \]Therefore, $a \le d^3$. This forces $a = d^3$.

How about this? We have $d^3a+1|a^2+1 \implies d^3a+1|a^2+1-d^3a-1$ Therefore,$d^3a+1 | a^2-d^3a$ $\implies d^3a+1 |a(a-d^3) \implies d^3a+1|a-d^3$. Case-1: $a< d^3$ Then, $d^3a+1 \le d^3-a$ $$\implies a(d^3+1)\le d^3-1$$$ a\le \frac{d^3-1}{d^3+1}<1$ Which is absurd. Case-2: $a >d^3$ Then,$d^3+1\le a-d^3 $ $$\implies a(d^3-1)\le -d^3-1$$Therefore,$a\le \frac{-(d^3+1)}{d^3-1}$. Which is not possible since $a$ is positive. So, clearly $a=d$ is the possible case. Fortunately,$x=d^4$ works, so we are done.

I'm a little confused on how you got $d^3a+1 \mid a^2+1$

Well, by assumption we have $d^3a+1 \mid d^2+n^2=d^2(a^2+1)$. But $d^3a+1$ is clearly coprime to $d$ and hence to $d^2$ so that this implies $d^3a+1 \mid a^2+1$.

Oh, thank you @Tintarn.

I also don't get how $d^3a+1 \le d^3-a$ in Case 1.

eduD_looC wrote: I also don't get how $d^3a+1 \le d^3-a$ in Case 1. Yes, this is the actual critical point. This woks if $a<d^3$ since then $d^3-a$ is a positive multiple of $d^3a+1$ and hence at least as large as $d^3a+1$. But of course this does not work if $d^3=a$. So in fact the solution in #3 would be correct by noting that this is the only missing case.

Tintarn wrote: eduD_looC wrote: I also don't get how $d^3a+1 \le d^3-a$ in Case 1. Yes, this is the actual critical point. This woks if $a<d^3$ since then $d^3-a$ is a positive multiple of $d^3a+1$ and hence at least as large as $d^3a+1$. But of course this does not work if $d^3=a$. So in fact the solution in #3 would be correct by noting that this is the only missing case. Ok thanks...I figured out my mistake.

One straightforward solution: consider the problem in the modulus $d^2n+1$, which means that we can change $n$ to $- \dfrac{1}{d^2}$ and then the problem is rewritten.(Write $n$ as $dn_1$and as$n \equiv -\dfrac{1}{d^2} (\mod nd^2+1)$, we have $n_1d^3+1 | d^3-n_1$. Compare the left and right hand side and we'll get $n_1=d^3 \Rightarrow n=dn_1=d^4$.)

Fair enough, but how is "rewriting the problem" a "straightforward solution"? I fail to see how the problem is trivial after that rewriting (of course it's not hard either, but then again the whole problem was not very hard to begin with...).

Let $n=dk$ where $n,d,k \in \mathbb{N}$. Note that \begin{align*}d^2n+1 \mid n^2+d^2 &\implies d^3k+1 \mid d^2(k^2+1) \implies d^3k+1 \mid k^2+1 \\& \implies d^3k+1 \leq k^2+1 \implies k \geq d^3 \qquad (*)\end{align*}Now because \begin{align*} d^3k+1 \mid k^2+1& \implies d^3k+1 \mid k^2+1-d^2k-1=k^2-kd^3 \\& \implies k-d^3\geq d^3k+1\end{align*}But $d^3k+1 \geq k-d^3$ so $k-d^3=0 \implies k=d^3.$ Therefore, $\boxed{n=d^4}$ where $d \in \mathbb{N}$.