Using Euclid’s algorithm, find the HCF of 960 and 1575.

1.	Using Euclid’s algorithm, find the HCF of 960 and 1575.
Answer» Step 1: Choose bigger number: 1575 > 960 On dividing 1575 by 960, we have Quotient = 1, remainder = 615 1575 = 960 x 1 + 615 Step 2: On dividing 960 by 615, we have Quotient = 1 and Remainder = 345 960 = 615 × 1 + 345 Step 3: On dividing 615 by 345 Quotient = 1 and Remainder = 270 615 = 345 × 1 + 270 Step 4: On dividing 345 by 270, we have Quotient = 1 and Remainder = 75 345 = 270 × 1 + 75 Step 5: Dividing 270 by 75, we get Quotient = 3, remainder =45 270 = 75 × 3 + 45 Step 6: Dividing 75 by 45, we get Quotient = 1, remainder = 30 75 = 45 × 1 + 30 Step 7: Dividing 45 by 30, we get Quotient = 1 and Remainder = 15 45 = 30 × 1 + 15 Step 8: Dividing 30 by 15, we get Quotient = 2 and Remainder = 0 Since remainder is zero, stop the process and write your answer. Therefore, H.C.F. of 1575 and 960 is 15.

Answer»

Step 1: Choose bigger number: 1575 > 960

On dividing 1575 by 960, we have

Quotient = 1, remainder = 615

1575 = 960 x 1 + 615

Step 2: On dividing 960 by 615, we have

Quotient = 1 and Remainder = 345

960 = 615 × 1 + 345

Step 3: On dividing 615 by 345

Quotient = 1 and Remainder = 270

615 = 345 × 1 + 270

Step 4: On dividing 345 by 270, we have

Quotient = 1 and Remainder = 75

345 = 270 × 1 + 75

Step 5: Dividing 270 by 75, we get

Quotient = 3, remainder =45

270 = 75 × 3 + 45

Step 6: Dividing 75 by 45, we get

Quotient = 1, remainder = 30

75 = 45 × 1 + 30

Step 7: Dividing 45 by 30, we get

Quotient = 1 and Remainder = 15

45 = 30 × 1 + 15

Step 8: Dividing 30 by 15, we get

Quotient = 2 and Remainder = 0

Since remainder is zero, stop the process and write your answer.

Therefore, H.C.F. of 1575 and 960 is 15.

Discussion