Euclid's Division Algorithm
Euclid's division algorithm is a way to find the HCF of two numbers by using Euclid's division lemma. It states that if there are any two integers a and b, there exists q and r such that it satisfies the given condition a = bq + r where 0 ≤ r < b. Let's learn more about it in this lesson.
What is Euclid's Division Lemma?
Euclid’s Division Lemma (lemma is like a theorem) says that given two positive integers a and b, there exist unique integers q and r such that a = bq + r, 0≤ r <b. The integer q is the quotient and the integer r is the remainder. The quotient and the remainder are unique.
In simple words, Euclid's Division Lemma is what you were using to check the accuracy of division in lower classes, which is Dividend = Divisor × Quotient + Remainder. When we divide a = 39 by b = 5, we get the quotient as q = 7 and the remainder as r = 4. Here is an example:
Thus, by Euclid's division lemma, 39 = 5 × 7 + 4.
What is Euclid's Division Algorithm?
Euclid’s Division Algorithm is the process of applying Euclid’s Division Lemma in succession several times to obtain the HCF of any two numbers.
We will come across Euclid's Division Algorithm in Class 10. An algorithm is a sequence of steps to accomplish a task. To understand this algorithm and why it works, let's assume that there are two numbers a and b. Applying Euclid’s Division Lemma, we will have two integers q and r such that a= b(q)+r, where q is the quotient and r is the remainder. We notice an important fact with respect to this relation. Any common factor of a and b must also be a factor of r. Why is that?
Let's assume that an integer k is a common factor of both a and b. Dividing the above relation on both sides by k, we have:
\[\begin{align}&\frac{a}{k} = \frac{b}{k}\left( q \right) + \frac{r}{k}\\ \Rightarrow \;\;\;&\frac{a}{k} - \frac{b}{k}\left( q \right) = \frac{r}{k}\end{align}\]
Clearly, the left side is an integer (as k is a common factor of both a and b), which means that the right side must also be an integer. Thus, r must be divisible by k. We will make use of this observation in understanding Euclid’s Division Algorithm.
Euclid's Division Algorithm Example - Finding HCF
If we have to find the HCF of 320 and 132, we apply the Euclid’s Division Lemma on these two numbers:
320 = 132(2) + 56 ......... (step 1)
We observe (based on our discussion above) that since the HCF (call it x) is a factor of both 320 and 132, it must also be a factor of the remainder 56 in the division step above. Now, we apply the division lemma on 132 and 56:
132 = 56(2) + 20 ......... (step 2)
Once again, since the HCF x is a common factor of both 132 and 56, it must also be a common factor of 20. So, in the next step, we apply the division lemma to 56 and 20:
56 = 20(2) + 16 ............ (step 3)
As earlier, since x is a common factor of both 56 and 20, it must also be a common factor of 16. Next, we apply the division lemma to 20 and 16:
20 = 16(1) + 4 .............. (step 4)
We see that x, being a factor of both 20 and 16, must also be a factor of 4. In the last step, we have:
16 = 4(4) + 0 .............. (step 5)
We have no remainder left. We now assert that the second last remainder is the HCF, that is, the HCF of 320 and 132 is equal to 4.
⇒ HCF (320,132)= 4
4 is a common factor of the original pair of numbers. To justify our assertion, we have to show that 4 is the highest possible common factor. Back-tracing from the second last step, it is easy to see that 4 is a common factor of the original pair of numbers (without actually dividing them by 4). In the second last step, we see that 4 is a common factor of 16 and 20, and hence of 56, and hence of 132, and hence of 320. Now, let us prove that no other higher common factor is possible:
From Step-1, any common factor (say y) of 320 and 132 must also be a factor of 56
From Step-2, y must also be a factor of 20
From Step-3, y must also be a factor of 16
Finally, from Step-4, y must also be a factor of 4
Thus, any common factor of 320 and 132 must also be a factor of the common factor 4, which means that 4 is the highest possible common factor, that is, the HCF is 4.
Important Notes:
- Euclid's division lemma says that given two positive integers a and b, there exist unique integers q and r such that a= bq+r, 0 ⩽ r <b
- Euclid’s Division Algorithm is the process of applying Euclid’s Division Lemma in succession several times to obtain the HCF of any two numbers.
- Euclid's Division Algorithm works because if a= b(q)+r, then HCF(a,b)= HCF(b,r).
Generalizing Euclid's Division Algorithm
Let us now generalize Euclid's division algorithm. Let's assume that we have to find the HCF of any two arbitrary numbers a and b. We apply Euclid’s Division Lemma in succession until we obtain a remainder of 0:
a=b(q1)+r1
b=r1(q2)+r2
r1=r2(q3)+r3
⋮
rn−2=rn−1(qn)+rn
rn−1=rn(qn+1)+0
The HCF is the remainder in the second last step, that is, HCF(a,b)= rn. You are urged to prove this by following the same line of reasoning as the one above. First, show that rn is indeed a common factor of a and b. Then, show that any common factor of a and b must also be a factor of rn, which means that rn is the highest common factor.
It is possible that you may not have understood the justification of Euclid’s Division Algorithm completely, and you may be tempted to skip it and move forward. However, our word of advice: understanding this reasoning is a good mental exercise, as well as important for reasons that will become clear later. So, do not move ahead until you fully understand the preceding discussion.
Shortcut Method for Euclid's Division Algorithm
Are the steps shown above confusing? Don't worry. Here is a shortcut method. Do you remember the process of finding the HCF using the long division method which you learned in the lower classes? We will use the same method to write the steps of Euclid's division algorithm. The shortcut shown here is for the same example above (finding HCF of 132 and 320). Here we use the following formula which we learned in the lower classes.
Dividend = Divisor × Quotient + Remainder
In this method, the divisor of the last step which leads to the remainder zero is the HCF. This implies, HCF(320,132)= 4.
Try to Solve These Challenging Questions
- Using Euclid’s Division Algorithm, find the HCF of 768 and 468. Tip: Use a similar approach as in examples 1 and 2.
- Express the HCF of 52 and 117 as 52x+117y, where x and y are integers. Tip: Use a similar approach as in example 3.
Related Topics
Solved Examples on Euclid's Division Algorithm
-
Example 2: Using Euclid’s Division Algorithm, find the HCF of 130 and 91.
Solution:
We have: 130=91(1)+39
91=39(2)+13
39=13(3)+0
We know that the HCF is the remainder in the second last step, which is 13.
Alternate Method (Shortcut):
Therefore, HCF (130, 91) = 13.
Practice Questions on Euclid's Division Algorithm
FAQs on Euclid's Division Algorithm
What is the Difference Between Euclid's Division Lemma and Division Algorithm?
Euclid's Division Lemma is a proven statement used for proving another statement while an algorithm is a series of well-defined steps that give a procedure for solving a type of problem.
Euclid's division algorithm is used to find the Highest Common Factor (HCF) of two numbers where we apply the statement of Euclid's division lemma.
What does Euclid's Division Algorithm Mean?
Euclid's Division Algorithm is a technique to compute the Highest Common Factor (HCF) of two given positive integers. HCF of two positive integers a and b is the largest positive integer d that divides both a and b.
What is the Division Algorithm for Polynomials?
To understand the division algorithm for polynomials, assume f(x) and g(x) are two polynomials, where g(x)≠0. We can write: f(x) = q(x) g(x) + r(x) which is same as Dividend = Divisor × Quotient + Remainder; where r(x) is the remainder polynomial and is equal to 0 and degree r(x) < degree g(x).
How to Find the GCD Algorithm?
The Euclidean Algorithm for finding Greatest Common Divisor or GCD(A,B) is: If A = 0 then GCD(A,B)=B, since the GCD(0,B)=B, we can stop. If B = 0, then GCD(A,B)=A, since the GCD(A,0)=A, we can stop. Write A in quotient remainder form (A = B×Q + R)
How does GCD Work?
The greatest common divisor (GCD), also called the greatest common factor, of two numbers is the largest number that divides them both.
How do you Use Euclid's Division Algorithm?
We use the division algorithm to find the HCF of two numbers. You can learn more about this from the section "What is Euclid's Division Algorithm?" of this page.
What is the Formula of the Division Algorithm?
The division algorithm is not a formula, it is the procedure for using Euclid's division lemma multiple times to find the HCF of two numbers.