Second-Degree Two-Variable Diophantine EquationDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/