Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
College Number Theory
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search