Question

Using Euclid's division algorithm, find the H.C.F. of 135 and 225

Answer 1

Starting with the larger number i.e., 225, we get

225 = 135 x 1 + 90

Now taking divisor 135 and remainder 90, we get

135 = 90 x 1 + 45

Further taking divisor 90 and remainder 45, we get

90 = 45 x 2 + 0

∴ Required H.C.F. = 45

Answer 2

Step 1: Since 225 > 135. Apply Euclid’s division lemma to a = 225 and b = 135 to find q and r such that 225 = 135q + r, 0 ≤ r < 135

On dividing 225 by 135 we get quotient as 1 and remainder as ‘90’

i.e., 225 = 135r 1 + 90

Step 2: Remainder 5 which is 90 7, we apply Euclid’s division lemma to a = 135 and b = 90 to find whole numbers q and r such that 135 = 90 × q + r 0 ≤ r < 90 on dividing 135 by 90 we get quotient as 1 and remainder as 45

i.e., 135 = 90 × 1 + 45

Step3: Again remainder r = 45 to so we apply division lemma to a = 90 and b = 45 to find q and r such that 90 = 45 × q × r. 0 ≤ r < 45. On dividing 90 by 45we get quotient as 2 and remainder as 0

i.e., 90 = 2 × 45 + 0

Step 4: Since the remainder = 0, the divisor at this stage will be HCF of (135, 225)

Since the divisor at this stage is 45. Therefore the HCF of 135 and 225 is 45.