Find the HCF (Highest Common Factor) of the following pairs of number by Euclid Division Algorithm:

75, 243

From the integers given in the question 243 and 75, it is observed that 243 > 75. So by Euclid’s Division Lemma we get the following:

243 = 75 × 3 + 18

Here the remainder is 18 which is not equal to zero. So applying Euclid’s Division Lemma on divisor 75 and remainder 18.

75 = 18 × 4 + 3

Here the remainder is 3 which is not equal to zero. So applying Euclid’s Division Lemma on divisor 18 and remainder 3.

18 = 3 × 6 + 0

So from the above relation is seen that remainder zero is obtained.

So the HCF of 243 and 75 is 3.

The entire process can be expressed in the following way: