[SOLVED] Understanding implementation of Extended Euclidean algorithm

Understanding implementation of Extended Euclidean algorithm

After some experimentation and search, I came up with the following definition:

emcd' :: Integer -> Integer -> (Integer,Integer,Integer)
emcd' a 0 = (a, 1, 0)
emcd' a b = 
  let (g, t, s) = emcd' b r
  in (g, s, t - (q * s))
    where
      (q, r) = divMod a b

What's the meaning behind this expression t - (q * s) ?

I've tried to evaluate it by hand; even though I arrived at the correct result (1, -4, 15), I can't see why that expression returns the value of t.

There is a famous method for calculating s and t in as + bt = gcd(a, b). In the process of finding the gcd, I get several equations.

By reversing the steps in the Euclidean Algorithm, it is possible to find these integers a and b. Those resulting equations look like the expression t - (q * s); however, I can't figure out the exact process.

Solution

Since (q, r) = divMod a b, we have the equation

a = qb + r

and because of the recursive call, we have:

tb + sr = g

Substituting a-qb for r in the second equation, that means

tb + s(a-qb) = g
tb + sa - qsb = g
sa + (t-qs)b = g

This explains why s and t - q*s are good choices to return.