Let a and b be any two positive integers. Then there exist two unique whole numbers a and b such that

a=bq + r, 0<= r < b

a is dividend

b is divisor

q is quotient

r is remainder

Euclid’s division Algorithm is based on this lemma.

It is a technique to compute HCF of two positive integers c and d where c > d.

Step 1. Apply Euclids Division Lemma to c and d, find whole numbers q and r such that c=dq+r, 0 <= r < d.

Step 2. If r = 0, then HCF (c,d) is d.

If r is not equal to zero, apply Euclids Division Lemma to d and r.

Step 3. Continue this process till we get the remainder as zero. The divisor at this step gives the required HCF.