Using Euclid’s division algorithm, find the HCF of
(i) 405 and 2520 (ii) 504 and 1188 (iii) 960 and 1575
Using Euclid’s division algorithm, find the HCF of
(i) 405 and 2520 (ii) 504 and 1188 (iii) 960 and 1575
(i)
On applying Euclid’s algorithm, i.e. dividing 2520 by 405, we get:
Quotient = 6, Remainder = 90
Therefore, 2520 = 405 x 6 + 90
Again on applying Euclid’s algorithm, i.e. dividing 405 by 90, we get:
Quotient = 4, Remainder = 45
Therefore, 405 = 90 x 4 + 45
Again on applying Euclid’s algorithm, i.e. dividing 90 by 45, we get:
Therefore, 90 = 45 x 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
Therefore, 1188 = 504.2 +180
Again on applying Euclid’s algorithm, i.e. dividing 504 by 180, we get:
Quotient = 2, Remainder = 144
Therefore, 504 = 180x 2 + 144
Again on applying Euclid’s algorithm, i.e. dividing 180 by 144, we get:
Quotient = 1, Remainder = 36
Therefore, 180 = 144 x 1 + 36
Again on applying Euclid’s algorithm, i.e. dividing 144 by 36, we get:
Therefore, 144 = 36 x 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
Therefore, 1575 = 960 x 1 + 615
Again on applying Euclid’s algorithm, i.e. dividing 960 by 615, we get:
Quotient = 1, Remainder = 345
Therefore, 960 = 615 x 1 + 345
Again on applying Euclid’s algorithm, i.e. dividing 615 by 345, we get:
Quotient = 1, Remainder = 270
Therefore, 615 = 345 x 1 + 270
Again on applying Euclid’s algorithm, i.e. dividing 345 by 270, we get:
Quotient = 1, Remainder = 75
Therefore, 345 = 270 x 1 + 75
Again on applying Euclid’s algorithm, i.e. dividing 270 by 75, we get:
Quotient = 3, Remainder = 45
Therefore, 270 = 75 x 3 + 45
Again on applying Euclid’s algorithm, i.e. dividing 75 by 45, we get:
Quotient = 1, Remainder = 30
Therefore, 75 = 45 x 1 + 30
Again on applying Euclid’s algorithm, i.e. dividing 45 by 30, we get:
Quotient = 1, Remainder = 15
Therefore, 45 = 30 x 1 + 15
Again on applying Euclid’s algorithm, i.e. dividing 30 by 15, we get:
Quotient = 2, Remainder = 0
Therefore, 30 = 15 x 2 + 0
Hence, the H.C.F of 960 and 1575 is 15.
(i)
On applying Euclid’s algorithm, i.e. dividing 2520 by 405, we get:
Quotient = 6, Remainder = 90
Therefore, 2520 = 405 x 6 + 90
Again on applying Euclid’s algorithm, i.e. dividing 405 by 90, we get:
Quotient = 4, Remainder = 45
Therefore, 405 = 90 x 4 + 45
Again on applying Euclid’s algorithm, i.e. dividing 90 by 45, we get:
Therefore, 90 = 45 x 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
Therefore, 1188 = 504.2 +180
Again on applying Euclid’s algorithm, i.e. dividing 504 by 180, we get:
Quotient = 2, Remainder = 144
Therefore, 504 = 180x 2 + 144
Again on applying Euclid’s algorithm, i.e. dividing 180 by 144, we get:
Quotient = 1, Remainder = 36
Therefore, 180 = 144 x 1 + 36
Again on applying Euclid’s algorithm, i.e. dividing 144 by 36, we get:
Therefore, 144 = 36 x 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
Therefore, 1575 = 960 x 1 + 615
Again on applying Euclid’s algorithm, i.e. dividing 960 by 615, we get:
Quotient = 1, Remainder = 345
Therefore, 960 = 615 x 1 + 345
Again on applying Euclid’s algorithm, i.e. dividing 615 by 345, we get:
Quotient = 1, Remainder = 270
Therefore, 615 = 345 x 1 + 270
Again on applying Euclid’s algorithm, i.e. dividing 345 by 270, we get:
Quotient = 1, Remainder = 75
Therefore, 345 = 270 x 1 + 75
Again on applying Euclid’s algorithm, i.e. dividing 270 by 75, we get:
Quotient = 3, Remainder = 45
Therefore, 270 = 75 x 3 + 45
Again on applying Euclid’s algorithm, i.e. dividing 75 by 45, we get:
Quotient = 1, Remainder = 30
Therefore, 75 = 45 x 1 + 30
Again on applying Euclid’s algorithm, i.e. dividing 45 by 30, we get:
Quotient = 1, Remainder = 15
Therefore, 45 = 30 x 1 + 15
Again on applying Euclid’s algorithm, i.e. dividing 30 by 15, we get:
Quotient = 2, Remainder = 0
Therefore, 30 = 15 x 2 + 0
Hence, the H.C.F of 960 and 1575 is 15.
