Solving Diophantine Equations

Date: 12/20/2004 at 08:25:30
From: Gabriel
Subject: Diophantine equations

Is "xyzw + 3xyz + 3xy + 3x = c" a Diophantine equation?  Which
algorithm should I use to solve it for a given "c"?  Are solutions
(x,y,z,w) unique for every "c"?

The most confusing part is that somehow the variables connect to each 
other influencing the result.

Thanks for your time.

Date: 12/20/2004 at 12:03:34
From: Doctor Vogler
Subject: Re: diophantine equations

Hi Gabriel,

Thanks for writing to Dr. Math.  It is indeed a Diophantine equation,
if you're trying to find solutions where x, y, z, and w are integers.

"Solving" a Diophantine equation generally comes in two steps, and is
not always possible.  First you ask, "Are there any integer
solutions?" and an answer in the affirmative usually comes in the form
of (at least) one solution.  Next you ask "What are ALL integer
solutions?"

The first question is easy to answer for your problem.  Let x=y=z=1,
and then the equation becomes

  w + 3 + 3 + 3 = c,

so you can take x = 1, y = 1, z = 1, w = c - 9.  If c is an integer,
then there is at least one integer solution.  Now on to the harder
question.

There is no general algorithm for solving any Diophantine equation,
but there are several techniques.  For an equation like yours, where
there is one big term (xyzw) and all of the other terms are constant
multiples of a factor of the big term, I would recommend taking
advantage of this fact.

That usually amounts to dividing everything by the big term

  1 + 3/w + 3/(zw) + 3/(yzw) = c/(xyzw)

and then noticing that all of those fractions are going to be pretty
small unless your variables are pretty small (compared to c).  So you
check all of the small values for your variables, and then you show
that bigger values will give

  3/w + 3/(zw) + 3/(yzw) - c/(xyzw)

too far from an integer.

But you can even do better than this, since your equation has a very
convenient add-one-variable pattern to the terms.  You can factor it
like this:

  x(yzw + 3yz + 3y + 3) = c.

Then we clearly see that x must be a factor of c.  To find all
solutions, you will need to be able to factor c.  Then there are only
finitely many factors, so you try each one (positive and negative). 
For each factor, you let x be that factor, and then you solve for y.

  y(zw + 3z + 3) = c/x - 3.

You get an integer for c/x - 3, and now you need to factor that 
number.  Well, y can be any factor of that number (positive and
negative) so you try each value for y, and then you solve for z:

  z(w + 3) = (c/x - 3)/y - 3.

Again, you factor the number on the right, and z can be any factor of
that number, and w is 3 less than the corresponding factor

  w = ((c/x - 3)/y - 3)/z - 3.

And that algorithm will give you 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/