Use Euclid’s division algorithm to find the HCF of 135 and 225.
Solution: Given numbers are 135 and 225.
By applying Euclid’s division algorithm, we have
225 = 135 x 1 + 90
Since the remainder is 90 ≠ 0, so again we apply Euclid’s division algorithm to 135 and 90, to get
135 = 90 x 1 + 45
Since the remainder is 45 ≠ 0, so again we apply Euclid’s division algorithm to 90 and 45, to get
90 = 45 x 2 + 0
The remainder has now become zero, so we stop.
∵ At the last stage, the divisor is 45
∴ The HCF of 135 and 225 is 45.
