Use Euclid’s division algorithm to find the HCF of:
(i)135 and 225
(ii) 196 and 38220
(iii) 867 and 255
Solution:
(i) 135 and 225
Since 225 > 135, we apply the division lemma to 225 and 135 to obtain
225 = 135 x 1 + 90
Since remainder 90 ≠ 0, we apply the division lemma to 135 and 90 to obtain
135 = 90 x 1 + 45
We consider the new divisor 90 and new remainder 45, and apply the division lemma to obtain
90 = 2 x 45 + 0
Since the remainder is zero, the process stops.
Since the divisor at this stage is 45,
Therefore, the HCF of 135 and 225 is 45.
(ii)196 and 38220
Since 38220 > 196, we apply the division lemma to 38220 and 196 to obtain
38220 = 196 x 195 + 0
Since the remainder is zero, the process stops.
Since the divisor at this stage is 196,
Therefore, HCF of 196 and 38220 is 196.
(iii)867 and 255
Since 867 > 255, we apply the division lemma to 867 and 255 to obtain
867 = 255 x 3 + 102
Since remainder 102 ≠ 0, we apply the division lemma to 255 and 102 to obtain
255 = 102 x 2 + 51
We consider the new divisor 102 and new remainder 51, and apply the division lemma to obtain
102 = 51 x 2 + 0
Since the remainder is zero, the process stops.
Since the divisor at this stage is 51,
Therefore, HCF of 867 and 255 is 51.
