**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 = q_{1}b + r_{1} ; 0 ≤ r_{1} < b

If it happens that r_{1} = 0 then b\a and gcd(a, b) = a, when r_{1} ≠ 0, divided by r_{1} to produce integers q_{2} and r_{2} satisfying

b = q_{2}r_{1} + r_{2}; 0 ≤ r_{2} < r_{1}

If r_{2} = 0, then we stop. Otherwise proceed as before to obtain.

r_{1} = q_{3}r_{2} + r_{3} ; 0 ≤ r_{3} < r_{2}

This division process continuous until some zero remainder appears, say at the (n + 1) th stage where r_{n-1} is divided by r_{n}(a zero remainder occurs sooner or later since the decreasing sequence b > r_{1} > r_{2 }> … ≥ 0 cannot more than b integers.)

The result is the following system of equations

a = q_{1}b + r_{1}; 0< r_{1} < b

b = q_{2}r_{1} + r_{2}; 0 < r_{2} < r_{1}

r_{1} = q_{3}r_{2} + r_{3}; 0 < r_{3} < r_{2}

………………………..

r_{n-2} = q_{n}r_{n-1} + r_{n}; 0 < r_{n} < r_{n-1}

r_{n-1} = q_{n+1}r_{n} + 0

We argue that r_{n} 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)