(i) Given numbers are 135 and 225. On applying Euclid’s division algorithm, we have 225 = 135 x 1 + 90 Since the remainder 90 ≠ 0, so again we apply Euclid’s division algorithm to 135 and 90, to get 135 = 90 x 1 + 45 Since the remainder 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. Alternatively: (i) By Euclid’s Division Algorithm, we have 225 = 135 x 1 + 90 135 = 90 x 1 + 45 90 = 45 x 2 + 0 ∴ HCF (135, 225) = 45. (ii) Given numbers are 196 and 38220 On applying Euclid’s division algorithm, we have 38220 = 196 x 195 + 0 Since we get the remainder zero in the first step, so we stop. ∵ At the above stage, the divisor is 196 ∴ The HCF of 196 and 38220 is 196. Alternatively: (ii) By Euclid’s Division Algorithm, we have 38220 = 196 x 195 + 0 196 = 196 x 1 + 0 ∴ HCF (38220, 196) = 196. (iii) Given numbers are 867 and 255 On applying Euclid’s division algorithm, we have 867 = 255 x 3 + 102 Since the remainder 102 ≠ 0, so again we apply Euclid’s division algorithm to 255 and 102. to get 255 = 102 x 2 + 51 Since the remainder 51 ≠ 0, so again we apply Euclid’s division algorithm to 102 and 51, to get 102 = 51 x 2 + 0 We find the remainder is 0 and the divisor is 51 ∴ The HCF of 867 and 255 is 51. Alternatively: (iii) 867 and 255 Step 1: Since 867 > 255, apply Euclid’s division lemma, to a =867 and b=255 to find q and r such that 867 = 255q + r, 0 ≤ r<255 On dividing 867 by 255 we get quotient as 3 and remainder as 102 i.e 867 = 255 x 3 + 102 Step 2: Since remainder 102 ≠ 0, we apply the division lemma to a=255 and b= 102 to find whole numbers q and r such that 255 = 102q + r where 0 ≤ r<102 On dividing 255 by 102 we get quotient as 2 and remainder as 51 i.e 255 = 102 x 2 + 51 Step 3: Again remainder 51 is non zero, so we apply the division lemma to a=102 and b= 51 to find whole numbers q and r such that 102 = 51 q + r where 0 r < 51 On dividing 102 by 51 quotient is 2 and remainder is 0 i.e 102 = 51 x 2 + 0 Since the remainder is zero, the divisor at this stage is the HCF Since the divisor at this stage is 51,therefore, HCF of 867 and 255 is 51. Concept Insight: To crack such problem remember to apply Euclid’s division Lemma which states that “Given positive integers a and b, there exist unique integers q and r satisfying a = bq + r, where 0 ≤ r < b” in the correct order. Here, a > b. Euclid’s algorithm works since Dividing ‘a’ by ‘b’, replacing ‘b’ by ‘r’ and ‘a’ by ‘b’ and repeating the process of division till remainder 0 is reached, gives a number which divides a and b exactly. i.e HCF(a,b) =HCF(b,r)