Writing the gcd as a Linear Combination of s and t

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 t₀, and think of t as t₁. The first step in the gcd algorithm computes t₂ as the remainder when t₀ is divided by t₁. We can write t₀ = q₁×t₁ + t₂. Here q₁ is the first quotient. The same procedure is then applied to t₁ and t₂, allowing us to write t₁ = q₂×t₂ + t₃. Continue writing t_i-1 = q_i×t_i + t_i+1, until t_n = g. Turn the last equation around, so that g = t_n-2 - q_n-1×t_n-1. Replace t_n-1 with t_n-3 - q_n-2×t_n-2. Replace t_n-2 with a comparable expression in t_n-4 and t_n-3. Continue backtracking until g is a linear combination of t₀ and t₁, 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 s₁ through s_n be a finite set of nonzero integers. Derive the gcd of this set as follows. Let g₂ = gcd(s₁,s₂). Thereafter, let g_i+1 = gcd(g_i,s_i+1). Finally g_n is the gcd of the entire set. Use the backtracking procedure to write g_n as a linear combination of g_n-1 and s_n. Then write g_n-1 as a linear combination of g_n-2 and s_n-1. Continue until g₂ becomes a linear combination of s₁ and s₂. Now g_n, the final gcd, is a linear combination of the values s₁ through s_n.