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.

Proof of Euclid's algorithm

In my last blog I described how to obtain the gcd (greatest common divisor) of two natural numbers by using Euclid's subtraction algorithm. I now want to prove that this algorithm always works.

Let a and b be natural numbers and let a>b. We perform the following iterations. Let
$$ a_{1}=a,        b_{1}=b    ...(1)$$  
then for each pair (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 we continue this process until
$$a_{k}=b_{k}   ...(3)$$
for some k.

Firstly, we note that for two numbers x an y, one of the following is true
$$x>y,   x=y,   x<y$$
and since the iterations in (2) only continue until (3) is true and we begin with a₁>b₁ then
$$a_{i}>b_{i}      i=1,2,...,k-1         ...(4)$$
by the construction of (a_i+1,b_i+1) in (2).

Now we show that
$$a_{i}>b_{i}>0      i=1,2,...,k-1         ...(5)$$
We know that from (1) a₁>b₁ and from (2) that a₂ is either b₁ or a₁-b₁ whichever is the greater and b₂ is b₁ or a₁-b₁ whichever is the smaller. Hence, as b₁>0 and a₁>b₁ implies a₁-b₁>0, then with (4)
$$a_{2}>b_{2}>0$$
provided k>2. By the same argument we can show that
$$a_{3}>b_{3}>0$$
provided k>3 and so on. Hence, (5) is proven.

Now let a₁ and b₁ have greatest common divisor d (a natural number), so that a₁=f₁d and b₁=g₁d, for some natural numbers f₁ and g₁. We show that
$$a_{i}=f_{i}d,      b_{i}=g_{i}d       i=1,2,...,k-1       ...(6)$$
From (2) we have that a₂ and b₂ are either b₁=g₁d or a₁-b₁=f₁d-g₁d=(f₁-g₁)d. Thus we can write a₂=f₂d and b₂=g₂d where f₂ and g₂ are either g₁ or f₁-g₁ and since
$$a_{1}-b_{1}>0\Leftrightarrow (f_{1}-g_{1})d>0\Leftrightarrow f_{1}-g_{1}>0$$
(since d>0) then f₂ and g₂ are natural numbers. Now, so long as k>2, then (5) holds and so we can repeat this argument to obtain a₃=f₃d and b₃=g₃d where f₃ and g₃ are natural numbers and so on. Hence (6) is proven.

Having laid the foundations we now come to the crux of the proof. We show that
$$a_{1}>a_{2}>...>a_{k-1}>a_{k}   ...(7)$$
and
$$b_{1}\geq b_{2}\geq ...\geq b_{k-1}\geq b_{k}   ...(8)$$
So a_i and b_i are decreasing sequences (for i=1 to k). Actually a_i is strictly decreasing. We now determine the values of a_i+1 and b_i+1 using the definition in (2). Look at the following table for i=1,2,...,k-1:

	bi>a i-bi	ai-bi>bi
ai+1	bi	ai-bi
bi+1	ai-bi	bi

This shows how a_i+1 and b_i+1 are calculated based on the relative sizes of b_i and a_i-b_i. If b_i>a_i-b_i then using (5)
$$a_{i+1}=b_{i}<a_{i}\Rightarrow a_{i+1}<a_{i}    i=1,2,...,k-1$$
and using the above table
$$b_{i+1}=a_{i}-b_{i}<b_{i}\Rightarrow b_{i+1}<b_{i}    i=1,2,...,k-1$$
On the other hand if a_i-b_i>b_i then
$$a_{i+1}=a_{i}-b_{i}<a_{i}\Rightarrow a_{i+1}<a_{i}    i=1,2,...,k-1$$
and
$$b_{i+1}=b_{i}    i=1,2,...,k-1$$
Hence (7) and (8) are proven.

Now from (6), (7) and (8) we have
$$f_{1}d>f_{2}d>...>f_{k-1}d>f_{k}d$$
and
$$g_{1}d\geq g_{2}d\geq ...\geq g_{k-1}d\geq g_{k}d$$
Hence as d>0 this implies
$$f_{1}>f_{2}>...>f_{k-1}>f_{k}$$
and
$$g_{1}\geq g_{2}\geq ...\geq g_{k-1}\geq g_{k}$$
Thus we have two decreasing sequences of natural numbers and by descent we must eventually have
$$f_{k}=g_{k}=1    ...(9)$$
for some k. Note that because the sequence g_i is not strictly decreasing more terms other than the last may be 1. It follows that k is determined by the strictly decreasing sequence f_i.

Hence (3) is proven to be true since (9) implies that
$$df_{k}=dg_{k}=d$$
and hence
$$a_{k}=b_{k}=d$$
as required.