# Use Euclid's division algorithm to find the HCF of

Question:

Use Euclid's division algorithm to find the HCF of

(i) 135 and 225

(ii) 196 and 38220

(iii) 867 and 255

(iv) 184, 230 and 276

(v) 136, 170 and 255

(vi) 1260 and 7344

(vii) 2048 and 960

Solution:

(i) Given integers are 225 and 135. Clearly 225 > 135. So we will apply Euclid’s division lemma to 225 and 135, we get,

$867=(225)(3)+192$

Since the remainder $90 \neq 0 .$ So we apply the division lemma to the divisor 135 and remainder $90 .$ We get, $135=(90)(1)+45$

Now we apply the division lemma to the new divisor 90 and remainder 45 . We get, $90=(45)(2)+0$

The remainder at this stage is 0. So the divisor at this stage is the H.C.F.

So the H.C.F of 225 and 135 is 45

(ii) Given integers are 38220 and 196 . Clearly $38220>196$. So we will apply Euclid's division lemma to 38220 and 196, we get, $38220=(196)(195)+0$

The remainder at this stage is 0. So the divisor at this stage is the H.C.F.

So the H.C.F of 38220 and 196 is 196

(iii) Given integers are 867 and 255 . Clearly $867>225$. So we will apply Euclid's division lemma to 867 and 225, we get, $867=(225)(3)+192$

Since the remainder $192 \neq 0$. So we apply the division lemma to the divisor 225 and remainder 192 . We get, $225=(192)(1)+33$

Now we apply the division lemma to the new divisor 192 and remainder 33 . We get, $192=(33)(5)+27$

Now we apply the division lemma to the new divisor 33 and remainder $27 .$ We get, $33=(27)(1)+6$

Now we apply the division lemma to the new divisor 27 and remainder 6 . We get, $27=(6)(4)+3$

Now we apply the division lemma to the new divisor 6 and remainder 3 . We get, $6=(3)(2)+0$

The remainder at this stage is 0. So the divisor at this stage is the H.C.F.

So the H.C.F of 867 and 255 is 3.

(iv) Given integers are 184, 230 and 276.

Let us first find the HCF of 184 and 230 by Euclid lemma.

Clearly, 230 > 184. So, we will apply Euclid’s division lemma to 230 and 184.

$230=184 \times 1+46$

Remainder is 46 which is a non-zero number. Now, apply Euclid’s division lemma to 184 and 46.

$230=184 \times 1+46$

The remainder at this stage is zero. Therefore, 46 is the HCF of 230 and 184.

Now, again use Euclid’s division lemma to find the HCF of 46 and 276.

$276=46 \times 6+0$

The remainder at this stage is zero. Therefore, 46 is the HCF of 184, 230 and 276.

(v) Given integers are 136, 170 and 255.

Let us first find the HCF of 136, 170 by Euclid lemma.

Clearly, 170 > 136. So, we will apply Euclid’s division lemma to 136 and 170.

$170=136 \times 1+34$

Remainder is 34 which is a non-zero number. Now, apply Euclid’s division lemma to 136 and 34.

$136=34 \times 4+0$

The remainder at this stage is zero. Therefore, 34 is the HCF of 136 and 170.

Now, again use Euclid’s division lemma to find the HCF of 34 and 255.

$255=34 \times 7+17$

Remainder is 17 which is a non-zero number. Now, apply Euclid’s division lemma to 34 and 17.

$34=17 \times 2+0$

The remainder at this stage is zero. Therefore, 17 is the HCF of 136, 170 and 255.

(vi) 1260 and 7344

1260 < 7344

Thus, we divide 7344 by 1260 by using Euclid's division lemma

$7344=1260 \times 5+1044$

∵ Remainder is not zero,

∴ we divide 1260 by 1044 by using Euclid's division lemma

$1260=1044 \times 1+216$

∵ Remainder is not zero,

∴ we divide 1044 by 216 by using Euclid's division lemma

$216=180 \times 1+36$

∵ Remainder is not zero,

∴ we divide 180 by 36 by using Euclid's division lemma

$180=36 \times 5+0$

Since, Remainder is zero

Hence, HCF of 1260 and 7344 is 36.

(vii) 2048 and 960

2048 > 960

Thus, we divide 2048 by 960 by using Euclid's division lemma

$2048=960 \times 2+128$

∵ Remainder is not zero,

∴ we divide 960 by 128 by using Euclid's division lemma

$960=128 \times 7+64$

∵ Remainder is not zero,

∴ we divide 128 by 64 by using Euclid's division lemma

$128=64 \times 2+0$

Since, Remainder is zero

Hence, HCF of 2048 and 960 is 64.