0Euclid's Division Lemma:
Given positive integers a and b,there exist unique integers q and r satisfying a = bq + r, 0 ≤ r < b.
Euclid’s division algorithm is based on this Lemma.
Example: Suppose we need to find the HCF of the integers 455 and 42. We start with the larger integer, that is 455. Then we use Euclid’s Lemma to get:
455 = 42 * 10 + 35.
Now consider the divisor 42 and remainder 35 and apply the Division Lemma:
42 = 1 * 35 + 7.
Now consider the divisor 35 and remainder 7 and apply the Division Lemma.
35 = 5*7+0.
No remainder has become zero. So, we can not go further.
We consider 7 as the HCF of 455 and 42.
