Question

Using Euclid’s division algorithm, 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

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.