Use Euclid's division algorithm to find the HCF of

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 × 1 + 46

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

184 = 46 × 4 + 0

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 × 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 × 1 + 34

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

136 = 34 × 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 × 7 +17

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

34 = 17 × 2 + 0

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