Step-by-step application of Euclid's division algorithm to find HCF. Class 10 NCERT method.

Find HCF of 96 and 72 Using Euclid's Division Lemma

Question

Find the HCF of 96 and 72 using Euclid’s Division Lemma.

Solution — Step by Step

We always start with the larger number as the dividend. So we divide 96 by 72.

96 = 72 \times 1 + 24

Here, quotient = 1 and remainder = 24.

Now we take the previous divisor (72) and the remainder (24). Divide 72 by 24.

72 = 24 \times 3 + 0

Remainder = 0. We stop here.

When the remainder becomes 0, the divisor at that step is our HCF.

The divisor in the last step was 24.

\text{HCF}(96, 72) = \mathbf{24}

Why This Works

Euclid’s Division Lemma says: for any two positive integers $a$ and $b$ , we can always write $a = bq + r$ where $0 \leq r < b$ . The key insight is that $\text{HCF}(a, b) = \text{HCF}(b, r)$ — the HCF doesn’t change when we replace the pair this way.

We keep reducing the problem to smaller and smaller pairs until the remainder hits zero. At that point, the last non-zero remainder is the HCF — it divides everything in the chain.

This is why the algorithm always terminates: the remainders are strictly decreasing ( $96 \to 24 \to 0$ ), and they can’t go below zero.

Alternative Method — Prime Factorisation

Break both numbers into prime factors:

96 = 2^5 \times 3

72 = 2^3 \times 3^2

Take the lowest power of each common prime factor:

\text{HCF} = 2^3 \times 3 = 8 \times 3 = \mathbf{24}

For NCERT board exams, Euclid’s algorithm is the expected method in Chapter 1 questions. Prime factorisation is fine for verification, but write out the division steps if the question says “use Euclid’s Division Lemma” — examiners want to see the algorithm explicitly.

Both methods give 24. Use prime factorisation as a quick cross-check in your rough work.

Common Mistake

The most common error: students stop at the first division and write 24 as the answer without verifying. Always check — the remainder must be 0 before you stop. If $96 = 72 \times 1 + 24$ , the remainder is 24 (not zero), so you must continue. Only $72 = 24 \times 3 + 0$ signals the end.

Another slip: taking the quotient instead of the divisor as the HCF. The quotient (3 in step 2) has nothing to do with the answer.

Question

Solution — Step by Step

Why This Works

Alternative Method — Prime Factorisation

Common Mistake

Try These Next