Question

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

$36575,2223,1330$

Answer 1

Finding HCF of $36575,2223,1330$:

Euclid's division algorithm: For any given positive integers $a$ and $b$ there exist unique integers $q$ and $r$ satisfying $a=bq+r,0\le r<b$

$HCF(36575,2223,1330)=HCF\left(HCF\right(36575,2223),1330)$

Finding HCF of $36575,2223$:

Since $36575>2223$ We apply Euclid's division algorithm,

$36575=2223\times 16+1007$

Since remainder $1007$≠$0$, so we again apply Euclid's division algorithm

$2223=1007\times 2+209$

Since remainder, $209$≠$0$, so we again apply Euclid's division algorithm

$1007=209\times 4+171$

Since remainder, $171$≠$0$, so we again apply Euclid's division algorithm

$209=171\times 1+38$

$171=38\times 4+19$

$38=19\times 2+0$

Therefore, HCF $(36575,2223)$=19

Now, $HCF(36575,2223,1330)=HCF\left(HCF\right(36575,2223),1330)$

Therefore, $HCF(36575,2223,1330)=HCF(19,1330)$

Since $1330>19$ we apply Euclid's division algorithm

$1330=19\times 70+0$

Here, Remainder = 0

Hence, the HCF $(36575,2223,1330)=19$