How do you find HCF by Euclid division?

You find the Highest Common Factor (HCF) of two numbers using Euclid's division algorithm by repeatedly applying the division lemma until the remainder is zero.

Understanding Euclid's Division Algorithm

Euclid's division algorithm is a technique to compute the HCF of two positive integers. It's based on the following principle:

• The HCF of two numbers divides their difference as well.

Steps to Find HCF using Euclid's Division Algorithm

Here's a step-by-step breakdown of how to find the HCF using Euclid's division algorithm:

1. Apply Euclid's Division Lemma:
   • Given two positive integers, a and b (where a > b), find whole numbers q and r such that a = bq + r, where 0 ≤ r < b. This is the core of the algorithm, as described in the reference: "a = bq + r, where 0 ≤ r < b."
2. Check the Remainder:
   • If r = 0, then b is the HCF of a and b. As the reference states: "If r = 0, then b is the HCF."
   • If r ≠ 0, then apply the division lemma again using b as the new dividend and r as the new divisor.
3. Repeat the Process:
   • Continue applying the division lemma, replacing the previous divisor with the previous remainder, until you get a remainder of 0. The reference highlights this iterative nature: "Otherwise, repeat the process with b and r until r = 0".
4. The HCF is the Last Non-Zero Divisor:
   • The divisor at the stage where the remainder is 0 is the HCF of the original two numbers.

Example

Let's find the HCF of 455 and 42 using Euclid's division algorithm.

1. Step 1: Apply the division lemma to 455 and 42.
   • 455 = 42 × 10 + 35
2. Step 2: The remainder is 35 (not 0), so apply the division lemma to 42 and 35.
   • 42 = 35 × 1 + 7
3. Step 3: The remainder is 7 (not 0), so apply the division lemma to 35 and 7.
   • 35 = 7 × 5 + 0
4. Step 4: The remainder is now 0. The last non-zero divisor was 7.

Therefore, the HCF of 455 and 42 is 7.

Summary Table

Advantages of Euclid's Division Algorithm

• It's a systematic and efficient method for finding the HCF of large numbers.
• It's guaranteed to find the HCF in a finite number of steps.