Solving Quadratic Diophantine and Pell Equations
Date: 05/04/2005 at 10:40:04 From: Deden Subject: NumberTheory Dear Dr. Math, Would you show me how to solve Diophantine equations that have the form a*x^2 + b*y^2 = z^2, with a, b, and z given?
Date: 05/04/2005 at 18:38:03 From: Doctor Vogler Subject: Re: NumberTheory Hi Deden, Thanks for writing to Dr. Math. So your equation is a*x^2 + b*y^2 = z^2. If a and b are given, and you want integer solutions in x, y, and z, then that is an easier question, because it means you really want to find rational solutions to a(x/z)^2 + b(y/z)^2 = 1, and you can learn about methods to find all rational solutions to an equation at Rational Solutions to Two Variable Quadratic Equation http://mathforum.org/library/drmath/view/65319.html But if, as you said, a, b, and z are given, and you want to find integer solutions in x and y, then it is slightly more complicated, but it can still be done. More generally, given a, b, and c, you can find integer solutions to a*x^2 + b*y^2 = c. (For your equation, just take c = z^2. The fact that it's a square doesn't change much.) There are a few different cases according to what a, b, and c are. Case 1: sign(a) = sign(b) = -sign(c). If a and b have the same sign (that is, both negative or both positive), then the left side of the equation will also have that sign, since x^2 and y^2 can never be negative. But if the right side (c) has a different sign, then there cannot be any solutions. Example: x^2 + y^2 = -1. Case 2: sign(a) = sign(b) = sign(c). If a, b, and c all have the same sign, then there are finitely many solutions. If all three are negative, then we can multiply both sides of the equation by -1 and then all three will be positive. Now suppose that all three are positive. Then since b*y^2 is greater than or equal to zero, that means a*x^2 <= c x^2 <= c/a. So all you have to do is check all of the integers from 0 up to the square root of c/a. For each of those numbers x, check if y^2 = (c - a*x^2)/b is both an integer and the square of an integer. Example: x^2 + 5y^2 = 14 Then y^2 <= 14/5 = 2.8. So we check y=0 and y=1, and only y=1 has a solution. So the solutions are (-3, -1), (3, -1), (-3, 1), (3, 1). You can also narrow down your search by using modular arithmetic (what values can x mod b have?). Example: 7x^2 + 2y^2 = 46 Then x^2 <= 46/7 = 6.5..., but also 7x^2 must be even, and so x must also be even. So we check x = 0 and x = 2, and only x = 2 works. So the solutions are (-2, -3), (2, -3), (-2, 3), (2, 3). Furthermore, quadratic reciprocity might allow you to determine very quickly that there are no solutions (if it is true that there are no solutions). Example: 7x^2 + 3y^2 = 692 Looking at this equation mod 3, we get x^2 = 2 (mod 3), which is impossible. Case 3: -ab is a square If you have -ab = m^2, then you can factor the left side. First multiply both sides of the equation by a: a^2*x^2 + ab*y^2 = ac and then change ab to -m^2 and factor: a^2*x^2 - m^2*y^2 = ac (ax + my)(ax - my) = ac. In this case, since ax + my and ax - my are both integers, each must be a factor of ac. So you can factor ac, make a list of all of its factors (and make sure that every number appears once as a positive and once as a negative), and then for each one, let ax + my be the factor F and ax - my be the corresponding factor G = ac/(ax + my). Then you can solve for x and y: ax + my = F ax - my = G x = (F + G)/(2a) y = (F - G)/(2m) and you throw away those solutions that don't give you integers. Example: x^2 - y^2 = 10 We factor this as (x - y)(x + y) = 10, and we list off all factors of 10, namely -10, -5, -2, -1, 1, 2, 5, 10, and for each we get x = -11/2, -7/2, -7/2, -11/2, 11/2, 7/2, 7/2, 11/2, but none of these are integers, so there are no solutions. Case 4: -ab is positive, but not a square This is the most difficult, or most complicated case. First I should discuss one particular case, namely when a=1, and c=1, and b is negative, but -b is not a square. Then we generally write d = -b, so that the equation is x^2 - d*y^2 = 1. This equation is called Pell's Equation. It takes some work to prove that this equation will have infinitely many solutions, and all of them are related in a simple way. In fact, there are two ways to show the relation. The idea is to find, first, the smallest positive solution (meaning NOT x = 1, y = 0) and call this solution (r, s), so that r^2 - d*s^2 = 1. Then all solutions can be written in the form x + y*sqrt(d) = + or - (r + s*sqrt(d))^k for an integer k. In fact, changing the sign of k amounts to changing the sign of y, and changing the "+ or -" amounts to changing the signs of both x and y. You can also write this as a recurrence; the first solutions are (1, 0) and then (r, s), and (r^2 + ds^2, 2rs), and then the recurrence continues infinitely, in both directions, where the solution that comes AFTER (x, y) is (rx + dsy, sx + ry), and the one that comes BEFORE (x, y) is (rx - dsy, -sx + ry). As I mentioned, proving this takes some work. And the situation only gets more complicated in the more general case when a is not 1, and c is not 1. If c is not 1 (but a = 1 still), then there may be several, although always finitely many "small solutions" (like (1, 0)) that start the recurrence, and then the recurrence still uses the same rule, where (rx - dsy, -sx + ry) becomes (x, y), which becomes (rx + dsy, sx + ry), where r and s are the smallest solution for the associated Pell Equation with c=1. In the other form, this means that x + y*sqrt(d) = (x0 + y0*sqrt(d))*(r + s*sqrt(d))^k where (r, s) is the smallest positive solution to r^2 - d*s^2 = 1, and there are finitely many choices of (x0, y0) to choose from. Finally, when a is not 1, then generally we still multiply the equation by a, getting (ax)^2 - (-ab)*y^2 = ac, and then we solve the equation for integers in (ax, y), where d = -ab, and then we throw away the solutions that don't have ax divisible by a. I deliberately tried to keep this discussion short, since it's a complicated topic, so if you want more details, then I will refer you to several places where you can learn more about Pell Equations, and quadratic Diophantine equations. There are a couple of helpful answers from our own archives, which you can find by searching our archives for "Pell equation." Then there is the MathWorld site on the subject at http://mathworld.wolfram.com/PellEquation.html You can certainly find much more information on the Internet by searching Google for "Pell equation," but I would like to point out two more good resources. One is a short paper written by a mathematician named Lenstra, which can be found at http://www.ams.org/notices/200202/200202-toc.html It is a very interesting paper that touches only lightly on many different aspects of Pell equations. It's good reading, and not too hard to read. The other is the home page of John Robertson, who has written a couple of very detailed papers describing good methods for finding all integer solutions to Pell equations and to other quadratic Diophantine equations. This page is at http://hometown.aol.com/jpr2718/ If you have any questions about this or need more help, please write back and show me what you have been able to do, and I will try to offer further suggestions. - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.