# Using Euclid’s algorithm, find the HCF of (i) 405 and 2520 (ii) 504 and 1188 (iii) 960 and 1575

739 views

closed

Using Euclid’s algorithm, find the HCF of

(i) 405 and 2520

(ii) 504 and 1188

(iii) 960 and 1575

+1 vote
by (33.5k points)
selected by

(i) On applying Euclid’s algorithm, i.e. dividing 2520 by 405, we get:

Quotient = 6, Remainder = 90

∴ 2520 = 405 × 6 + 90

Again on applying Euclid’s algorithm, i.e. dividing 405 by 90, we get:

Quotient = 4, Remainder = 45

∴ 405 = 90 × 4 + 45

Again on applying Euclid’s algorithm, i.e. dividing 90 by 45, we get:

∴ 90 = 45 × 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 × 2 + 180

Again on applying Euclid’s algorithm, i.e. dividing 504 by 180, we get:

Quotient = 2, Remainder = 144

∴ 504 = 180 × 2 + 144 Again on applying Euclid’s algorithm, i.e. dividing 180 by 144, we get:

Quotient = 1, Remainder = 36

∴ 180 = 144 × 1 + 36

Again on applying Euclid’s algorithm, i.e. dividing 144 by 36, we get:

∴ 144 = 36 × 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 × 1 + 615

Again on applying Euclid’s algorithm, i.e. dividing 960 by 615, we get:

Quotient = 1, Remainder = 345

∴ 960 = 615 × 1 + 345

Again on applying Euclid’s algorithm, i.e. dividing 615 by 345, we get:

Quotient = 1, Remainder = 270

∴ 615 = 345 × 1 + 270

Again on applying Euclid’s algorithm, i.e. dividing 345 by 270, we get:

Quotient = 1, Remainder = 75

∴ 345 = 270 × 1 + 75

Again on applying Euclid’s algorithm, i.e. dividing 270 by 75, we get:

Quotient = 3, Remainder = 45

∴ 270 = 75 × 3 + 45

Again on applying Euclid’s algorithm, i.e. dividing 75 by 45, we get:

Quotient = 1, Remainder = 30

∴ 75 = 45 × 1 + 30

Again on applying Euclid’s algorithm, i.e. dividing 45 by 30, we get:

Quotient = 1, Remainder = 15

∴ 45 = 30 × 1 + 15

Again on applying Euclid’s algorithm, i.e. dividing 30 by 15, we get:

Quotient = 2, Remainder = 0

∴ 30 = 15 × 2 + 0

Hence, the HCF of 960 and 1575 is 15.