Using Euclid's algorithm, find the HCF of (i) 405 and 2520 (ii) 504 and 1188

Home » Using Euclid’s algorithm, find the HCF of (i) 405 and 2520 (ii) 504 and 1188

Using Euclid’s algorithm, find the HCF of
(i) 405 and 2520
(ii) 504 and 1188

Using Euclid’s algorithm, find the HCF of
(i) 405 and 2520
(ii) 504 and 1188

Solution:

(i)

When applying Euclid’s algorithm, that is dividing $2520$ by $405$ , we obtain,
Quotient $=6$ , Remainder $=90$
$\therefore 2520=405 \times 6+90$
Again upon applying Euclid’s algorithm, that is dividing $405$ by $90$ , we obtain
Quotient $=4$ , Remait $\therefore 405=90 \times 4+45$
Again applying Euclid’s algorithm, that is dividing $90$ by $45$ , we obtain;
$\therefore 90=45 \times 2+0$
As a result, the HCF of 2520 and 405 is 45 .

Upon applying Euclid’s algorithm, that is dividing $1188$ by $504$ , we obtain:
$\begin{array}{l} \text { Quotient }=2, \text { Remainder }=180 \\ \therefore 1188=504 \times 2+180 \end{array}$
$\begin{array}{l} \text { Quotient }=2, \text { Remainder }=144 \\ \therefore 504=180 \times 2+144 \end{array}$
Again applying Euclid’s algorithm, that is dividing $180$ by $144$ , we obtain
$\begin{array}{l} \text { Quotient }=1, \text { Remainder }=36 \\ \therefore 180=144 \times 1+36 \end{array}$
Again upon applying Euclid’s algorithm, that is dividing $144$ by $36$ , we obtain:
$\therefore 144=36 \times 4+0$
As a result, the HCF of 1188 and 504 is 36 .