Euclidean Algorithm and Linear Equations

Date: 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/