# Use Euclid’s division algorithm to find the HCF of :(i) 135 and 225(ii) 196 and 38220(iii) 867 and 255

Concept used :
To obtain the HCF of two positive integers, say c and d, with c > d,we follow
the steps below:
Step 1 : Apply Euclid’s division lemma, to c and d. So, we find whole numbers, q and r such that c = dq + r, 0 ≤ r < d.
Step 2 : If r = 0, d is the HCF of c and d. If r ≠ 0, apply the division lemma to d and r.
Step 3 : Continue the process till the remainder is zero. The divisor at this stage will be the required HCF.

(i)  We know that,

= 225>135

Applying Euclid’s division algorithm:
(Dividend = Divisor × Quotient + Remainder)

225 = 135 ×1+90

Here remainder = 90,

So, Again Applying Euclid’s division algorithm

135 = 90×1+45

Here remainder = 45,

So, Again Applying Euclid’s division algorithm

90 = 45×2+0

Remainder = 0,

Hence,

HCF of (135, 225) = 45

(ii)
We know that,

38220>196

So, Applying Euclid’s division algorithm

38220 = 196×195+0 (Dividend = Divisor × Quotient + Remainder)

Remainder = 0

Hence,

HCF of (196, 38220) = 196

(iii)
We know that,

867>255

So, Applying Euclid’s division algorithm

867 = 255×3+102 (Dividend = Divisor × Quotient + Remainder)

Remainder = 102

So, Again Applying Euclid’s division algorithm

255 = 102×2+51

Remainder = 51

So, Again Applying Euclid’s division algorithm

102 = 51×2+0

Remainder = 0

Hence,

(HCF 0f 867 and 255) = 51

Rate this question :

How useful is this solution?
We strive to provide quality solutions. Please rate us to serve you better.
Related Videos  Interactive Quiz:Euclid's Division Lemma44 mins  Fundamental Theorem of Arithmetic-238 mins  NCERT | Imp. Qs. on Rational and Irrational Numbers44 mins  Champ Quiz | Fundamental Principle Of Arithmetic41 mins  Fundamental Theorem of Arithmetic- 143 mins  Euclids Division Lemma49 mins  Relation Between LCM , HCF and Numbers46 mins  Application of Euclids Division Lemma50 mins  Quiz | Fun with Fundamental Theorem of Arithmetic51 mins  Quiz | Imp Qs on Real Numbers37 mins
Try our Mini CourseMaster Important Topics in 7 DaysLearn from IITians, NITians, Doctors & Academic Experts
Dedicated counsellor for each student
24X7 Doubt Resolution
Daily Report Card
Detailed Performance Evaluation view all courses 