Solving a Diophantine Equation

Date: 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/