I am asking myself the following question:
Let $p$ and $q$ be two primes. How can we solve the qaudratic Diophantine equation $pX^2+qY+d = 0$?
My take on that would be as follows. The equation implies the two congruences:
- $pX^2 \equiv -d \pmod q$, equivalent to $X^2 \equiv -dp^{-1} \pmod q$
- $qY \equiv -d \pmod p$, equivalent to $Y \equiv -dq^{-1} \pmod p$
We check if $-dp^{-1}$ is indeed a quadratic residue modulo $q$ with the "Euclidean -style" algorithm of the Jacobi symbol, if not the equation has no solution. We can also calculate the square root of $-dp$ using Cipolla's or the Tonelli Shanks algorithm to get $\sqrt{-dq^{-1}}$ modulo $p$.
Here I get stuck: How can we combine this to find the solutions of $pX^2+qY+d = 0$ ?