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 :

Show that the square of any positive integer cannot be of the form 6m + 2 or 6m + 5 for any integer m.

NCERT - Maths ExemplarShow that the square of any integer is of the form 4m + 1, for some integer m.

NCERT - Maths ExemplarShow that every positive odd integer is of the form (4q + 1) or (4q + 3) for some integer q.

RS Aggarwal - MathematicsUse Euclid’s division algorithm to find the HCF of 441, 567 and 693.

NCERT - Maths ExemplarUsing Euclid’s division algorithm, find the largest number that divides 1251, 9377 and 15628 leaving remainders 1, 2 and 3, respectively.

NCERT - Maths Exemplar