Euclid's Algorithm again

I now want to try and relate what I know about gcd's (greatest common divisors) to what we were taught about Euclid's algorithm at the OU (in courses MS221 and M208). I have so far mentioned Euclid's subtraction algorithm but there is a faster division algorithm which is defined as follows.

Suppose we want to find the gcd(a,b) of two natural numbers a and b. Let a>b and let
$$a_{1}=a,   b_{1}=b$$
Then for each pair (a_i,b_i) we form pair (a_i+1,b_i+1) as follows:
$$a_{i+1}=b_{i},    b_{i+1}=r_{i}$$
where r_i is the remainder when a_i is divided by b_i. The process is stopped when b_k divides a_k for some k in which case gcd(a,b)=b_k.

Let's take an example from the MS221 handbook (p83) and find the gcd(25,9). We have
$$(a_{1},b_{1})=(25,9)$$
$$(a_{2},b_{2})=(9,25-2\times 9)=(9,7)$$
$$(a_{3},b_{3})=(7,9-7)=(7,2)$$
$$(a_{4},b_{4})=(2,7-3\times 2)=(2,1)$$
As 1 divides 2 then the gcd(25,9)=1. This is not unexpected as 25 and 9 are coprime and so their only common divisor is 1. In MS221 and M208 we were interested in finding multiplicative inverses and this necessarily meant that we were only interested in numbers a and b that were coprime.

Now let's repeat the gcd calculation but replace 25 and 9 by the symbols a and b.
$$(25,9)=(a,b)$$
$$(9,7)=(b,a-2b)$$
$$(7,2)=(a-2b,b-(a-2b))=(a-2b,3b-a)$$
$$(2,1)=(3b-a,a-2b-3(3b-a))=(3b-a,4a-11b)$$
From this we deduce that 4a-11b=4x25-11x9=1. This process is called the extended Euclidean algorithm.

We can now see better what was actually going on in the method that we were taught at the OU. Here is the full OU example. We are asked to find the multiplicative inverse of 9 in Z₂₅={0,1,2,...,24}, that is the element x of Z₂₅ such that
$$9\times_{25} x=1$$
We applied the division algorithm repeatedly (i.e. we found the gcd(25,9)):
$$25=2\times 9+7$$
$$9=1\times 7+2$$
$$7=3\times 2+1$$
We then worked backwards from the last of these equalities (the extended algorithm):
$$1=7-3\times2$$
$$\Leftrightarrow 1=7-3\times (9-1\times 7)$$
$$\Leftrightarrow 1=-3\times 9+4\times 7$$
$$\Leftrightarrow 1=-3\times 9+4\times (25-2\times 9)$$
$$\Leftrightarrow 1=4\times 25-11\times 9$$
The last line is the result we had before. Thus we can write
$$9\times(-11)=(-4)\times 25 +1$$
That is
$$9\times(-11)\equiv 1\:(\mbox{mod }25)$$
or alternatively
$$9\times_{25} (-11)=1$$
However, -11 is not in Z₂₅ but
$$-11\equiv 14\:(\mbox{mod }25)$$
Thus
$$9\times_{25} 14=1$$
and so x is 14.