Question

find the HCF of the following by using eculid algorithm : 2870 and 5180​

Answer 1

Step 1: Since 5180 > 2870, we apply the division lemma to 5180 and 2870, to get

5180 = 2870 x 1 + 2310

Step 2: Since the reminder 2870 ≠ 0, we apply division lemma to 2310 and 2870, to get

2870 = 2310 x 1 + 560

Step 3: We consider the new divisor 2310 and the new remainder 560, and apply the division lemma to get

2310 = 560 x 4 + 70

We consider the new divisor 560 and the new remainder 70, and apply the division lemma to get

560 = 70 x 8 + 0

The remainder has now become zero, so our procedure stops. Since the divisor at this stage is 70, the HCF of 2870 and 5180 is 70

Notice that 70 = HCF(560,70) = HCF(2310,560) = HCF(2870,2310) = HCF(5180,2870) .