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

Question

How do we use Euclid’s division algorithm to find the HCF (Highest Common Factor) of two numbers step by step?

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

This is the foundation. The algorithm applies this lemma repeatedly.

To find HCF( $a$ , $b$ ) where $a > b$ :

Apply the division lemma: $a = bq_1 + r_1$
If $r_1 = 0$ , then HCF = $b$ . Stop.
If $r_1 \neq 0$ , replace $a$ with $b$ and $b$ with $r_1$ . Go to step 1.

Repeat until the remainder becomes 0. The last non-zero remainder is the HCF.

Step 1: $455 = 42 \times 10 + 35$ (remainder = 35)

Step 2: $42 = 35 \times 1 + 7$ (remainder = 7)

Step 3: $35 = 7 \times 5 + 0$ (remainder = 0)

The last non-zero remainder is 7.

\boxed{\text{HCF}(455, 42) = 7}

Always start with the larger number:

$38220 = 196 \times 195 + 0$

The remainder is 0 in the very first step. So:

\text{HCF}(38220, 196) = 196

This tells us 196 divides 38220 exactly.

The key insight: $\text{HCF}(a, b) = \text{HCF}(b, r)$ where $r$ is the remainder when $a$ is divided by $b$ .

This is because any common factor of $a$ and $b$ must also divide $r = a - bq$ . And any common factor of $b$ and $r$ must also divide $a = bq + r$ . So the set of common factors is the same, meaning the HCF is preserved.

flowchart TD
    A["Find HCF of a and b"] --> B["Divide a by b: a = bq + r"]
    B --> C{"Is r = 0?"}
    C -->|"Yes"| D["HCF = b"]
    C -->|"No"| E["Replace: a becomes b, b becomes r"]
    E --> B

Why This Works

Euclid’s algorithm works because it reduces the problem size at each step without changing the answer. The pair $(a, b)$ is replaced by $(b, r)$ where $r < b$ , so the numbers get strictly smaller. Since we are working with positive integers that decrease at each step, the process must terminate — and it terminates when the remainder hits 0.

The algorithm is over 2300 years old and is one of the earliest known algorithms in mathematics. It is computationally very efficient, requiring at most about $5 \times$ the number of digits steps.

Alternative Method

For small numbers, prime factorization is often faster: factorize both numbers, then take the product of common prime factors with the lowest powers. For example, $24 = 2^3 \times 3$ and $36 = 2^2 \times 3^2$ , so HCF $= 2^2 \times 3 = 12$ . But for large numbers, Euclid’s algorithm is far more practical.

Common Mistake

Students sometimes apply the algorithm with $a < b$ (smaller divided by larger). While the algorithm still works (the first step just swaps them, since $a = b \times 0 + a$ ), it wastes one step. Always start with $a > b$ to be efficient. More importantly, when showing work in CBSE exams, starting with $a < b$ confuses the examiner and may cost a step mark.

Question

Solution — Step by Step

Why This Works

Alternative Method

Common Mistake

Try These Next