Euclidean Algorithm: The Euclidean algorithm may be described as follows: Let a and b be two integers whose common divisor is desired. Since gcd(|a|,|b|)= gcd(a, b) there is no harm is assuming that a ≥ b > 0. The first step is to apply the division algorithm to a and b to get
a = q1b + r1 ; 0 ≤ r1 < b
If it happens that r1 = 0 then b\a and gcd(a, b) = a, when r1 ≠ 0, divided by r1 to produce integers q2 and r2 satisfying
b = q2r1 + r2; 0 ≤ r2 < r1
If r2 = 0, then we stop. Otherwise proceed as before to obtain.
r1 = q3r2 + r3 ; 0 ≤ r3 < r2
This division process continuous until some zero remainder appears, say at the (n + 1) th stage where rn-1 is divided by rn(a zero remainder occurs sooner or later since the decreasing sequence b > r1 > r2 > … ≥ 0 cannot more than b integers.)
The result is the following system of equations
a = q1b + r1; 0< r1 < b
b = q2r1 + r2; 0 < r2 < r1
r1 = q3r2 + r3; 0 < r3 < r2
rn-2 = qnrn-1 + rn; 0 < rn < rn-1
rn-1 = qn+1rn + 0
We argue that rn the last non zero remainder which appears in this manner is equal to gcd(a, b). (Proved)
Lemma: If a = qb + r then gcd(a, b) = gcd(b, r).
Proof: If d = gcd(a, b), then the relations d\a and d\b imply that d\(a – qb) or d\r.
Thus d is a common divisor of b and r. On the other hand, if c is an arbitrary common divisors of b and r, then c\(qb + r), whence c\a. This makes c is a common divisor of a and b, so that c ≤ d. It now follows from the definition of gcd(b, r) that
d = gcd(b, r). (Proved)