# Does a solution exist to Diophantine Equation?

I'm interested in finding if an integer solution exists to the equation $ax^2 + bx + cy + d = 0$

I found Dario Alpern's website https://www.alpertron.com.ar/QUAD.HTM which has a solver that seems to determine if a solution exists by trying to solve an equation of that form using module 9, 16, and 25. For example, $x^2 + 5 x + 15 y + 50 = 0$ gives "No solutions found using mod 9, so there are no integer solutions." but $x^2 + 15 x + 5 y + 50 = 0$ gives "There are solutions, so we must continue.".

My question is: how does module 9, 16, and 25 allow us to know if a solution exists and where can I find more information? Internet search didn't lead me anywhere - probably because I'm not using the right keywords.

To be clear, I am not interested in actually finding solutions; only whether or not a solution exists.

• To use more familiar notation, I'm referring to the general form $ax^2 + bxy + c y^2 + dx + ey + f = 0$ with $b=c=0$, leaving $ax^2 + dx + ey + f = 0$ (although I relabeled the final coefficients in my question). Commented Oct 21, 2016 at 6:06

$x^2+5x+15y+50\equiv x^2+14x+15y+50=(x+7)^2+1+15y\bmod9$. Now $15y$ is a multiple of 3, but $u^2+1$ isn't, so there is no solution modulo 3, never mind modulo 9.
In general, for your type of equation, $ax^2+dx+ey+f=0$, it makes sense to work modulo $e$: $ax^2+dx+f\equiv0\bmod e$. Completing the square on the left side, you will wind up with a congruence of the form $z^2\equiv g\bmod e$, so all you have to do is work out whether $g$ is a quadratic residue (that is, a "square") modulo $e$, and any intro Number Theory text will tell you how to do that, using quadratic reciprocity.
• That is true if $a$ and $e$ are coprime, and $e$ is odd or $d$ is even. Otherwise it can be a bit more complicated. Commented Oct 21, 2016 at 6:53
• @GerryMyerson How is $x^2 + 5x +15y + 50 \equiv x^2 + 14x + 15y + 50$? The $5x$ to $14x$ is not clear to me. If we can always substitute $f = m + n$ and get to a form $(x + \sqrt{m})^2 + n \equiv 0 mod e$ and work $mod e$, why does it matter if $a$ and $e$ are coprime and what can we do if they are not? Commented Oct 21, 2016 at 15:23
• mod $e$, not mode Commented Oct 21, 2016 at 15:26
• Did you miss the "mod 9", Dio? $5\equiv14\bmod9$. I encourage you to make up an example where $\gcd(a,e)\ne1$, and see what happens. Commented Oct 21, 2016 at 21:50
• Sorry Gerry, I overlooked the mod $9$. That makes sense. With your help I'm beginning to see that $f(x) \equiv 1$ mod $e$ is the best way to determine if a solution exists (or use $gcd(a,e)$ to make $a,e$ coprime) and the quadratic residue is an excellent source of information.I would venture to guess that the website's statement about using mod 9, 16, and 25 is a coding error, rather than a method to checking if a solution exists. Commented Oct 22, 2016 at 4:42