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

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

Concept: Euclid’s Division Lemma
Is there an error in this question or solution?
Chapter 1: Real Numbers - Exercise 1.1 [Page 7]

#### APPEARS IN

NCERT Class 10 Maths
Chapter 1 Real Numbers
Exercise 1.1 | Q 1.2 | Page 7
RD Sharma Class 10 Maths
Chapter 1 Real Numbers
Exercise 1.2 | Q 2.2 | Page 27

Share