Second-Degree Two-Variable Diophantine Equation

Date: 04/12/2001 at 02:08:03
From: Melvin
Subject: Solving 2nd-degree 2-variable diophantine equation

I need to know an a method to solve a specific case of a general 
second-degree, two-variable diophantine equation:

Ax^2 + Bxy + Cy^2 + Dx + Ey + F = 0

where B^2-4AC=k^2 for some integer k

How to solve for integer values of x and y ?
Can you explain it together with the algorithm, so I can implement the 
solution on a computer program?

PS: I saw an explanation to this problem on Dario Alejandro Alpern's
page at http://www.alpertron.com.ar/METHODS.HTM   , but I can't 
understand what the author was trying to say.

Date: 04/12/2001 at 12:00:17
From: Doctor Rob
Subject: Re: Solving 2nd-degree 2-variable diophantine equation
 
Thanks for writing to Ask Dr. Math, Melvin.

The above Web page does explain the solution correctly and completely.
You only care about a small part of what is on that page, though, 
since you are dealing with a special case.

Start with

   A*x^2 + B*x*y + C*y^2 + D*x + E*y + F = 0.

Start the process of solving this equation by completing the square on
X.  Multiply the equation through by 4*A, and add and subtract
B^2*y^2 + 2*B*D*y + D^2:

 4*A^2*x^2 + 4*A*B+x*y + B^2*y^2 + 4*A*D*x + 2*B*D*y + D^2 +
           4*A*C*y^2 - B^2*y^2 + 4*A*E*y - 2*B*D*y + 4*A*F - D^2 = 0,
 (2*A*x+B*y+D)^2 - (B^2-4*A*C)*y^2 + (4*A*E-2*B*D)*y = D^2 - 4*A*F.

Now you know that B^2 - 4*A*C = k^2, so substitute that:

 (2*A*x+B*y+D)^2 - (k*y)^2 + (4*A*E-2*B*D)*y = D^2 - 4*A*F.

Now complete the square on y by multiplying through by k^2, and adding
(2*A*E-B*D)^2 to both sides:

 (2*A*k*x+B*k*y+D*k)^2 - (k^2*y + [2*A*E-B*D])^2 =
                                 D^2*k^2 - 4*A*F*k^2 + (2*A*E-B*D)^2.

Now the left side is a difference of squares, so factor it:

 (2*A*k*x+B*k*y+D*k-k^2*y-2*A*E+B*D)*
   (2*A*k*x+B*k*y+D*k+k^2*y+2*A*E-B*D) =
                                  D^2*k^2 - 4*A*F*k^2 + (2*A*E-B*D)^2.

Now there are two cases, if the right side of this equation is zero or
not.

Case 1:  G = D^2*k^2 - 4*A*F*k^2 + (2*A*E-B*D)^2 = 0. Then if either
factor on the left side is zero, there is a solution. This boils down
to finding the solutions of *either* of two linear Diophantine
equations in two unknowns:

   (2*A*k)*x + (B*k-k^2)*y = -D*k + 2*A*E - B*D,  or
   (2*A*k)*x + (B*k+k^2)*y = -D*k - 2*A*E + B*D.

Any solution to either equation will be a solution to the original 
one. A necessary and sufficient condition for the existence of a 
solution to one of these equations is that the GCD of the coefficients 
of x and y be a divisor of the right-hand side.  I leave the rest of 
this to you.

Case 2:  G = D^2*k^2 - 4*A*F*k^2 + (2*A*E-B*D)^2 is nonzero.  Then you
need to find all the divisors of G, both positive and negative.  Let
them be the set {u[i]: 1 <= i <= m}.  For each such divisor u[i], you
need to solve simultaneously the system of equations

   (2*A*k)*x + (B*k-k^2)*y + D*k - 2*A*E + B*D = u[i],
   (2*A*k)*x + (B*k+k^2)*y + D*k + 2*A*E - B*D = G/u[i].

or

   (2*A*k)*x + (B*k-k^2)*y = -D*k + 2*A*E - B*D + u[i],
   (2*A*k)*x + (B*k+k^2)*y = -D*k - 2*A*E + B*D + G/u[i].

The solutions of this are

   x = (-2*B^2*D+B*[4*A*E+u[i]-G/u[i]]+k*[-2*D*k+u[i]+G/u[i]])/
                                                            (4*A*k^2),
   y = (2*B*D-4*A*E-u[i]+G/u[i])/(2*k^2).

If either x or y is not an integer, you can throw that pair out.  The
pairs remaining will be all the solutions.

Example:  Solve

   x^2 + 9*x*y + 8*y^2 + 4*x - 5*y + 35 = 0.

Here A = 1, B = 9, C = 8, D = 4, E = -5, and F = 35.  Then
B^2 - 4*A*C = 81 - 32 = 49 = 7^2, so k = 7.  Multiply through by 4 and
complete the square on x:

   4*x^2 + 36*x*y + 16*x + 32*y^2 - 20*y + 140 = 0,
   (2*x+9*y+4)^2 + 32*y^2 - 81*y^2 - 20*y - 72*y + 140 - 16 = 0,
   (2*x+9*y+4)^2 - 49*y^2 - 92*y + 124 = 0.

Now multiply through by 7^2 and complete the square on y:

   (14*x+63*y+28)^2 - (49*y+46)^2 = -8192,
   (14*x+63*y+28-49*y-46)*(14*x+63*y+28+49*y+46) = -8192,
   (14*x+14*y-18)*(14*x+112*y+74) = -8192.

Now since G = -8192 is nonzero, we are in Case 2, and the factors of
G = -2^13 are:

   -8192, -4096, -2048, -1024, -512, -256, -128, -64, -32, -16, -8,
   -4, -2, -1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048,
   4096, and 8192

There are 28 factors.  The systems of equations look like

   14*x + 14*y = 18 + u[i],
   14*x + 112*y = -74 - 8192/u[i].

The solutions are

   x = (218 + 8*u[i] + 8192/u[i])/98,
   y = (-92 - u[i] - 8192/u[i])/98.

The choices for u[i] which give integer solutions are -2048, -256,
-32, or -4.  The corresponding solutions are

   (x,y) = (-165,20), (-19,2), (-3,2), or (-19,20).

I hope that this is clear.  If not, write again.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/