Question

Using Euclid's division algorithm, find the H.C.F. of 196 and 38220

Answer 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

Answer 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’.