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.