Question 28

Use Euclid division algorithm to find the HCF of 441, 567 and 693.

Solution:

To find the HCF (Highest Common Factor) of the numbers 441, 567, and 693 using the Euclidean division algorithm, we will follow these steps:

Step 1: Find HCF of 567 and 693

1. Identify the numbers: Let $$a=693$$ and $$b=567$$.
2. Apply the Euclidean division algorithm:
$$a=bq+r$$
where $$q$$ is the quotient and $$r$$ is the remainder.

We divide 693 by 567:
$$693=567\times 1+126$$
Here, $$q=1$$ and $$r=126$$.

Step 2: Repeat with 567 and 126

3. Now, we take $$a=567$$ and $$b=126$$:
$$567=126q+r$$
Dividing 567 by 126:
$$567=126\times 4+63$$
Here, $$q=4$$ and $$r=63$$.

Step 3: Repeat with 126 and 63

4. Next, we take $$a=126$$ and $$b=63$$:
$$126=63q+r$$
Dividing 126 by 63:
$$126=63\times 2+0$$
Here, $$q=2$$ and $$r=0$$.

Since the remainder is now 0, we conclude that the HCF of 567 and 693 is $$63$$.

Step 4: Find HCF of 441 and 63

5. Now, we need to find the HCF of 441 and 63:
Let $$a=441$$ and $$b=63$$:
$$441=63q+r$$
Dividing 441 by 63:
$$441=63\times 7+0$$
Here, $$q=7$$ and $$r=0$$.

Since the remainder is 0, the HCF of 441 and 63 is $$63$$.

Conclusion

Thus, the HCF of 441, 567, and 693 is 63.