Euclidean Algorithm and Linear EquationsDate: 11/03/2003 at 19:11:33 From: Danielle Subject: Euclidean Algorithm I have read your explanations on the Euclidean Algorithm, but I am still confused on how it works for linear problems. Could you please explain step by step how to solve a linear problem to find x and y integers? I am confused at what to do after you find the greatest common divisor of ax + by = c. For example, in the linear equation 2y = 14x + 60y, I obtain 0 = 14x + 58y. By using the division algorithm I find that the GCD is 2. What is the next step to solving for x and y integers? Date: 11/03/2003 at 20:09:52 From: Doctor Rob Subject: Re: Euclidean Algorithm Thanks for writing to Ask Dr. Math, Danielle! If c is nonzero, proceed like this. The algorithm gives you a sequence of equations of this form: a = q(1)*b + r(1), b = q(2)*r(1) + r(2), r(1) = q(3)*r(2) + r(3), r(2) = q(4)*r(3) + r(4), ... r(k-2) = q(k)*r(k-1) + r(k), r(k-1) = q(k+1)*r(k). The GCD then is d = r(k). Rewrite all the equations (except the last) in the form: r(1) = a - q(1)*b, r(2) = b - q(2)*r(1), r(3) = r(1) - q(3)*r(2), r(4) = r(2) - q(4)*r(3), ... d = r(k) = r(k-2) - q(k)*r(k-1). Now work from the bottom upwards, substituting for the r(i) with the highest i in the current equation using the next one above on the above list. This starts with d = r(k-2) - q(k)*[r(k-3) - q(k-1)*r(k-2)], = [1 + q(k)*q(k-1)]*r(k-2) - q(k)*r(k-3). Next substitute for r(k-2) = r(k-4) - q(k-2)*r(k-3), and rearrange, gathering terms with the same r(i) together. Continue this until you have eliminated all the r(i)'s and have d expressed in terms of a and b. Then you can read off a pair (r,s) of integers which make a*r + b*s = d. Now multiply through by c/d, which must be an integer (or else there can be no solution), and you'll have a*(r*c/d) + b*(s*c/d) = c. Now the set of all pairs (x,y) which solve a*x + b*y = c are x = r*(c/d) + (b/d)*t, y = s*(c/d) - (a/d)*t, where t is any integer. To find the smallest pair (x,y), pick t to be approximately s*c/(a*d). For example to solve 422*x + 128*y = 10, perform the Euclidean Algorithm, 422 = 3*128 + 38, 128 = 3*38 + 14, 38 = 2*14 + 10, 14 = 1*10 + 4, 10 = 2*4 + 2, 4 = 2*2. Rearranging the equations, 38 = 422 - 3*128, 14 = 128 - 3*38, 10 = 38 - 2*14, 4 = 14 - 1*10, 2 = 10 - 2*4. Now working backwards, 2 = 10 - 2*(14 - 1*10) = 3*10 - 2*14, = 3*(38 - 2*14) - 2*14, = 3*38 - 8*14, = 3*38 - 8*(128 - 3*38), = 27*38 - 8*128, = 27*(422 - 3*128) - 8*128, 2 = 27*422 - 89*128. Multiplying by 10/2 = 5, 10 = 135*422 - 445*128. Then all solutions (x,y) of 422*x + 128*y = 10 are x = 135 + 64*t, y = -445 - 211*t. Picking t = -2, which is approximately (-445)/211, we find the smallest solution (x,y) = (7,-23). Sure enough, 7*422 + (-23)*128 = 2954 - 2944 = 10. ---------- If c = 0, the situation is simpler. If the GCD is d, then the equation becomes (a/d)*x = (-b/d)*y, and GCD(a/d,b/d) = 1, so a/d must be a divisor of y, that is, y = k*a/d, which implies that x = k*(-b/d), for any integer k. Thus the solution is (x,y) = (k*(-b/d),k*a/d), for any k. Feel free to write again if I can help further. - Doctor Rob, 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/