Using Euclid's division algorithm, find the H.C.F. of 196 and 38220
Solution 1
Starting with larger number 38220, we get:
By Euclid's division algorithm, we have
38220 = 196 x 195 + 0
Since, the remainder is 0
∴ H.C.F. = 196
Solution 2
Step 1: Since 867 > 255, apply Euclid’s division
Lemma a to a = 867 = 255 q + r, 0 < r < 255
On dividing 867 by 255 we get quotient as 3 and the remainder as low
Step 2: Since the remainder 102 to, we apply the division lemma to a = 255 and b = 102 to find 255 = 102q + 51 = 102r – 151
Step 3: Again remainder 0 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 = q = r when 0 ≤ r < 51
On dividing 102 by 51 quotient = 2 and remainder is ‘0’
i,e., = 102 = 51 × 2 + 0
Since the remainder is zero, the divisional this stage is the HCF.
Since the divisor at this stage is 51, ∴ HCF of 867 and 255 is ‘51’.
