Bulgarian Winter Tournament

Let $d=(x,y)$ be the greatest common divisor of the numbers $x$ and $y$. Then, $x=d{x}_1$, $y=d{y}_1$, where $x_1,y_1$ are coprime naturals. The expression in the condition can be rewritten as $$\frac{d^{k-1}}{y_1^2-x_1^2}{x}_1^k{y}_1=p,$$ where we want $p$ to be prime. But $(x_1^k,y_1^2-x_1^2)=(x_1,y_1{)}^{\min (k,2)}=1=(y_1,y_1^2-x_1^2)$, i.e., $x_1^k{y}_1$ is coprime to $y_1^2-x_1^2$ and for $p$ to be whole it takes $y_1^2-x_1^2\mid d^{k-1}$. Moreover, $y_1>x_1$ and therefore $x_1^k{y}_1>1$. Therefore, to be $p$ it is simply necessary that $x_1=1$, $y_1=p$ and $y_1^2-x_1^2=d^{k-1}$ are fulfilled at the same time. If $k=1$, then $1=p^2-1=(p-1)(p+1)$, which is impossible. At $k=2$ we want $d=p^2-1$ and here the pair $(x,y)=(p^2-1,p(p^2-1))$ has the desired

property for every prime $p$. Therefore, $k=2$ is a solution. With $k>2$ we want $d^{k-1}=p^2-1=(p-1)(p+1)$. It is directly verified that $p=2$ does not lead to a solution, since 3 is not the $k-1$th power of a natural number. Hence, $p$ is an odd number and $8\mid p^2-1$, whence $k-1\ge 3$. Therefore, $k=3$ is not a solution. $k=4$ is a solution at $p=3$ and $d=2$, i.e., $(x,y)=(2,6)$. $\square$