Integer Solutions of ax + by = cDate: 04/03/2001 at 19:58:44 From: Chris Armentrout Subject: integer solutions to ax+by = c Dr. Math, I am teaching a class to help prepare colleagues for the California Praxis exam. This question came up for us. While we were able to find part A all right, we could not find the solution to the general solution. A) Given the equation 5y - 3x = 1, find three points where x and y are both integers. B) Show that there will always be integer points (x,y) in ax + by = c if a, b and c are all integers. If not, show a counterexample. Thanks, I'm looking forward to your reply. Chris Armentrout Date: 04/04/2001 at 18:13:57 From: Doctor Paul Subject: Re: integer solutions to ax+by = c Solving equations of the form ax + by = c has been around for a long time. The mathematician Diophantus of Alexandria (200-284 AD) gave a general solution for when problems of this type are solvable. Of course he was only interested in integer solutions, so when we say a problem like this is solvable, we mean that there exist integers x and y such that ax + by = c. Because Diophantus showed when these equations are solvable, they are today known as Diophantine equations. More specifically, they are linear Diophantine equations. In general, linear Diophantine equations are solvable if and only if the greatest common divisor of a and b divides c. So this answers part B in your question. If you try to find integers x and y such that 3x + 6y = 4, you'll have problems. Notice that gcd(3,6) = 3 and since 3 does not divide four, the problem has no solution. You're welcome to try to find a solution, but you'd be wasting your time. If the linear Diophantine equation is solvable, there is an infinite number of integer solutions. Here's how to solve them: You first need to know the Euclidean algorithm for determining the gcd of a and b. So let's do that. It's easiest to show an example of how it works: Let's say you want to find the gcd of 6 and 64. Proceed as follows (the idea is a generalization of the division algorithm): 64 = 10*6 + 4 6 = 1*4 + 2 4 = 2*2 + 0 When you get a zero in the "remainder" spot, you're done. The gcd is the previous remainder. So in this case, the gcd of 6 and 64 is two. Let's do another example: Find the gcd of 12 and 136. 136 = 11*12 + 4 12 = 3*4 + 0 so the gcd of 12 and 136 is 4. One of the things that Euclid showed is that you can express gcd(a,b) as a linear combination of a and b. That is, there always exist integers x and y such that ax + by = d, where d = gcd(a,b). This is getting closer to what we want, but we're not quite there yet. The way to find the integers x and y is to use the Euclidean algorithm (which you just did to find the gcd of a and b) in reverse. Let's go to 2 Solve for the gcd: 2 = 6 - 1*4 Now look at the next line up in your Euclidean algorithm: 64 = 10*6 + 4 Solve this for the remainder: 4 = 64 - 10*6. Now substitute this expression of the number four into the last line we had: 2 = 6 - 1*4 2 = 6 - 1*4 2 = 6 - 1*(64 - 10*6) 2 = 6 - 64 + 10*6 2 = 11*6 - 64 We have found the desired integers. So if we had been asked to find integers x and y such that 6x + 64y = 2, we could reply that x = 11 and y = -1 back to when we found the gcd of 6 and 64. We said that was 2. So that means we can find integers x and y such that 6x + 64y = 2. Let's find them. Here's how to do it. Start with the next to the last line in your Euclidean algorithm (the one that gave the gcd): 6 = 1*4 + 2 Solve for the gcd: 2 = 6 - 1*4 Now look at the next line up in your Euclidean algorithm: 64 = 10*6 + 4 Solve this for the remainder: 4 = 64 - 10*6. Now substitute this expression of the number four into the last line we had: 2 = 6 - 1*4 2 = 6 - 1*4 2 = 6 - 1*(64 - 10*6) 2 = 6 - 64 + 10*6 2 = 11*6 - 64 We have found the desired integers. So if we had been asked to find integers x and y such that 6x + 64y = 2, we could reply that x = 11 and y = -1. Let's do another example like this. Find integers x and y such that 12378x + 3054y = 6 Well, we first need to find gcd(12378,3054). It should be obvious at this point that gcd(12378,3054) = 6 because I haven't told you how to finish the problem if the right-hand side is not equal to gcd(a,b). We proceed to find gcd(12378,3054): 12378 = 4*3054 + 162 3054 = 18*162 + 138 162 = 1*138 + 24 138 = 5*24 + 18 24 = 1*18 + 6 18 = 3*6 + 0 So gcd(12378,3054) is indeed 6. Now write 6 as a linear combination of 12378 and 3054 by reversing the steps of the Euclidean algorithm that was used to find the gcd. 6 = 24 - 18 = 24 - (138 - 5*24) = 6*24 - 138 = 6(162-138) - 138 = 6*162 - 7*138 = 6*162 - 7(3054 - 18*162) = 132*162 - 7*3054 = 132(12378 - 4*3054) - 7*3054 = 132*12378 + (-535)*3054 Thus x = 132 and y = -535 The French mathematician Gabriel Lame (1795-1870) proved that the number of steps required in the Euclidean Algorithm is at most five times the number of digits in the smaller integer. In this example, the smaller integer (3054) has four digits, so the total number of divisions cannot be greater than 20; in fact, only six divisions were needed. Now let's talk about what to do if asked to find integers x and y such that ax + by = t, where t is not equal to gcd(a,b). The procedure is exactly the same as the procedure outlined above, but one extra step is needed. The extra step will become obvious as we proceed. Let's look at an example: 172x + 20y = 1000 Using the Euclidean Algorithm, it is found that gcd(172,20) = 4. I'll leave the work to you. Working backward to write 4 as a linear combination of 172 and 20, we obtain: 4 = 2*172 + (-17)*20 Again, you supply the work. We wanted to have something of the form 1000 = 172x + 20y. Now the aforementioned extra step: Do you see that if we take the equation 4 = 2*172 + (-17)*20 and multiply both sides by 1000/4 = 250, we're done? 4 = 2*172 + (-17)*20 1000 = 500*172 + (-4250)*20 So we were asked to solve 172x + 20y = 1000. Clearly, x = 500 and y = -4250. Now let's go back to something I said in the beginning. I said that if a set of integer solutions (x,y) existed, an infinite number of integer solution pairs exist. That is indeed the case. If x = x_0 and y = y_0 are the initial solutions, then the family of solutions is given by: x = x_0 + (b/d)*t y = y_0 - (a/d)*t where d = gcd(a,b) and t is an arbitrary integer. So here's an example of that idea. If you look at the linear Diophantine equation 5x + 22y = 18, the initial solution is x = 8, y = -1. The complete solution is given by: x = 8 + 22t y = -1 - 5t (You do the work.) I hope this has been helpful. Please write back if you have additional questions. - Doctor Paul, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/