Question

Using Euclid’s division algorithm, find the HCF of

405 and 2520

Answer 1

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.