Euclid's division algorithm — find HCF step by step with examples

Question

Use Euclid’s division algorithm to find the HCF of 196 and 38220. Show each step clearly.

Solution — Step by Step

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

The algorithm: keep dividing the divisor by the remainder until the remainder becomes 0. The last non-zero remainder is the HCF.

Step 1: $38220 = 196 \times 195 + 0$

Wait — let us check: $196 \times 195 = 38220$ . The remainder is 0 in the very first step.

Since the remainder is 0, the divisor at this step is the HCF.

HCF(38220, 196) = 196

Step 1: $272 = 64 \times 4 + 16$ (remainder = 16)

Step 2: $64 = 16 \times 4 + 0$ (remainder = 0)

The last non-zero remainder is 16.

So HCF(272, 64) = 16.

flowchart TD
    A[Start with a and b, a greater than b] --> B[Divide a by b]
    B --> C{Remainder = 0?}
    C -->|Yes| D[HCF = b - the divisor]
    C -->|No| E[Replace a with b, b with remainder]
    E --> B

Why This Works

Euclid’s algorithm works because HCF(a, b) = HCF(b, r), where $r$ is the remainder when $a$ is divided by $b$ . This is because any common divisor of $a$ and $b$ must also divide $r$ (since $r = a - bq$ ). The remainders keep decreasing, so the process must terminate at 0.

Alternative Method

You can also find HCF by prime factorisation: $272 = 2^4 \times 17$ and $64 = 2^6$ . Common prime factors = $2^4 = 16$ . But Euclid’s algorithm is faster for large numbers (no need to factorise).

Common Mistake

Students sometimes divide $b$ by $a$ instead of $a$ by $b$ (larger by smaller). Always start with the larger number as the dividend. If you accidentally swap them, the first step will give a quotient of 0 and remainder = $a$ , which just adds an extra step — but the final answer is still correct.

CBSE Class 10 boards always ask one question on Euclid’s division algorithm — either find HCF of two numbers, or use the algorithm to show that a given number divides both. Practice at least 5 examples with 3-digit numbers to build speed.

Question

Solution — Step by Step

Why This Works

Alternative Method

Common Mistake

Try These Next