Question

write the steps of Euclid division algorithm​

Answer 1

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.

Answer 2

Let us state Euclid’s division algorithm clearly.

To obtain the HCF of two positive integers, say c and d, with c > d, follow the steps below:

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.

---------------------------------------------------------------------------

Examples :

1) Use Euclid’s algorithm to find the 420 and 130.

Solution :

Step:1 Since 420 > 130 we apply the division lemma to 420 and 130 to get ,

420 = 130 x 3 + 30

Step:2 Since 30 ≠ 0 , we apply the division lemma to 130 and 30 to get

130 = 30 x 4 + 10

Step:3 Since 10 ≠ 0 , we apply the division lemma to 30 and 10 to get

30 = 10 x 3 + 0

The remainder has now become zero, so our procedure stops. Since the divisor at this Step is 10, the HCF of 420 and 130 is 10.