Using Euclid's division algorithm, find the H.C.F. of 135 and 225
Solution 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
Solution 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.
