Question

Use Euclids division algorithm to find the HCF of:

(i) $135$ and $225$

(ii) $196$ and $38220$

(iii) $867$ and $225$

Answer 1

(i) $135$ and $225$

Step 1: First find which integer is larger.

$225>135$

Step 2: Then apply the Euclid's division algorithm to $225$ and $135$ to obtain

$225=135\times 1+90$

Repeat the above step until you will get remainder as zero.

Step 3: Now consider the divisor $135$ and the remainder $90,$ and apply the division lemma to get

$135=90\times 1+45$

$90=2\times 45+0$

Since the remainder is zero, we cannot proceed further.

Step 4: Hence, the divisor at the last process is $45$

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

(ii) $196$ and $38220$

Step 1: First find which integer is larger.

$38220>196$

Step 2: Then apply the Euclid's division algorithm to 38220 and 196 to obtain

$38220=196\times 195+0$

Since the remainder is zero, we cannot proceed further.

Step 3: Hence, the divisor at the last process is 196.

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

(iii) $867$ and $225$

Step 1: First find which integer is larger.

$867>255$

Step 2: Then apply the Euclid's division algorithm to $867$ and $255$ to obtain

$867=255\times 3+102$

Repeat the above step until you will get remainder as zero.

Step 3: Now consider the divisor $225$ and the remainder $102,$ and apply the division lemma to get

$255=102\times 2+51$

$102=51\times 2=0$

Since the remainder is zero, we cannot proceed further.

Step 4: Hence the divisor at the last process is 51.

So, the H.C.F. of $867$ and $255$ is $51.$