Q. 14.1( 1418 Votes )

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

Answer :

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 LemmaInteractive Quiz:Euclid's Division LemmaInteractive Quiz:Euclid's Division Lemma44 mins
Fundamental Theorem of Arithmetic-2Fundamental Theorem of Arithmetic-2Fundamental Theorem of Arithmetic-238 mins
NCERT | Imp. Qs. on Rational and Irrational NumbersNCERT | Imp. Qs. on Rational and Irrational NumbersNCERT | Imp. Qs. on Rational and Irrational Numbers44 mins
Champ Quiz | Fundamental Principle Of ArithmeticChamp Quiz | Fundamental Principle Of ArithmeticChamp Quiz | Fundamental Principle Of Arithmetic41 mins
Fundamental Theorem of Arithmetic- 1Fundamental Theorem of Arithmetic- 1Fundamental Theorem of Arithmetic- 143 mins
Euclids Division LemmaEuclids Division LemmaEuclids Division Lemma49 mins
Relation Between LCM , HCF and NumbersRelation Between LCM , HCF and NumbersRelation Between LCM , HCF and Numbers46 mins
Application of Euclids Division LemmaApplication of Euclids Division LemmaApplication of Euclids Division Lemma50 mins
Quiz | Fun with Fundamental Theorem of ArithmeticQuiz | Fun with Fundamental Theorem of ArithmeticQuiz | Fun with Fundamental Theorem of Arithmetic51 mins
Quiz | Imp Qs on Real NumbersQuiz | Imp Qs on Real NumbersQuiz | 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
caricature
view all courses