Diophantine Equations, Step by StepDate: 10/01/2002 at 12:00:29 From: Jennifer Subject: Finding all positive integer solutions Find all positive integer solutions to 43x + 7y + 17z = 400 Date: 10/01/2002 at 14:37:30 From: Doctor Greenie Subject: Re: Finding all positive integer solutions Hello, Jennifer - This problem gives you a lot of exercise in solving diophantine equations. Diophantine equations are ones in which you have fewer equations than unknowns and the values of the unknowns are restricted to integer values. Probably the most common type of problem involving diophantine equations is one in which there are three unknowns and you only have two equations. Your problem is more involved, since we have three unknowns and only one equation. To solve this type of problem, we simply choose, one at a time, all the possible values for one of the unknowns; for each of those values we get a diophantine equation with two unknowns, which we then solve using standard methods for diophantine equations. I will help get you started on this process, in case you are not familiar with those standard techniques. Because the coefficient on x is the largest of the three coefficients, the number of possible values for x is less than for the other unknowns. Because of this, we will have fewer cases to consider if we start our solution by considering the different possible values of x. 43*9 is less than 400 and 43*10 is greater than 400, so the range of values we need to consider for x is from 1 to 9. I will just pick one of these 9 cases; each one is solved in a manner similar to what I will show for that one case. The case I will work through is the case where x=3. Given x=3, our equation is 43(3)+7y+17z = 400 129+7y+17z = 400 7y+17z = 271 Now for a demonstration of the standard method for solving diophantine equations.... We take our equation in its current form and solve for one variable in terms of the other. It doesn't matter which variable you solve for. One way may lead to much simpler arithmetic later on than the other; with some experience, you might be able to predict which is the better way to go. I won't deal with that question here; I'm simply going to choose to solve for y in terms of z. 7y+17z = 271 7y = 271-17z 271-17z y = ------- 7 5 17z y = 38 - - --- 7 7 17z-5 y = 38 - ----- 7 In the preceding work, I could have stopped when I got the equation 271-17z y = ------- 7 However, with the equation in this form, finding values of z that make the expression on the right an integer is difficult because of the large numbers. The work I need to do to finish the analysis for this case will be easier if I take the whole number part out of the expression on the right. In the last form of the equation above, since y needs to be an integer and since 38 is an integer, I know that the expression 17z-5 ----- 7 must also be an integer. At this point, I just start trying values of z until I find one for which (17z-5) is a multiple of 7. Starting with z=1, z=2, etc., I find the following values for (17z-5): 12, 29, 46, 63, ... "63" is the first of these which is a multiple of 7; this gives me my first solution for this case: z=4; 17z-5=63; (17z-5)/7=63/7=9; y=38-9=29 The first solution I have found to the problem is (x,y,z) = (3,29,4) At this point, I can continue trying values of z=5, z=6, ..., and so on; but I can be smarter than that. In the expression 17z-5 ----- 7 the "17" and the "7" have no common factors; this tells me that, after the solution with z=4, my next possible solution will be with z=4+7=11. Trying this solution, I find z=11; 17z-5=182; (17z-5)/7=182/7=26; 38-26=12 And so the second solution I have found to the problem is (x,y,z) = (3,12,11) The next possible solution for this case should be when z=11+7=18; trying this solution, I find z=18; 17z-5=301; (17z-5)/7=43; y=38-43=-5 This attempt to find another solution gives me a negative value for y, so it is not a valid solution. This means I have found all the solutions for the case x=3. Note that there is one more place I can be smart to cut down on the amount of work I need to do. Once I have found my first solution for this case, (x,y,z) = (3,29,4) I can again look at the expression 17z-5 y = 38 - ----- 7 and see that, when I increase z by 7, my y-value is going to decrease by 17. So then I can find all my other solutions for the case x=3 simply by adding 7 to my z-value and subtracting 17 from my y-value until the y-value becomes negative: 1st solution: (3,29,4) 2nd solution: (3,12,11) 3rd solution: (3,-5,6) (invalid...) So...... There are 2 solutions to the problem when x=3. You need to go through this entire process for each of the other cases from x=1 to x=9 to find the complete set of solutions. It isn't really as much work as it sounds. For example, for the case x=9, the "43x" is nearly the whole total of 400, and it turns out there are no values of y and z that satisfy the original equation. And when you are done with the whole problem you will have had a lot of experience solving diophantine equations. I hope all this helps. Please write back if you have any further questions about any of this. - Doctor Greenie, 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/