Question

Using Euclid’s division algorithm, find the HCF of
504 and 1188

Answer 1

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.