. Using Euclids division algorithm find the HCF of 135 and 225

Best Answer


According to Euclid's division algorithm if we have two positive integers a and b, then there exist unique

integers q and r which satisfies the condition a = bq + r where 0 ≤ r < b. That means, on dividing both the integers a and b the remainder is zero.

Given numbers are 135 and 225,

Here, 225>135

Applying Euclid’s division lemma to 225 and 135


Since the remainder is not equal to 0. So we apply the division lemma to the divisor 135 and remainder 90


Apply the division lemma to the new divisor 90 and remainder 45


Since the remainder is 0, the divisor will be the HCF(45).

Final Answer:

Hence, the HCF of 135 and 225 is 45.


Talk to Our counsellor