Welcome to our third lesson. In our previous discussion, we established what the Highest Common Factor (HCF) is and practiced finding it by listing out all the factors of two numbers. While this method is excellent for building intuition with small numbers, we concluded that it's inefficient and error-prone for larger ones.
Today, we will address this challenge by learning a far more powerful and elegant technique: Euclid's division algorithm. This is a classic, centuries-old algorithm for finding the HCF of any two positive integers. The systematic, step-by-step nature of this process is something that often appeals to those with a background in engineering or software development. Our goal is to understand not just how to apply the algorithm, but also why it works, which will be invaluable for explaining the concept to your daughter.
The Foundation: Euclid's Division Lemma
The entire algorithm is built upon a simple, foundational statement known as Euclid's Division Lemma. This might sound intimidating, but it's really just a formal way of expressing the outcome of a standard division operation.
Euclid's Division Algorithm - Definition, Statement, Examples
This article from Cuemath provides a clear and direct definition of the lemma, which is the cornerstone of the algorithm.
Please read the first section, What is Euclid's Division Lemma?. Focus on understanding the relationship between the four integers a, b, q, and r.
As the article explains, for any two positive integers a (the dividend) and b (the divisor), we can always find unique integers q (the quotient) and r (the remainder) such that:
The crucial condition is that the remainder r must be greater than or equal to zero and strictly less than the divisor b (). This is something you're already familiar with—when you perform division, the process stops when the remainder is smaller than the number you are dividing by.
The Logic of the Algorithm: Why It Works
Before we learn the steps of the algorithm, it's essential to understand the mathematical principle that makes it valid. This is the "secret ingredient" that makes the process so efficient. The core idea is that the Highest Common Factor of two numbers a and b is the same as the HCF of the smaller number b and the remainder r from the division of a by b.
In short: HCF(a, b) = HCF(b, r)
This property allows us to replace a problem involving large numbers (finding HCF of a and b) with an equivalent problem involving smaller numbers (finding HCF of b and r), and repeat the process until the problem becomes trivial to solve.
For a rigorous proof of this property, which aligns with your preference for understanding derivations, the following resource from Khan Academy is excellent.
The Euclidean Algorithm (article)
This article provides a formal proof for the key property of the Euclidean Algorithm. Understanding this will give you the deep conceptual clarity you're looking for.
In the section "Understanding the Euclidean Algorithm", first read the two proofs that establish the preliminary result: the GCD proofs. Then, carefully follow the logic that uses this result to prove the main property: GCD(A,B)=GCD(B,R).
The key insight from the proof is that any number that is a common divisor of A and B must also be a divisor of their difference, A-B, and by extension, the remainder R. This means the set of common divisors for (A, B) is identical to the set of common divisors for (B, R). If the sets are identical, their greatest elements (the HCFs) must also be identical.
The image below provides a great visual intuition for the simpler case, GCD(A,B) = GCD(B, A-B), which is the basis for the more general proof.
The Method: Applying the Algorithm
Now that we understand why the algorithm works, let's see it in action. The process involves repeatedly applying the division lemma to reduce the numbers until we get a remainder of 0. The HCF will be the last non-zero remainder.
To build a strong mental model of this process, let's watch a video that visualizes the algorithm as a problem of tiling a rectangle with the largest possible square tiles.
Euclid's division algorithm visualised | Real numbers | Class 10 (India) | Math
This Khan Academy video provides a brilliant visualization of what Euclid's algorithm is actually doing. It transforms an abstract numerical process into a concrete geometric task.
Watch the entire video from start to finish. Pay close attention to how finding the HCF of two numbers (the dimensions of the rectangle) is equivalent to finding the size of the largest square brick that can tile it perfectly. Notice how each step of the algorithm reduces the size of the remaining area to be tiled.
The video beautifully illustrates the reduction HCF(a, b) → HCF(b, r). The original problem of tiling the 32x12 area is reduced to tiling the remaining 12x8 area, which is then reduced to tiling the 8x4 area. Since 4x4 squares tile the 8x4 area perfectly (remainder 0), the largest possible square tile size is 4. Thus, HCF(32, 12) = 4.
Now, let's apply this method to a numerical example using the a = bq + r format.
Euclid's Division Algorithm - Definition, Statement, Examples
This article walks through the exact steps of the algorithm with a clear example and connects it back to the long division method you're familiar with from school.
First, quickly read the section "Why it works" to see a slightly different algebraic justification that reinforces what we've already learned. Next, carefully study the step-by-step example for finding the HCF of 320 and 132. Finally, look at the "Shortcut Method" section. It shows how these algebraic steps correspond directly to the long division method.
The image below shows the same process for finding the HCF of 320 and 132. It's a great summary that links the long division steps with the corresponding lemma equations.
Check Your Understanding
Let's apply the algorithm to find the HCF of 455 and 42.
Try to work through the steps yourself using the a = bq + r format.
Click to see the solution
Step 1: Apply the lemma to 455 and 42.
- The remainder is 35. Now we find the HCF of 42 and 35.
Step 2: Apply the lemma to 42 and 35.
- The remainder is 7. Now we find the HCF of 35 and 7.
Step 3: Apply the lemma to 35 and 7.
- The remainder is 0. The process stops.
The last non-zero remainder was 7. Therefore, the HCF of 455 and 42 is 7.
Conclusion
In this lesson, we have explored Euclid's division algorithm, a highly efficient method for finding the HCF of two positive integers. We focused not only on the mechanical steps but also on the logical foundation that makes it work.
Key Takeaways:
- Euclid's Division Lemma is the formal statement of division: , where .
- The algorithm's power comes from the property that HCF(a, b) = HCF(b, r). This allows us to systematically reduce the problem to smaller numbers.
- The algorithm is an iterative process: we repeatedly apply the lemma until the remainder becomes zero. The last non-zero remainder is the HCF of the original numbers.
We have now covered two methods for finding HCF: listing factors and Euclid's algorithm. The latter is clearly superior for larger numbers. In our next lesson, we will introduce another cornerstone of number theory: the Fundamental Theorem of Arithmetic. This theorem states that every integer greater than 1 can be uniquely represented as a product of prime numbers. This will lead us to a third method for finding HCF and will also allow us to easily calculate the Lowest Common Multiple (LCM).