Q1 of 54 Page 5

Use Euclid’s division algorithm to find the HCF of

196 and 38220

Euclid’s Division is a method for finding the HCF (highest common factor) of two given integers. According to Euclid’s Division Algorithm, For any two positive integers, ‘a’ and ‘b’, there exists a unique pair of integers ‘q’ and ‘r’ which satisfy the relation:

a = bq + r , 0 ≤ r ≤ b


Given integers 196 and 38220. Clearly 38220>196.


By applying division lemma


⇒ 38220 = 196×195 + 0


Since remainder 0


∴ the HCF of 196 and 38220 is 195.


More from this chapter

All 54 →
1

Use Euclid’s division algorithm to find the HCF of

900 and 270

 1

Use Euclid’s division algorithm to find the HCF of

1651 and 2032

 2

Use Euclid division lemma to show that any positive odd integer is of form 6q + 1, or 6q + 3 or 6q + 5, where q is some integers.

 3

Use Euclid’s division lemma to show that the square of any positive integer is of the form 3p, 3p + 1 or 3p + 2.