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.