## Numbers, Writing the gcd as a Linear Combination of s and t

### Writing the gcd as a Linear Combination of s and t

Let g be the gcd of s and t.
Are there coefficients x and y such that xs + yt = g?
There are, and Euclid's algorithm makes it easy to find them.
For convenience, think of s as t0, and think of t as t1.
The first step in the gcd algorithm computes t2
as the remainder when t0 is divided by t1.
We can write t0 = q1×t1 + t2.
Here q1 is the first quotient.
The same procedure is then applied to t1 and t2,
allowing us to write t1 = q2×t2 + t3.
Continue writing ti-1 = qi×ti + ti+1,
until tn = g.
Turn the last equation around,
so that g = tn-2 - qn-1×tn-1.
Replace tn-1 with tn-3 - qn-2×tn-2.
Replace tn-2 with a comparable expression in tn-4 and tn-3.
Continue backtracking
until g is a linear combination of t0 and t1,
better known as s and t.
Realize that this procedure works even if s and t are negative.
Here is the procedure, applied to 100 and 36.

```
100 = 2×36 + 28
36 = 1×28 + 8
28 = 3×8 + 4
----------------
4 = 28-3×8
4 = 4×28-3×36
4 = 4×100-11×36
```

Let s1 through sn be a finite set of nonzero integers.
Derive the gcd of this set as follows.
Let g2 = gcd(s1,s2).
Thereafter, let gi+1 = gcd(gi,si+1).
Finally gn is the gcd of the entire set.
Use the backtracking procedure to write gn as a linear combination of gn-1 and sn.
Then write gn-1 as a linear combination of gn-2 and sn-1.
Continue until g2 becomes a linear combination of s1 and s2.
Now gn, the final gcd, is a linear combination of the values s1 through sn.