Use Euclid’s division algorithm to find the HCF of 196 and 38220.

Given: The numbers 196 and 38220

To find: H.C.F of 196 and 38220

Concept Used:

Euclid's division lemma:

If there are two positive integers a and b,

then there exist unique integers q and r such that,

a = bq + r where 0 ≤ r ≤ b.

Explanation:

196 and 38220

Step 1: Since 38220 > 196, apply Euclid's division lemma

let a =38220 and b=196 to find whole numbers q and r such that

Using Euclid's division lemma

38220 = 196 q + r, (0≤r<196)

On dividing 38220 we get quotient as 195 and remainder r as 0

i.e. 38220 = 196 × 195 + 0

Since the remainder is zero therefore divisor at this stage is HCF of 196 and 38220 is 196.