Diophantine Equations in Three VariablesDate: 11/17/2004 at 08:19:26 From: Kazim Subject: Diophantine Equations I need to know how to get positive integer solutions of two Diophantine equations having three variables. For example: 2x + 3y + 7z = 32 ; 3x + 4y - z = 19 (give the positive set of triples for the above equations) Date: 11/17/2004 at 19:34:32 From: Doctor Vogler Subject: Re: Diophantine Equations Hi Kazim, First of all, there are two ways to interpret your two equations, and I'm not sure which one you want. Either you want positive integer triples (x, y, z) that satisfy *both* equations 2x + 3y + 7z = 32 3x + 4y - z = 19, or you want all positive integer triples that satisfy the equation 2x + 3y + 7z = 32 as well as all positive integer triples that satisfy the equation 3x + 4y - z = 19. If the first case is what you want, then you just solve for the variable z in the second equation, substitute into the first equation, and that gives you a normal linear Diophantine equation in two variables. (If there weren't a variable with a coefficient of 1, then you could make one of the coefficients 1--leaving the rest integers-- by adding and subtracting multiples of one equation from the other, back and forth.) Here's an answer for our archives that discusses this case: Systems with More Variables than Equations http://mathforum.org/library/drmath/view/61825.html If the second case is what you want, then you are asking how to solve a linear Diophantine equation in three variables. The following answer discusses this case: Diophantine Equations, Step by Step http://mathforum.org/library/drmath/view/61325.html However, I would like to take this opportunity to describe a different technique for solving three-variable linear Diophantine equations that gives an answer more like the formula for all integer solutions to two-variable linear Diophantine equations. So I will use this technique to find all integer solutions to an equation, and then mention how you use this to find all *positive* integer solutions. First let's solve the equation 6x + 10y + 15z = 0. We know that z has to be even, right? And we know that y has to a multiple of 3, right? So suppose that z = 2a and y = 3b. Then we solve for x: 6x + 10(3b) + 15(2a) = 0 6x = -30b - 30a x = -5(a+b). Then that means that all solutions are x = -5(a+b) y = 3b z = 2a for any integers a and b. You can describe all of the solutions in different ways, as well. Basically, x has to be divisible by 5, y by 3, and x by 2. Then you can pick any two of those variables to be anything (satisfying the divisibility condition) and the third variable is determined from the equation. Let's try another. Let's solve your equation 2x + 3y + 7z = 32. As in solving a two-variable linear Diophantine equation, the first thing to do is find any *one* integer solution. In three variables, the easiest way to do this is often to pick any number for one of the variables and then use your usual techniques (such as modular inverses or the Euclidean algorithm) to find solutions in the others. Here's an easy solution for this equation: Take x=16 to cancel the 32 on the right, so you have 3y + 7z = 0, and then take y = 7 and z = -3. So now we have one solution, (16, 7, -3) and we want to find all solutions. Well, let's suppose that (x, y, z) is another solution. Then what happens if we subtract our known solution from it? 2(x - 16) + 3(y - 7) + 7(z + 3) = (2x + 3y + 7z) - 32 = 0. So that means that if a = x - 16 b = y - 7 c = z + 3, then (a, b, c) satisfy the equation 2a + 3b + 7c = 0. Now you see why I started with an equation that equaled zero. In the previous case, there were common factors between any two of the coefficients, and that allowed us to divide by those common factors. If there are not, as here, then you don't divide by anything. (I.e. you divide by the common factor 1.) But we still can't solve for a until we know that 3b + 7c is even. So we have to make it even. We do this by noticing that if 3b + 7c is even, then so is b - c. So we let b = c + 2r, and now we know that 2a = -(3b + 7c) = -(3c + 6r + 7c) = -(10c + 6r) is even, so we can solve for a: a = -(5c + 3r). And c can be anything. So we have a = -5s - 3r b = s + 2r c = s for some integers r and s. That is, every solution to 2a + 3b + 7c = 0 has that form for some r and s. Furthermore, for any integers r and s, those three numbers are solutions. If we recall that a = x - 16 b = y - 7 c = z + 3, then we can also say about all solutions to 2x + 3y + 7z = 32 that they are given by x = 16 - 5s - 3r y = 7 + s + 2r z = -3 + s. Finally, if we want to find only positive solutions, then we just have to find all (s, r) pairs that satisfy the three inequalities x = 16 - 5s - 3r > 0 y = 7 + s + 2r > 0 z = -3 + s > 0. The easiest way to solve these inequalities might be to graph them (as lines) on a plane and count all of the lattice points (integer points). Now, let me summarize (and generalize). Suppose we want to solve an equation of the form Ax + By + Cz = N for some (known) integers A, B, C, and N. We may assume that A, B, and C have no common factor (of all three), since if such a common factor divides N, then we can divide the whole equation by that number. If that common factor does not divide N, then there are no solutions. First we find a single particular solution by choosing any number x. If gcd(B, C) > 1, then our x must satisfy Ax = N (mod gcd(B, C)). Then we find some solution for y and z, such as by using the Euclidean Algorithm. So now we have a particular solution (x0, y0, z0). To find all solutions, we let x' = x - x0 y' = y - y0 z' = z - z0 and find that (x', y', z') must satisfy Ax' + By' + Cz' = 0. Next, x' must be divisible by gcd(B, C), and y' must be divisible by gcd(A, C), and z' must be divisible by gcd(A, B), so we let x" = x'/gcd(B, C) y" = x'/gcd(A, C) z" = z'/gcd(A, B), and we let A' = A/(gcd(A, C)*gcd(A, B)) B' = B/(gcd(A, B)*gcd(B, C)) C' = C/(gcd(A, C)*gcd(B, C)) so that now we have A'x" + B'y" + C'z" = 0 where A', B', and C' are pairwise relatively prime (that is, no two have a common factor). Now we would like to solve for x", so we decide what b must be mod A'. B'y" + C'z" = 0 (mod A'). So we find an integer k that satisfies B'k + C' = 0 (mod A'), which is -C'/B' (mod A') and can be computed using the Euclidean algorithm, and then y" - kz" must be divisible by A', so we let y" = kz" + A'r and then we solve for x" A'x" = -B'y" - C'z" = -B'(kz" + A'r) - C'z" = -(B'k + C')z" - A'B'r and so x" = -B'r - z"(B'k + C')/A' where that last number m = (B'k + C')/A' is an integer. Finally, we choose any number for z" and we get x" = -B'r - ms y" = ks + A'r z" = s x' = gcd(B, C) * (-B'r - ms) y' = gcd(A, C) * (ks + A'r) z' = gcd(A, B) * s x = x0 + gcd(B, C) * (-B'r - ms) y = y0 + gcd(A, C) * (ks + A'r) z = z0 + gcd(A, B) * s and this last formula gives us all integer solutions to the equation Ax + By + Cz = N in the form of linear combinations of the two arbitrary integers r and s. Of course, this isn't the *only* way to express all integer solutions. For example, we can change r to -t or t-s or t-7s, and get new ways to write out all integer solutions. Or we can change s to t-6r, for example. (We can't change them to just anything, but we can change them to many different things.) I hope you find this useful and informative. If you have any questions about this or need more help, please write back, and I will try to explain further. - 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/