An Introduction to Basic Diophantine EquationsDate: 08/27/2007 at 02:33:59 From: Katie Subject: Diophantine equations 2 legged birds and 1 legged birds in a birdcage equaling 11 legs. What different combinations could there be to make 11 legs. I have never done Diophantine equations before and don't know how. Date: 08/27/2007 at 12:38:00 From: Doctor Greenie Subject: Re: diophantine equations Hi, Katie. This is a nice problem for looking at and understanding how Diophantine equations can be solved. Of course, by far the easiest way to solve this problem is to make a list of all the possible combinations. The numbers are small enough that it should be easy to figure out. So we'll first go ahead and solve it that way; then we will look at the solution using Diophantine equations and see the similarities between the two approaches. Suppose we let x be the number of 2-legged birds and y be the number of 1-legged birds. Then the total number of legs is 2x + y and we need to solve the equation 2x + y = 11 for all the solutions (x,y) that are non-negative integers. Let's do that by "trial and error", using logic to tell us what kinds of numbers to try. We will first find all the possible combinations by choosing different values of x in this equation--i.e., different numbers of 2-legged birds. number of number of remaining number of 2-legged legs on number 1-legged birds these of legs birds ------------------------------------------- 0 0 11-0 = 11 11 1 2 11-2 = 9 9 2 4 11-4 = 7 7 3 6 11-6 = 5 5 4 8 11-8 = 3 3 5 10 11-10 = 1 1 So our complete set of solutions (x,y) is (0,11), (1,9), (2,7), (3,5), (4,3), and (5,1) Now let's look at an algebraic solution, which is similar. This one does not use Diophantine equations; but seeing the similarity between the "trial and error" solution and the formal algebraic solution will be helpful when we get to the Diophantine approach later. Our beginning equation again is 2x + y = 11 We can solve this for "y": y = 11 - 2x Now we can choose non-negative integer values for x and find the corresponding values for y; and we can do this as long as the value we find for y is also a non-negative integer. x y = 11 - 2x --------------- 0 11 - 0 = 11 1 11 - 2 = 9 2 11 - 4 = 7 3 11 - 6 = 5 4 11 - 8 = 3 5 11 - 10 = 1 Now let's go back to the "trial and error" approach but this time we'll start by choosing numbers of 1-legged birds instead of choosing numbers of 2-legged birds, as we did above. Then we will look at the corresponding solution using algebra; this time we WILL use Diophantine equations. number of number of remaining number of 1-legged legs on number 2-legged birds these of legs birds --------------------------------------------------------------- 0 0 11 11/2 -- oops! not an integer 1 1 10 10/2 = 5 2 2 9 9/2 -- oops! 3 3 8 8/2 = 4 4 4 7 7/2 -- oops! At this point, we can see that any choice of an even number of 1-legged birds is not going to give us a solution, because the remaining number of legs will be odd, and no number of 2-legged birds will have a total number of legs that is odd. So we can save some time by not bothering with the even values for the choices for x. 5 5 6 6/2 = 3 7 7 4 4/2 = 2 9 9 2 2/2 = 1 11 11 0 0/2 = 0 Of course, we again end up with our same set of solutions: (0,11), (1,9), (2,7), (3,5), (4,3), and (5,1) Now let's look at the corresponding algebraic solution, using Diophantine equations. Our original equation is still 2x + y = 11 But this time we will solve this equation for x instead of y: 2x + y = 11 2x = 11 - y 2x = (10 + 1) - y 2x = 10 + (1 - y) x = 5 + (1 - y)/2 In the above work, a technique is used which is basic to one method for solving Diophantine equations. After we got the "x" term isolated on the left-hand side and saw that it had a coefficient of 2, we rearranged the terms on the right so that "as much as possible" of the right-hand side would be divisible by 2--so that, when we divide by 2 to find an expressions for "x" alone, we get integer results for as much as possible on the right-hand side. So now our equation is x = 5 + (1 - y)/2 and our x and y values are restricted to non-negative integers. On the left-hand side of this equation, "x" is an integer; and on the right-hand side, "5" is an integer. In order for the equation to be satisfied, the term "(1 - y)/2" must also be an integer. If (1 - y)/2 is to be an integer, then (1 - y) must be an even integer; and that means y must be an odd integer. And since y must be non-negative, our possible values for y are 1, 3, 5, .... So now we try these values for y, remembering that the corresponding value we get for x also has to be a non-negative integer: y x = 5 + (1 - y)/2 --------------------- 1 5 + 0/2 = 5 + 0 = 5 3 5 + -2/2 = 5 - 1 = 4 5 5 + -4/2 = 5 - 2 = 3 7 5 + -6/2 = 5 - 3 = 2 9 5 + -8/2 = 5 - 4 = 1 11 5 + -10/2 = 5 - 5 = 0 And once again we find the same set of solutions for (x,y): (0,11), (1,9), (2,7), (3,5), (4,3), and (5,1) I will show another example of solving Diophantine equations so you can see one more time the process which is used. But before I do that, let's look again at our original equation and at the solutions we found. The equation is 2x + y = 11 and the solutions we found are (0,11), (1,9), (2,7), (3,5), (4,3), and (5,1) Look at these solutions, and compare each one in the list to the next one. Each time x increases by 1, the value of y decreases by 2. Now let's look at the original equation and see why this makes sense. Our equation says that 2 times x plus y has to equal 11. Each time we increase x by 1, the value of "2 times x" increases by 2. If the sum has to remain 11, then the value of y has to decrease by 2. So instead of the formal algebraic process of using Diophantine equations to find the solution to your problem, we can find, by trial and error, ANY solution; then we can find all the other solutions by either adding 1 to x and subtracting 2 from y or by subtracting 1 from x and adding 2 to y. For example, if the first solution we found happened to be (x,y) = (2,7) then we could find the solutions for larger values of x by adding 1 to x and subtracting 2 from y... (2,7), (3,5), (4,3), (5,1) and we could find the solutions for smaller values of x by subtracting 1 from x and adding 2 to y... (2,7), (1,9), (0,11) Now let's look at an arbitrary--and slightly more difficult--example of a Diophantine equation and take one more close look at the formal algebraic process for solving it. 3x + 11y = 100 We solve the equation for x: 3x + 11y = 100 3x = 100 - 11y We want to "play" with the right-hand side so that, when we divide by 3 to get "x" by itself on the left, as much as possible of the right-hand side will be integers. 3x = 100 - 11y 3x = (99 + 1) - (12y - y) 3x = 99 + 1 - 12y + y 3x = (99 - 12y) + (1 + y) x = (33 - 4y) + (1 + y)/3 Now "x", "33", and "4y" are integers, so "(1 + y)/3" must be an integer. The non-negative integer values of y for which (1 + y)/3 is an integer are 2, 5, 8, 11, ... So we try each of these values in our equation for x in terms of y: y x = 33 - 4y + (1 + y)/3 (check this solution...) ---------------------------------------------------------------- 2 33 - 8 + 3/3 = 25 + 1 = 26 3(26) + 11(2) = 78 + 22 = 100 5 33 - 20 + 6/3 = 13 + 2 = 15 3(15) + 11(5) = 45 + 55 = 100 8 33 - 32 + 9/3 = 1 + 3 = 4 3(4) + 11(8) = 12 + 88 = 100 The next possible value of y (y = 11) will give us a negative value for x, so we are done. The set of solutions is (x,y) = (26,2), (15,5), (4,8) Note again how the solutions are related to the coefficients in the original equation. The equation is 3x + 11y = 100 Once we find one solution, we know we can find another solution by either adding 11 to x and subtracting 3 from y, or by subtracting 11 from x and adding 3 to y. So we could find the complete set of solutions for this example by finding one solution by trial and error and then using this process to find the remaining solutions. For this particular example, we might simply start trying different values for y until we find one which gives us an integer value for x...: y = 1; 3x + 11 = 100; 3x = 89 no, 89 is not divisible by 3 y = 2; 3x + 22 = 100; 3x = 78 yes, 78/3 = 26 So our "first" solution is (x,y) = (26,2) And then we find our other solutions by subtracting 11 from x and adding 3 to y, until we run into negative values for x: (26,2), (15,5), (4,8) Note that this "quick" process for finding all the solutions--by finding an initial solution by trial and error and then using the coefficients of the original equation to find the remaining solutions --CAN be useful for relatively simple examples. But the general algebraic process for solving Diophantine equations is still very useful, because in more difficult problems (with large coefficients for x and y) finding an initial solution by trial and error can be very difficult. 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-2015 The Math Forum
http://mathforum.org/dr.math/