HCF of Three Numbers by Euclid's Algorithm | Class 10

Quick answer: To find the HCF of three numbers with Euclid's algorithm, find the HCF of two of them first, then find the HCF of that result and the third number: $\text{HCF}(a, b, c) = \text{HCF}(\text{HCF}(a, b), c)$. For example, $\text{HCF}(441, 567, 693) = 63$. The HCF of two numbers can also be written as $ax + by$ for some integers $x$ and $y$; for example, $\text{HCF}(56, 72) = 8 = 56(4) + 72(-3)$.

Euclid's division algorithm finds the HCF of two positive integers by repeated division: divide, take the remainder, and divide again until the remainder is $0$. The last non-zero remainder (the last divisor) is the HCF.

This guide extends the method in two ways: finding the HCF of three numbers, and writing the HCF as a combination of the two numbers, $ax + by$.

Syllabus note: Euclid's division algorithm has been removed from the current rationalised NCERT Class 10 textbook (Chapter 1, Real Numbers), which now finds HCF using prime factorisation. This guide shows both methods for the three-number problem. Euclid's algorithm is still useful for older papers, NCERT Exemplar and competitive exams.

What You Will Learn

• A quick review of Euclid's division lemma, $a = bq + r$ with $0 \le r < b$
• How to find the HCF of three numbers in two stages
• A check using prime factorisation
• How to write the HCF as $ax + by$ by working backwards
• Two fully solved examples

1. HCF of Three Numbers

Rule: $\text{HCF}(a, b, c) = \text{HCF}(\text{HCF}(a, b), c)$

Step 1: Find $d = \text{HCF}(a, b)$ using Euclid's algorithm.

Step 2: Find $\text{HCF}(d, c)$. This is the HCF of all three numbers.

2. Example 1: HCF of 441, 567 and 693

Step 1: HCF of 441 and 567

$567 = 441 \times 1 + 126$

$441 = 126 \times 3 + 63$

$126 = 63 \times 2 + 0$

The remainder is now $0$, so $\text{HCF}(441, 567) = 63$.

Step 2: HCF of 63 and 693

$693 = 63 \times 11 + 0$

The remainder is $0$, so $\text{HCF}(63, 693) = 63$.

Answer: $\text{HCF}(441, 567, 693) = 63$.

Check Using Prime Factorisation

The common prime factors with their smallest powers are $3^2$ and $7$, so the HCF is $3^2 \times 7 = 63$. ✓

3. Writing the HCF as ax + by

If $d$ is the HCF of $a$ and $b$, then there are integers $x$ and $y$ (one of them may be negative) such that:

$d = ax + by$

Method:

Step 1: Use Euclid's algorithm to find the HCF.

Step 2: Start from the step where the HCF appears as the remainder, and write the HCF in terms of the other numbers.

Step 3: Work backwards, replacing each remainder using the earlier steps, until only $a$ and $b$ are left.

4. Example 2: Write HCF(56, 72) as 56x + 72y

Step 1: Euclid's algorithm

$72 = 56 \times 1 + 16 \qquad \text{...(1)}$

$56 = 16 \times 3 + 8 \qquad \text{...(2)}$

$16 = 8 \times 2 + 0$

So $\text{HCF}(56, 72) = 8$.

Step 2: Work backwards

From (2):

$8 = 56 - 16 \times 3$

From (1), $16 = 72 - 56$. Substituting:

$8 = 56 - (72 - 56) \times 3 = 56 - 72 \times 3 + 56 \times 3 = 56 \times 4 - 72 \times 3$

So:

$8 = 56(4) + 72(-3)$

Answer: $\text{HCF}(56, 72) = 8$, with $x = 4$ and $y = -3$.

Check: $56 \times 4 - 72 \times 3 = 224 - 216 = 8$. ✓

5. Summary Table

6. Exam Tips and Common Mistakes

Exam Tip: When working backwards, keep products like $16 \times 3$ unmultiplied. This makes it easier to collect the terms in $a$ and $b$.

Exam Tip: Always check your $x$ and $y$ by working out $ax + by$.

Common Mistake: Sign errors when removing brackets: $-(72 - 56) \times 3 = -72 \times 3 + 56 \times 3$.

Common Mistake: Giving the last quotient as the HCF. The HCF is the last non-zero remainder, which is the divisor in the final step.

Frequently Asked Questions

How do you find the HCF of three numbers?

Find the HCF of any two of the numbers, then find the HCF of that result and the third number.

What is the HCF of 441, 567 and 693?

How do you express the HCF of two numbers as ax + by?

Use Euclid's algorithm to find the HCF, then work backwards through the division steps, replacing each remainder, until the HCF is written using only the two numbers.

What are x and y if HCF(56, 72) = 56x + 72y?

x = 4 and y = −3, since 56 × 4 − 72 × 3 = 8.

Is Euclid's algorithm in the current Class 10 syllabus?

It has been removed from the rationalised NCERT Class 10 textbook, which uses prime factorisation for HCF, but it is still useful for older papers and competitive exams.