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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.