I’m interested in finding if an integer solution exists to the equation ax2+bx+cy+d=0ax^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, x2+5x+15y+50=0x^2 + 5 x + 15 y + 50 = 0 gives “No solutions found using mod 9, so there are no integer solutions.” but x2+15x+5y+50=0x^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 ax2+bxy+cy2+dx+ey+f=0ax^2 + bxy + c y^2 + dx + ey + f = 0 with b=c=0b=c=0, leaving ax2+dx+ey+f=0ax^2 + dx + ey + f = 0 (although I relabeled the final coefficients in my question).

– Dio12345

2 days ago

=================

1 Answer

1

=================

x2+5x+15y+50≡x2+14x+15y+50=(x+7)2+1+15ymod9x^2+5x+15y+50\equiv x^2+14x+15y+50=(x+7)^2+1+15y\bmod9. Now 15y15y is a multiple of 3, but u2+1u^2+1 isn’t, so there is no solution modulo 3, never mind modulo 9.

In general, for your type of equation, ax2+dx+ey+f=0ax^2+dx+ey+f=0, it makes sense to work modulo ee: ax2+dx+f≡0modeax^2+dx+f\equiv0\bmod e. Completing the square on the left side, you will wind up with a congruence of the form z2≡gmodez^2\equiv g\bmod e, so all you have to do is work out whether gg is a quadratic residue (that is, a “square”) modulo ee, and any intro Number Theory text will tell you how to do that, using quadratic reciprocity.

1

That is true if aa and ee are coprime, and ee is odd or dd is even. Otherwise it can be a bit more complicated.

– Robert Israel

2 days ago

@GerryMyerson How is x2+5x+15y+50≡x2+14x+15y+50x^2 + 5x +15y + 50 \equiv x^2 + 14x + 15y + 50? The 5x5x to 14x14x is not clear to me. If we can always substitute f=m+nf = m + n and get to a form (x+√m)2+n≡0mode(x + \sqrt{m})^2 + n \equiv 0 mod e and work modemod e, why does it matter if aa and ee are coprime and what can we do if they are not?

– Dio12345

2 days ago

mod ee, not mode

– Dio12345

2 days ago

Did you miss the “mod 9”, Dio? 5≡14mod95\equiv14\bmod9. I encourage you to make up an example where gcd(a,e)≠1\gcd(a,e)\ne1, and see what happens.

– Gerry Myerson

2 days ago

Sorry Gerry, I overlooked the mod 99. That makes sense. With your help I’m beginning to see that f(x)≡1f(x) \equiv 1 mod ee is the best way to determine if a solution exists (or use gcd(a,e)gcd(a,e) to make a,ea,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.

– Dio12345

yesterday