Question

Using Eculid's division algorithm, find the HCF of:
a) 4052 and 12576
b) 615 and 154

Answer 1

SOLUTION

To Find:

Use Euclid’s Division Algorithm to find the HCF of:

• a) 4052 and 12576
• b) 615 and 154

Euclid’s Division Algorithm:

• a = bq + r

Where,

• ‘a’ and ‘b’ are positive integers.
• q = Quotient
• r = Remainder

Finding the HCF of 4052 and 12576:

Dividing 12576 by 4052.

→ 12576 = 4052 × 3 + 420

Here, Quotient = 3 and Remainder = 420

Dividing 4052 by 420.

→ 4052 = 420 × 9 + 272

Here, Quotient = 9 and Remainder = 272

Dividing 420 by 272.

→ 420 = 272 × 1 + 148

Here, Quotient = 1 and Remainder = 148

Dividing 272 by 148.

→ 272 = 148 × 1 + 124

Here, Quotient = 1 and Remainder = 124

Dividing 148 by 124.

→ 148 = 124 × 1 + 24

Here, Quotient = 1 and Remainder = 24

Dividing 124 by 24.

→ 124 = 24 × 5 + 4

Here, Quotient = 5 and Remainder = 4

Dividing 24 by 4

→ 24 = 4 × 6 + 0

Here, Quotient = 6 and Remainder = 0

Hence,

• The HCF of 4052 and 12576 is 4.

Finding the HCF of 615 and 154:

Dividing 615 by 154.

→ 615 = 154 × 3 + 153

Here, Quotient = 3 and Remainder = 153

Dividing 154 by 153.

→ 154 = 153 × 1 + 1

Here, Quotient = 1 and Remainder = 1

Dividing 153 by 1.

→ 153 = 1 × 153 + 0

Here, Quotient = 153 and Remainder = 0

Hence,

• The HCF of 615 and 154 is 1.