Integer Solutions to AX + BY = C
Date: 04/25/2000 at 12:01:33 From: Carol Subject: Algebraic equation with 2 variables How do you prove that, for any equation of the form ax + by = c, where a, b and c are whole numbers, there will be an infinite number of whole number solutions for both x and y? (There is an exception to this - see next paragraph.) For example, the equation 4x + 7y = 30 is true for x (-3, 4, ...) and y (6, 2, ...). I have a feeling that for ANY values of a, b and c, there must exist an infinite number of cases where both x and y are whole numbers. However, there are important exceptions to this. For example, the equation 2x + 4y = 65 cannot have whole number solutions for both x and y, since the sum of multiples of 2 must be even, and 65 is odd. This would be true for any equation in which a is a multiple of b (or vice versa), and c is not a multiple of either a or b. Apart from this situation, however, is it indeed the case that there exist an infinite number of whole number solutions for both x and y simultaneously in any equation ax + by = c? If so, how would you prove this? Thanks for your help. Carol
Date: 04/25/2000 at 13:07:04 From: Doctor Rob Subject: Re: Algebraic equation with 2 variables Thanks for writing to Ask Dr. Math, Carol. Your intuition is correct. Whenever there is a solution, there are infinitely many. Let d = GCD(a,b), the greatest common divisor of a and b. Then if d is not a divisor of c, there is no solution. If d is a divisor of c, there are solutions, and if (X,Y) is one solution, then all solutions have the form x = X + (b/d)*t y = Y - (a/d)*t where t is any integer. Thus there are infinitely many solutions whenever there are any. You can check this by substituting these into the equation and seeing that all the terms involving t drop out, and what is left is just the statement that (X,Y) is a solution. If d does divide c, then you can divide d out of the equation to obtain (a/d)*x + (b/d)*y = c/d and GCD(a/d,b/d) = 1. To find the one solution (X,Y), you can first solve (a/d)*x + (b/d)*y = 1 This is done by using the Extended Euclidean Algorithm starting with the two numbers a/d and b/d. If (x0,y0) is one solution to that equation, then X = (c/d)*x0, Y = (c/d)*y0, is one solution to the original equation. Again, this is easy to check. If you want to know more about the use of the Extended Euclidean Algorithm to solve A*x + B*y = 1 with GCD(A,B) = 1, write again. - Doctor Rob, The Math Forum http://mathforum.org/dr.math/
Date: 04/26/2000 at 15:05:23 From: J. Alfred Prufrock Subject: Re: Algebraic equation with 2 variables Dear Dr. Rob, Thank you very much for your help. I have a couple of questions about what you said though. I hope they're not too silly. 1) Why is it that if GCD(a,b) is divisible by c, there must be solutions? I can see why there WON'T be solutions if GCD(a,b) is not divisible by c, but what guarantees that there will be solutions if it is? Is it because a multiple, say m, of a number can always be expressed as the sum of two multiples of m? 2) What about when GCD(a,b) = 1? Is a solution guaranteed for the same reason? (In this case m = 1, and any multiple of 1 can be expressed as the sum of two other multiples of 1?) 3) Why do I first have to solve (a/d)*x + (b/d)*y = 1 in order to solve the original equation a*x + b*y = c? And yes, if you don't mind I would like to know more about using the Extended Euclidean Algorithm to solve A*x + B*y = 1. Sorry if the above questions are stupid; I am learning all this on my own and have no one else to ask! Thanks very much, Carol
Date: 04/26/2000 at 17:16:11 From: Doctor Rob Subject: Re: Algebraic equation with 2 variables Thanks for writing back. The only silly question is the one that isn't asked! 1) There are solutions when d divides c because they can be constructed using the techniques described above and below. 2) When d = 1, it automatically divides c, so there are always solutions. They are constructed using the technique described below. 3) You solve (a/d)*x + (b/d)*y = 1 first because we know how to do that easily, and by doing it, we can solve the original equation easily. It is just a matter of breaking down an originally hard-looking problem into smaller, more manageable pieces. This is not the only way to solve such problems, just a systematic method that always works. Suppose you have two nonzero integers A and B. Then this is the Euclidean Algorithm: 1. Start with two nonzero integers A and B. 2. Express A = q*B + r, q and r integers with 0 <= r < |B|. (Do this using division with remainder.) 3. If r = 0, output |B| and stop. 4. Replace (A,B) by (B,r). 5. Go to Step 2 above. When you do this, the algorithm will output GCD(A,B) and stop. Now the Extended Euclidean Algorithm is similar, but you compute more numbers as you go along: 1. Start with two nonzero integers A and B, and set (u,U) = (1,0) and (v,V) = (0,1). 2. Express A = q*B + r, q and r integers with 0 <= r < |B|. 3. If r = 0, output |B|, U, and V, and stop. 4. Replace (A,B) by (B,r), (u,U) by (U,u-q*U), and (v,V) by (V,v-q*V). 5. Go to Step 2 above. When you do this, the algorithm will output GCD(A,B), U, and V, and the following equation will be true: A*U + B*V = GCD(A,B). Now when GCD(A,B) = 1, you get the solution x = U, y = V, of the equation A*x + B*y = 1. Example: Solve 323*x + 256*y = 1. Solution, using the Extended Euclidean Algorithm: 1. (A,B) = (323,256), (u,U) = (1,0), (v,V) = (0,1). 2. 323 = 1*256 + 67, so q = 1, r = 67. 3. Continue. 4. (A,B) = (256,67), (u,U) = (0,1), (v,V) = (1,-1). 2. 256 = 3*67 + 55, so q = 3, r = 55. 3. Continue. 4. (A,B) = (67,55), (u,U) = (1,-3), (v,V) = (-1,4). 2. 67 = 1*55 + 12, so q = 1, r = 12. 3. Continue. 4. (A,B) = (55,12), (u,U) = (-3,4), (v,V) = (4,-5). 2. 55 = 4*12 + 7, so q = 4, r = 7. 3. Continue. 4. (A,B) = (12,7), (u,U) = (4,-19), (v,V) = (-5,24). 2. 12 = 1*7 + 5, so q = 1, r = 5. 3. Continue. 4. (A,B) = (7,5), (u,U) = (-19,23), (v,V) = (24,-29). 2. 7 = 1*5 + 2, so q = 1, r = 2. 3. Continue. 4. (A,B) = (5,2), (u,U) = (23,-42), (v,V) = (-29,53). 2. 5 = 2*2 + 1, so q = 2, r = 1. 3. Continue. 4. (A,B) = (2,1), (u,U) = (-41,107), (v,V) = (53,-135). 2. 2 = 2*1 + 0, so q = 2, r = 0. 3. Output (1,107,-135) and stop. Now 323*107 - 256*135 = 34561 - 34560 = 1 so the solution is (107,-135). Example: Solve 323*x + 256*y = 179. From the previous example, we know that 323*107 + 256*(-135) = 1. Thus 323*(107*79) + 256*(-135*79) = 79 so one solution is (107*79,-135*79) = (8453,-10665). Then the general solution is x = 8453 - 256*t y = -10665 + 323*t for any integer t. - Doctor Rob, 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.