Associated Topics || Dr. Math Home || Search Dr. Math

### 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!

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/
```
Associated Topics:
College Number Theory
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search