Diophantine equation of the form $ax^2+by=1, hcf(a,b)=1$

Question

Is there any known method to solve for $(x,y)\in\mathbb{Z}^2$ the Diophantine equations of the form $$ax^2+by=1,\ a,b\in\mathbb{N}\text{ such that }hcf(a,b)=1?$$

Answer 1

The equation can be rearranged to \begin{eqnarray*} x^2=a^{-1} \pmod{b}. \end{eqnarray*} So it boils down to asking if $a^{-1}$ is a quadratic residue modulo $b$. The best way to solve this problem is to find a primitive element $p$ modulo $b$ ($a^{-1} =p^{\alpha}$) and then see if the exponent $\alpha$ is even.