# Euclid's Division Lemma

**Euclidean Algorithm :**

Let a and b be positive integers with aâ‰¥ b.

If b divides a, then (a, b) = b.

If b divides a, then apply the division algorithm repeatedly as follows:

_{0}+ r

_{0}with 0 â‰¤ r

_{0}< b

b = r

_{0}q

_{1 }+ r

_{1 }with 0 â‰¤ r

_{1 }< r

_{0}

r

_{0}= r

_{1}q

_{2}+ r

_{2 }with 0 â‰¤ r

_{2}< r

_{1}

r

_{1}= r

_{2}q

_{3}+ r

_{3}with 0 â‰¤ r

_{3}< r

_{2}

r

_{2}= r

_{3}q

_{4}+r

_{4 }with 0 â‰¤ r

_{4}< r

_{3}......................

This process ends when the remainder 0 is obtained. This must occur after a finite number of steps; that is, for some k

r

_{k-2}= r

_{k-1}q

_{k }+ r

_{k }with 0 â‰¤ r

_{k}< r

_{k-1}

r

_{k-1}= r

_{k}q

_{k+1}+ 0

Then r

_{k}the last non zero remainder, is the greatest common divisor of a and b.

**Proof**

The proof follows from the property: if a = b q + r, then (a, b) = (b, r). Thus, if b divides a then a = b q + 0 and so (a, b) = (b, 0) = b. Also, as in the statement of the proposition,

(a, b) = (b, r_{0}) = (r_{0, }r_{1}) =_{ ... }= (r_{k-2,}r_{k-1}) =(r_{k-1,}r_{k}) = (r_{k,0}) = r_{k}.

Find the HCF of 274170 and 17017.

274170= 17017 x 16 + 1898

**Answer:** 17017