Question

Find the HCF of 142, 637 using Euclid's algorithm. ​

Answer 1

Answer:

1

Step-by-step explanation:

Step 1: Since 637 > 142, we apply the division lemma to 637 and 142, to get

637 = 142 x 4 + 69

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

142 = 69 x 2 + 4

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

69 = 4 x 17 + 1

We consider the new divisor 4 and the new remainder 1, and apply the division lemma to get

4 = 1 x 4 + 0

The remainder has now become zero, so our procedure stops. Since the divisor at this stage is 1, the HCF of 142 and 637 is 1

Notice that 1 = HCF(4,1) = HCF(69,4) = HCF(142,69) = HCF(637,142) .