Solving a Diophantine EquationDate: 05/01/2005 at 19:58:28 From: OC Subject: Diophantine ! How can I find all integer solutions of an equation in the form aXY + bX + cY + d = 0? For example, 5XY + 3X - 8Y - 8 = 0. I tried solving for Y and got to Y = -(bX + d)/(aX + c) Date: 05/02/2005 at 11:57:18 From: Doctor Vogler Subject: Re: Diophantine ! Hi OC, Thanks for writing to Dr. Math. Solving for Y like you did is a good idea. The next thing you should do is divide the polynomials on the right, as in, Y = -b/a + (constant)/(aX + c). Then if you multiply both sides by the number a, you find that the fraction has to be an integer, and there aren't very many X values that will do that for you. This idea can be used in more general Diophantine equations, too. Essentially, it amounts to the same thing as the following: Multiply the equation by the number a: a^2*XY + abX + acY + ad = 0 Then add bc - ad to both sides of the equation and factor the left side. You'll get (aX + c)(aY + b) = bc - ad. Now the right side is an integer, and you just have to factor it. You find all of the factors of the number on the right (including the negative ones, which are just the negations of the positive factors), and then aX + c has to be one of those factors, and aY + b has to be the corresponding factor. For each one, subtract c, divide by a, and see if you still have an integer. For example, if you have 5XY + 3X - 8Y - 8 = 0 then you multiply both sides by 5 and factor 25XY + 15X - 40Y - 40 = 0 (5X - 8)(5Y + 3) = 40 - 24 = 16. Then all factors of 16 are -16, -8, -4, -2, -1, 1, 2, 4, 8, 16. For each one, we add 8 and divide by 5 to get X -8/5, 0/5, 4/5, 6/5, 7/5, 9/5, 10/5, 12/5, 16/5, 24/5. The only ones that are divisible by 5 are X = 0/5 = 0 (from 5X - 8 = -8) and X = 10/5 = 2 (from 5X - 8 = 2). The corresponding Y values are Y = -1 (from 5Y + 3 = -2) and Y = 1 (from 5Y + 3 = 8). So those are all integer solutions! 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: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/