Euclid's Algorithm: Let a and b be two positive integers with a <= b. Let d be their greatest common divisor(GCD). Then there are two lists of...

Euclid's algorithm is a way to find the GCD of any Euclidian domain, in this case, the natural numbers.

Euclid's Algorithm: Let a and b be two positive integers with a <= b. Let d be their greatest common divisor(GCD). Then there are two lists of positive integers q(i) and r(i) such that

b > r(1) > r(2) > r(3) ... > r(k-1) > r(k) > r(k+1) = 0 and

a = bq(1) + r(1)
b = r(1)q(2) + r(2)
r(1) = r(2)q(3) + r(3)
r(2) = r(3)q(2) + r(4)
.
.
.
r(k-2) = r(k-1)q(k) + r(k)
r(k-1) = r(k)q(k+1) (that is, r(k+1) = 0 )

and therefore d = r(k)

Proof

Since a < = b then there exists a q(1) and r(1) such that a = bq(1) + r(1) where 0 < = r(1) < b , and therefore, since r(1) < b there exists a q(2) and r(2) such that b=r(1)q(2) + r(2) and so one for r(2)< r(1). If we keep going down the line of positive integers we reach a point were r(k+1)=0 and so it is evident that:

b > r(1) > r(2) > r(3) ... > r(k-1) > r(k) > r(k+1) = 0

Now, to show that d (the GCD) is equal to r(k) we have to show that r(k) < = d and r(k) > = d.

First we show that r(k) < = d.

We first notice that r(k) divides r(k-1) (because r(k-1) = r(k)q(k+1)), we also notice that r(k) divides r(k-2) because r(k-2) = r(k-1)q(k) + r(k), and so r(k) divides both r(k) and r(k-1) by the proof we did two days ago. (When another proof is used in a proof, it is called a lemma). Now, if we keep going up the line, we see that every number has a component of the previous integer, and so r(k) is a common divisor for all the numbers including a and b. Since d is the GCD for a and b, then r(k) has to be < = d by the proof we did yesterday.

Now we show that r(k) > = d.

We note that d divides r(1) since r(1) = a - bq(1), and since d divides r(1) then by the proof we did two days ago, d also divides r(2) since r(2) = b - r(1)q(2), continuing this pattern down the line we see that d divides r(k-1) and r(k) and therefore r(k) > = d.

Now we can say that d= r(k) which is equal to 1, and 1 is the GCD of all positive integers, or the natural numbers.