Euclid's Division Algorithm

Go back to  'Arithmetic-Integers'

What is Euclid's Division Algorithm and why does it work?

The process of applying Euclid’s Division Lemma in succession a number of times to obtain the HCF of any two numbers is known as Euclid’s Division Algorithm (an algorithm is a sequence of steps to accomplish a task). To understand this algorithm and why it works, suppose 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\left( q \right) + r\]

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? Suppose 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, 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.

Applying Euclid's Division Algorithm: First Example

Suppose that we have to find the HCF of 320 and 132. We apply the division lemma on these two numbers:

\[320 = 132\left( 2 \right) + 56  \qquad\qquad \left[ {{\rm{step}} - 1} \right]\]

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 step division step above. Now, we apply the division lemma on 132 and 56:

\[132 = 56\left( 2 \right) + 20 \qquad\qquad \left[ {{\rm{step}} - 2} \right]\]

Once again, since the HCF x is a common factor of both 132 and 56, it must also be a common factor of 20. In the next step, we apply the division lemma to 56 and 20:

\[56 = 20\left( 2 \right) + 16 \qquad\qquad \left[ {{\rm{step}} - 3} \right]\]

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\left( 1 \right) + 4 \qquad\qquad \left[ {{\rm{step}} - 4} \right]\]

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\left( 4 \right) + 0 \qquad\qquad \left[ {{\rm{step}} - 5} \right]\]

We have no remainder left. We now assert that the second last remainder is the HCF, that is, the HCF x is equal to 4. But why?

To justify our assertion, we have to show that:

  • 4 is a common factor of the original pair of numbers.

  • 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.

Go through this discussion as many times as you have to until you understand it completely.

Applying Euclid's Division Algorithm: Second Example

Let us take another example to clarify Euclid’s Division Algorithm. Consider the pair of numbers 350 and 224. Applying Euclid’s Division Lemma in succession, we have the following steps:

\[\begin{align}&350 = 224\left( 1 \right) + 126 \qquad\;\;\; \left[ {{\rm{step}} - 1} \right]\\&224 = 126\left( 1 \right) + 98 \qquad\quad\; \left[ {{\rm{step}} - 2} \right]\\&126 = 98\left( 1 \right) + 28 \qquad\quad\;\;\; \left[ {{\rm{step}} - 3} \right]\\&98 = 28\left( 3 \right) + 14 \qquad\qquad\; \left[ {{\rm{step}} - 4} \right]\\&28 = 14\left( 2 \right) + 0 \qquad\qquad\;\;\; \left[ {{\rm{step}} - 5} \right]\end{align}\]

Thus, the HCF is the remainder in the second last step, that is, 14. Let us prove how.

  • First, we prove (without explicit division) that 14 is a common factor of the original pair of numbers. From Step-5, we note that 14 is a factor of 28, and hence (from Step-4) of 98, and hence (from Step-3) of 126, and hence (from Step-2) of 224, and hence (from Step-1) of 350.

  • Next, we prove that 14 is the highest possible common factor. For that, consider any common factor, say x, of 350 and 224. Then, it must be a factor of 126 (from Step-1), and hence of 98 (from Step-2), and hence of 28 (from Step-3), and hence of 14 (from Step-4). Thus, any common factor of 350 and 224 must also be a factor of 14, which means that 14 is the highest possible common factor, that is, the HCF.

Applyig Euclid's Division Algorithm: General Case

Let us now generalize this discussion. Suppose 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:

\[\begin{align}&a = b\left( {{q_1}} \right) + {r_1}\\&b = {r_1}\left( {{q_2}} \right) + {r_2}\\&{r_1} = {r_2}\left( {{q_3}} \right) + {r_3}\\& \qquad\qquad \vdots \\&{r_{n - 2}} = {r_{n - 1}}\left( {{q_n}} \right) + {r_n}\\&{r_{n - 1}} = {r_n}\left( {{q_{n + 1}}} \right) + 0\end{align}\]

The HCF is the remainder in the second last step, that is:

\[{\rm{HCF}}\left( {a,\;b} \right) = {r_n}\]

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.

Examples on Euclid's Division Algorithm

Example 1. Using Euclid’s Division Algorithm, find the HCF of 130 and 91.

Solution. We have:

\[\begin{align}&130 = 91\left( 1 \right) + 39\\&\;\;91 = 39\left( 2 \right) + 13\\&\;\;39 = 13\left( 3 \right) + 0\end{align}\]

Thus,

\[{\rm{HCF}}\left( {130,\;91} \right) = 13\]

Example 2. Using Euclid’s Division Algorithm, find the HCF of 648 and 1400.

Solution. We have:

\[\begin{align}&1400 = 648\left( 2 \right) + 104\\&\;\;648 = 104\left( 6 \right) + 24\\&\;\;104 = \;\;24\left( 4 \right) + 8\\&\quad 24 =\quad\; 8\left( 3 \right) + 0\end{align}\]

Thus,

\[{\rm{HCF}}\left( {1400,\;648} \right) = 8\]

Example 3. Using Euclid’s Division Algorithm, find the HCF of 768 and 468.

Solution. We have:

\[\begin{align}&768 = 468\left( 1 \right) + 300\\&468 = 300\left( 1 \right) + 168\\&300 = 168\left( 1 \right) + 132\\&168 = 132\left( 1 \right) + 36\\&132 = \;\;36\left( 3 \right) + 24\\&36 = \quad24\left( 1 \right) + 12\\&24 = \quad12\left( 2 \right) + 0\end{align}\]

Thus,

\[{\rm{HCF}}\left( {768,\;468} \right) = 12\]

For each of these three examples, you should also calculate the HCFs by prime factorization, and compare the two approaches.

Learn math from the experts and clarify doubts instantly

  • Instant doubt clearing (live one on one)
  • Learn from India’s best math teachers
  • Completely personalized curriculum