# 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 $225 .$

Solution:

(i) 135 and $225 .$

Start with the larger integer, that is, 225. Apply the division lemma to 225 and 135, to get.

$225=135 \times 1+90$

Since the remainder $90 \neq 0$, we apply the division lemma to 135 and 90 to get

$135=90 \times 1+45$

We consider the new divisior 90 and the new remainder 45, and apply the division lemma to get

$90=45 \times 2+0$

The remainder has now become zero, so our procedure stops. Since the divisor at this stage is 45, the HCF of 225 and 135 is 45

(ii) 196 and 38220

Start with the larger integer, that is, 38220. Apply the division lemma to 38220 and 196, to get

$38220=196 \times 195+0$

Remainder at this stage is zero, so our procedure stops.

So, HCF of 196 and 38220 is 196.

(iii) 867 and 225

Start with the larger integer, that is, 867. Apply the division lemma to 867 and 225, to get.

$867=225 \times 3+192$

Since the remainder $192 \neq 0$, we apply the division lemma to 225 and 192 to get

$225=192 \times 1+33$

Since the remainder $33 \neq 0$, we apply the division lemma to 33 and 27 to get

$192=33 \times 5+27$

Since the remainder $27 \neq 0$, we apply the division lemma to 27 and 6 to get

$33=27 \times 1+6$

Since the remainder $6 \neq 0$, we apply the division lemma to 6 and 3 to get

$27=6 \times 4+3$

Since the remainder $3 \neq 0$, we apply the division lemma to 6 and 3 to get

$6=3 \times 2+0$

Now, remainder at this stage is zero, so our procedure stops.

So, HCF of 867 and 225 is 3.