Using Euclid's algorithm, find the HCF of (i) 960 and 1575

Home » Using Euclid’s algorithm, find the HCF of (i) 960 and 1575

Using Euclid’s algorithm, find the HCF of
(i) 960 and 1575

CBSE | Class 10 | Exercise 1A | Real Numbers | RS Aggarwal

Using Euclid’s algorithm, find the HCF of
(i) 960 and 1575

Solution:

(i)

On applying Euclid’s division algorithm, that is dividing 1575 by 960, we obtain:
Quotient $= 1$ , Remainder $= 615$
$\therefore 1575 = 960 \times 1 + 615$
Again on applying Euclid’s division algorithm, that is dividing 960 by 615, we obtain:
Quotient $= 1$ , Remainder $= 345$
$\therefore 960 = 615 \times 1 + 345$
Again on applying Euclid’s division algorithm, that is dividing 615 by 345, we obtain:
Quotient $= 1$ , Remainder $= 270$
$\therefore 615 = 345 \times 1 + 270$
Again on applying Euclid’s division algorithm, that is dividing 345 by 270, we obtain:
Quotient $= 1$ , Remainder $= 75$
$\therefore 345 = 270 \times 1 + 75$
Again on applying Euclid’s division algorithm, that is dividing 270 by 75, we obtain:
Quotient $= 3$ , Remainder $= 45$
$\therefore 270 = 75 \times 3 + 45$
Again on applying Euclid’s division algorithm, that is dividing 75 by 45, we obtain:
Quotient $= 1$ , Remainder $= 30$
$\therefore 75 = 45 \times 1 + 30$
Again on applying Euclid’s division algorithm, that is dividing 45 by 30, we obtain:
Quotient $= 1$ , Remainder $= 15$
$\therefore 45 = 30 \times 1 + 15$
Again on applying Euclid’s division algorithm, that is dividing 30 by 15, we obtain:
Quotient $= 2$ , Remainder $= 0$
$\therefore 30 = 15 \times 2 + 0$
As a result, the HCF of 960 and 1575 is 15.