What do you mean by Euclid's division lemma ?

1.	What do you mean by Euclid's division lemma ?
Answer» ≡QUESTION≡ What do you mean by Euclid's division lemma ? ║⊕ANSWER⊕║ It states that: Given positive integers m and n, there exist TWO unique integers q and R, satisying m = nq + r, where 0 ≤ r < n. EXAMPLE Find the HCF of 6 and 9 using the Euclidean division algorithm. SOLUTION The larger integer is 9 THEREFORE applying the Division Lemma m = nq + r where 0 ≤ r ≤ n, we have a = 9 and b = 6 ⇒ 9 = 6 × 1 + 3 Applying the Euclid’s Division Algorithm again we have, ⇒6 = 3 × 2 + 0 We cannot proceed further as the remainder becomes ZERO. According to the algorithm, DIVISOR in this case is 3 which is the HCF of 6 and 9 .