Use Euclid's algorithm to find HCF of 4052 and 12576

Question

Use Euclid’s Division Algorithm to find the HCF of 4052 and 12576.

Solution — Step by Step

Euclid’s Division Algorithm states: for any two positive integers $a$ and $b$ (where $a > b$ ), there exist unique integers $q$ (quotient) and $r$ (remainder) such that:

a = bq + r, \quad 0 \leq r < b

To find HCF( $a$ , $b$ ): repeatedly apply this division until the remainder is 0. The last non-zero remainder is the HCF.

This works because HCF( $a$ , $b$ ) = HCF( $b$ , $r$ ) — the HCF doesn’t change when we replace the larger number with the remainder.

Since $12576 > 4052$ , divide 12576 by 4052:

12576 = 4052 \times 3 + 420

Check: $4052 \times 3 = 12156$ . And $12576 - 12156 = 420$ . ✓

Now: HCF(12576, 4052) = HCF(4052, 420)

Divide 4052 by 420:

4052 = 420 \times 9 + 272

Check: $420 \times 9 = 3780$ . And $4052 - 3780 = 272$ . ✓

Now: HCF(4052, 420) = HCF(420, 272)

Divide 420 by 272:

420 = 272 \times 1 + 148

Check: $272 \times 1 = 272$ . And $420 - 272 = 148$ . ✓

Now: HCF(420, 272) = HCF(272, 148)

Step 5a: Divide 272 by 148:

272 = 148 \times 1 + 124

HCF(272, 148) = HCF(148, 124)

Step 5b: Divide 148 by 124:

148 = 124 \times 1 + 24

HCF(148, 124) = HCF(124, 24)

Step 5c: Divide 124 by 24:

124 = 24 \times 5 + 4

HCF(124, 24) = HCF(24, 4)

Step 5d: Divide 24 by 4:

24 = 4 \times 6 + 0

Remainder = 0. The last non-zero remainder is 4.

\text{HCF}(12576, 4052) = \mathbf{4}

Why This Works

Euclid’s algorithm exploits a beautiful property: if $d$ divides both $a$ and $b$ , then $d$ also divides $a - bq = r$ . So any common divisor of $a$ and $b$ is also a common divisor of $b$ and $r$ . The HCF is preserved at each step.

We keep making the numbers smaller (the remainder is always less than the divisor) until we reach zero. The second-to-last step gives us the answer — the smallest positive common divisor that “exactly divides” the previous step’s dividend and divisor simultaneously.

It’s one of the oldest algorithms in mathematics — described by Euclid around 300 BCE and still used today in computer science (the binary GCD algorithm is based on the same principle).

Alternative Method — Prime Factorisation

4052 = 4 \times 1013 = 2^2 \times 1013

12576 = 12576 \div 4 = 3144 \div 4 = ... \text{let's check: } 12576 = 2^2 \times 3144 = 2^2 \times 4 \times 786 = 2^4 \times 786 = 2^4 \times 2 \times 393 = 2^5 \times 393

Wait — let me verify with Euclid’s result. If HCF = 4, then $4052/4 = 1013$ and $12576/4 = 3144$ . Check that 1013 and 3144 share no further common factor: $3144 = 1013 \times 3 + 105$ ; $1013 = 105 \times 9 + 68$ ; $105 = 68 \times 1 + 37$ ; $68 = 37 \times 1 + 31$ ; $37 = 31 \times 1 + 6$ ; $31 = 6 \times 5 + 1$ ; $6 = 1 \times 6$ . So HCF(1013, 3144) = 1. ✓

So HCF(4052, 12576) = 4 is confirmed.

Prime factorisation is an alternative but Euclid’s algorithm is faster for large numbers.

Common Mistake

The most common error is stopping too early — stopping when the remainder becomes small, not when it reaches zero. The algorithm must continue until the remainder is exactly 0. Students sometimes also forget to write the division equation for each step; doing so is required to earn full marks in CBSE board exams.

Another common slip: taking the wrong number as the dividend in each step. Always divide the previous divisor by the previous remainder: HCF(a, b) → HCF(b, r) → HCF(r, r’) etc. The pattern is: new dividend = old divisor, new divisor = old remainder.

In CBSE board exams, Euclid’s algorithm questions are worth 3–5 marks. Show all division steps clearly with the equation in the form $a = bq + r$ . Do not skip steps even if the numbers seem simple — each step is worth 0.5–1 mark.

Question

Solution — Step by Step

Why This Works

Alternative Method — Prime Factorisation

Common Mistake

Try These Next