Question

a. Let C and d be two positive integers such that C = dq +r, where 0 <r<d, then HCF (c, d) = HCF what? give quick answer

Х​

Answer 1

Given: Two positive integers c and d, there exist unique integers q and r satisfying c = dq + r, 0 ≤ r < d.

To Find: HCF (c, d) is equal to

Solution:

Step 1: Apply Euclid’s division lemma, to c and d. So, we find whole numbers, q and r such that c = dq + r, 0 ≤ r < d.

Step 2: If r = 0, d is the HCF of c and d. If r ≠ 0, apply the division lemma to d and r.

Step 3 : Continue the process till the remainder is zero. The divisor at this stage will be the required HCF.

This algorithm works because HCF (c, d) = HCF (d, r) where the symbol HCF (c, d) denotes the HCF of c and d, etc.