Determine all positive integers $n$ which have a divisor $d$ with the property that $dn+1$ is a divisor of $d^2 + n^2$

Question

Determine all positive integers $n$ which have a divisor $d$ with the property that $dn+1$ is a divisor of $d^2 + n^2$.

So i formed the equation that $$\frac{n}{d} = \frac{d^2 + n^2}{dn + 1}$$

And ended with $n = d^3$ which I think is wrong If I'm wrong can someone please show me the right way.

Answer 1

Write $n = cd$. Then \begin{align*} 1 + dn \mid d^2 + n^2 &\iff 1 + cd^2 \mid d^2 + c^2 d^2 \\ &\iff 1 + cd^2 \mid d^2 (1 + c^2) \\ &\iff 1 + cd^2 \mid 1 + c^2 \quad \quad \quad (\text{since } 1 + cd^2 \text{ and } d \text{ are relatively prime}) \\ &\iff 1 + cd^2 \mid 1 + c^2 - (1 + cd^2) = c^2 - cd^2 \\ &\iff 1 + cd^2 \mid c(c - d^2) \\ &\iff 1 + cd^2 \mid c - d^2. \quad \quad \quad (\text{since } 1 + cd^2 \text{ and } c \text{ are relatively prime}) \\ \end{align*}

Therefore, we restate the problem as follows: find all positive integers $\boldsymbol{c,d}$ such that $\boldsymbol{1 + cd^2 \mid c - d^2}$.

There are three cases: $c - d^2 = 0$, $c - d^2 > 0$, and $c - d^2 < 0$.

• Case 1: $c - d^2 = 0$

  Here we get that $n = cd = d^3$, which is indeed one possible solution.

• Case 2: $c - d^2 > 0$.

  In this case, $c - d^2$ is a positive multiple of $1 + cd^2$, so $1 + cd^2 \le c - d^2$, so $cd^2 - c + d^2 - 1 \le -2$, so $(c + 1)(d^2 - 1) \le -2$. But this is a contradiction, since $c+1$ and $d^2-1$ are nonnegative.

• Case 3: $c - d^2 < 0$.

  In this case, $d^2 - c$ is a positive multiple of $1 + cd^2$, so $1 + cd^2 \le d^2 - c$, so $cd^2 - d^2 + c - 1 \le -2$, so $(c - 1)(d^2 + 1) \le -2$. But this is a contradiction, since $c+1$ and $d^2-1$ are nonnegative.

Therefore, the only solution is $n = d^3$.

Answer 2

This is an additional remark, not really an answer to the question. I shall not provide a proof either, but the technique I used to get this result is basically Vieta Jumping. I have to post as an answer because the comment is too long.

It is well known (at least you can find a proof of this extraordinary claim in the link given above) that, if $a,b\in\mathbb{N}_0$ are such that $k:=\frac{a^2+b^2}{ab+1}$ is an integer, then $k=m^2$ for some $m\in\mathbb{N}_0$. For a fixed $m$, every solution $(a,b)\in\mathbb{N}_0\times\mathbb{N}_0$ to $\frac{a^2+b^2}{ab+1}=m^2$ is either of the form $\left(x_r(m),x_{r+1}(m)\right)$ or of the form $\left(x_{r+1}(m),x_r(m)\right)$, where $\left(x_r(m)\right)_{r=0}^\infty$ is the sequence defined by $x_0(m)=0$, $x_1(m)=m$, and $$x_r(m)=m^2\cdot x_{r-1}(m)-x_{r-2}(m)$$ for all integers $r\geq 2$. Note that $$x_r(m)=\frac{m}{\sqrt{m^4-4}}\left(\left(\frac{m^2+\sqrt{m^4-4}}{2}\right)^r-\left(\frac{m^2-\sqrt{m^4-4}}{2}\right)^r\right)$$ for all $r\in\mathbb{N}_0$.

Note that, for $m\geq 2$, $\left(x_r(m)\right)_{r=0}^\infty$ is strictly increasing. Hence, if $r\geq 1$ and $x_r(m)\mid x_{r+1}(m)$, then by the relation $x_{r+1}(m)=m^2\cdot x_{r}(m)-x_{r-1}(m)$, we have that $x_{r}(m)\mid x_{r-1}(m)$. This can occur only when $r=1$ (where $x_{r-1}(m)=x_0(m)=0$). Thus, if $(a,b)=(d,n)$ is a solution in $\mathbb{N}\times\mathbb{N}$ with $d\mid n$ to $\frac{a^2+b^2}{ab+1}=m^2$ with $m\geq 2$, then $$(d,n)=\left(x_1(m),x_2(m)\right)=\left(m,m^3\right)\,.$$ For $m=1$, it is obvious that the only solution $(a,b)\in\mathbb{N}\times\mathbb{N}$ to $\frac{a^2+b^2}{ab+1}=m^2$ is $(a,b)=(1,1)$.