## 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.