Question

Use Euclid's division algorithm to find the HCF of

$\left(1\right)135\text{and}225$

$\left(2\right)196\text{and}38220$

$\left(3\right)867\text{and}255$

Answer 1

Euclid's Division Lemma:

If $a,b$ are two positive integers then there would be the whole numbers $p,q$ satisfies the equation $a=bq+r$ where $0\le r<b$.

$\left(1\right)135\text{and}225$

Now, $225>135$

$\therefore 225=135\times 1+90$

As, $r\ne 0$ and $135>90$

$\therefore 135=90\times 1+45$

As, $r\ne 0$ and $90>45$

$\therefore 90=45\times 2+0$

As, $r=0$

Hence, HCF of $135$ and $225$ is $45$.

$\left(2\right)196\text{and}38220$

Now, $38220>196$

$\therefore 38220=196\times 195+0$

As, $r=0$

Hence, HCF of $196$ and $38220$ is $196$.

$\left(3\right)867\text{and}255$

Now, $867>225$

$\therefore 867=225\times 3+192$

As, $r\ne 0$ and $225>192$

$\therefore 225=192\times 1+33$

As, $r\ne 0$ and $192>33$

$\therefore 192=33\times 5+27$

As, $r\ne 0$ and $33>27$

$\therefore 33=27\times 1+6$

As, $r\ne 0$ and $27>6$

$\therefore 27=6\times 4+3$

As, $r\ne 0$ and $6>3$

$\therefore 6=3\times 2+0$

As, $r=0$

Hence, HCF of $867$ and $225$ is $3$.