Question

Use Euclid’s Division Algorithm to find the HCF of 10244 and 9648.

Answer 1

Given :

• 10244 and 9648.

To find :

• HCF of 10244 and 9648 by using Euclid’s Division Algorithm.

Step-by-step explanation :

Clearly, 10244 > 9648

Applying the Euclid's division lemma to 10244 and 9648, we get

10244 = 9648 x 1 + 596

Since the remainder 596 ≠ 0, we apply the Euclid's division lemma to divisor 9648 and remainder 596 to get

9648 = 596 x 16 + 112

We consider the new divisor 596 and remainder 112 and apply the division lemma to get

596 = 112 x 5 + 36

We consider the new divisor 112 and remainder 36 and apply the division lemma to get

112 = 36 x 3 + 4

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

36 = 4 x 9 + 0

Now, the remainder at this stage is 0.

So, the divisor at this stage, ie, 4 is the HCF of 10244 and 9648.