Question

Using Euclid's algortihm, find the HCF of

(i) 405 and 2520
(ii) 504 and 1188
(iii) 960 and 1575

Answer 1

(i)

On applying Euclid's algorithm, i.e. dividing 2520 by 405, we get:
Quotient = 6, Remainder = 90
∴ 2520 = 405 $\times$ 6 + 90
Again on applying Euclid's algorithm, i.e. dividing 405 by 90, we get:
Quotient = 4, Remainder = 45
∴ 405 = 90 $\times$ 4 + 45
Again on applying Euclid's algorithm, i.e. dividing 90 by 45, we get:
∴ 90 = 45 $\times$ 2 + 0

Hence, the HCF of 2520 and 405 is 45.

(ii)

On applying Euclid's algorithm, i.e. dividing 1188 by 504, we get:
Quotient = 2, Remainder = 180
∴ 1188 = 504 $\times$ 2 +180
Again on applying Euclid's algorithm, i.e. dividing 504 by 180, we get:
Quotient = 2, Remainder = 144
∴ 504 = 180$\times$ 2 + 144
Again on applying Euclid's algorithm, i.e. dividing 180 by 144, we get:
Quotient = 1, Remainder = 36
∴ 180 = 144 $\times$ 1 + 36
Again on applying Euclid's algorithm, i.e. dividing 144 by 36, we get:
∴ 144 = 36 $\times$ 4 + 0

Hence, the HCF of 1188 and 504 is 36.

(iii)

On applying Euclid's algorithm, i.e. dividing 1575 by 960, we get:
Quotient = 1, Remainder = 615
∴ 1575 = 960 $\times$ 1 + 615
Again on applying Euclid's algorithm, i.e. dividing 960 by 615, we get:
Quotient = 1, Remainder = 345
∴ 960 = 615 $\times$ 1 + 345
Again on applying Euclid's algorithm, i.e. dividing 615 by 345, we get:
Quotient = 1, Remainder = 270
∴ 615 = 345 $\times$ 1 + 270
Again on applying Euclid's algorithm, i.e. dividing 345 by 270, we get:
Quotient = 1, Remainder = 75
∴ 345 = 270 $\times$ 1 + 75
Again on applying Euclid's algorithm, i.e. dividing 270 by 75, we get:
Quotient = 3, Remainder = 45
∴270 = 75 $\times$ 3 + 45
Again on applying Euclid's algorithm, i.e. dividing 75 by 45, we get:
Quotient = 1, Remainder = 30
∴ 75 = 45 $\times$ 1 + 30
Again on applying Euclid's algorithm, i.e. dividing 45 by 30, we get:
Quotient = 1, Remainder = 15
∴ 45 = 30 $\times$ 1 + 15
Again on applying Euclid's algorithm, i.e. dividing 30 by 15, we get:
Quotient = 2, Remainder = 0
∴ 30 = 15 $\times$ 2 + 0

Hence, the HCF of 960 and 1575 is 15.