gcd by subtraction

I am now getting into chapter 2 of Stillwell's number theory book and one of the first things I have seen is how to find the greatest common divisor (gcd) of two natural numbers using Euclid's subtraction algorithm. The greatest common divisor is equivalently known as the highest common factor (HCF) of two numbers. The OU defined the HCF of two natural numbers as "the largest number which is a factor of both or, alternatively, the product of the lowest power of each prime factor common to both" (see the OU's Revision Pack for MST121).

Let's see how this definition works. If I want the HCF of, say, 66 and 312, then breaking the numbers down into their prime factors we have 60=2²x3x5 and 312=2³x3x13. 2 and 3 are prime factors that are common to both numbers and the lowest power of 2 here is 2 and the lowest power of 3 is 1. Hence the HCF or gcd of 60 and 312 is 2²x3=12.

Now let's see how Euclid's subtraction algorithm works. Let a, b be natural numbers with a>b. We let
$$ a_{1}=a,        b_{1}=b    ...(1)$$  
Then for each (a_i,b_i) we form the pair (a_i+1,b_i+1), where
$$a_{i+1}=max(b_{i},a_{i}-b_{i}),         b_{i+1}=min(b_{i},a_{i}-b_{i})   ...(2)$$
and this is another example of descent because both a_i and b_i are decreasing sequences. Eventually,
$$a_{k}=b_{k}   ...(3)$$
for some k and we have that the gcd(a,b)=a_k=b_k.

So how does this work in practice? Taking our example from above, then we obtain the following sequence of pairs of numbers:
$$( a_{1}=312, b_{1}=60)$$
$$( a_{2}=252, b_{2}=60)$$
$$( a_{3}=192, b_{3}=60)$$
$$( a_{4}=132, b_{4}=60)$$
$$( a_{5}=72, b_{5}=60)$$
$$( a_{6}=60, b_{6}=12)$$
$$( a_{7}=48, b_{7}=12)$$
$$( a_{8}=36, b_{8}=12)$$
$$( a_{9}=24, b_{9}=12)$$
$$( a_{10}=12, b_{10}=12)$$ 
We stop at i=10 where a₁₀ and b₁₀ are equal. Hence the gcd(312,60)=12 as we have already discovered. It looks like the sequence a_i (i=1 to k) is strictly decreasing whereas the sequence b_i isn't. This in fact turns out to be the case and one of the tasks I set myself was to prove that this algorithm does indeed always work and this (lengthy) proof will be the subject of my next blog.