Bulgarian Mathematical Olympiad

Solution:

It follows by the given condition that $m(m+j-1)=j(j-1)$ and hence $m^{2}=(j-m)(j-1)$. If $p$ is a prime divisor of $j-m$ and $j-1$, then it divides $m$. Therefore $p$ divides $j$ and $1$. This contradiction shows that $j-m$ and $j-1$ are coprime. Then $j-m=u^{2}$ and $j-1=v^{2}$, where $u$ and $v$ are non-negative integers. It follows that $uv=m$ and $u^{2}+uv=j=v^{2}+1$, and the condition $1 \leq j < 2004$ gives $0 \leq v \leq 44$. So, we have to solve in non-negative integers the equation
$$u^{2}+uv=v^{2}+1$$
If $v=0$, then $u=1$. Assume that the pair $(u_{0}; v_{0})$ is a solution of $(*)$ and $v_{0} \geq 1$. Then $u_{0} \geq 1$. Since $u_{0}v_{0} \geq 1$, it follows that $u_{0} \leq v_{0}$. Moreover, it is clear that $v_{0}<2u_{0}$. Set $v_{1}=v_{0}-u_{0}$, $0 \leq v_{1}<v_{0}$. We have that $u_{0}^{2}=v_{0}(v_{0}-u_{0})+1=(u_{0}+v_{1})v_{1}+1=u_{0}v_{1}+v_{1}^{2}+1$. Set $u_{1}=u_{0}-v_{1}=2u_{0}-v_{0}>0$. Then
$$(u_{1}+v_{1})^{2}=(u_{1}+v_{1})v_{1}+v_{1}^{2}+1 \Longleftrightarrow u_{1}^{2}+u_{1}v_{1}=v_{1}^{2}+1$$
i.e., we obtain a new solution of $(*)$. If $v_{1}=0$, then $u_{1}=1$. If $v_{1} \geq 1$, then $u_{1} \geq 1$. Setting $v_{2}=v_{1}-u_{1}<v_{1}$ and $u_{2}=u_{1}-v_{2}$, we get in the same way a new solution. So, we get a sequence of non-negative integers $v_{0}>v_{1}>\cdots$. If $v_{k}=0$ for some $k$, then $u_{k}=1$ and writing $u_{k-1}, v_{k-1}, \ldots, u_{0}, v_{0}$, we get the Fibonacci sequence.

Thus solutions of $(*)$ are $(u; v)=(1; 0), (1; 1), (2; 3), (5; 8), (13; 21)$, and for the other solutions we have that $v>44$. The first solution of $(*)$ gives $j=v^{2}+1=0^{2}+1=1$ and then $m=uv=0$, which does not satisfy the given condition. The other solutions give the following solutions of the problem: $j=1^{2}+1=2$, $j=3^{2}+1=10$, $j=8^{2}+1=65$ and $j=21^{2}+1=442$.