# Euclid's Division Algorithm

Go back to  'Integers'

## What is an Algorithm?

An algorithm is a sequence of steps to accomplish a task.

OR

A process or set of rules to be followed in calculations or other problem-solving operations, especially by a computer.

OR

An algorithm is a procedure that takes in input, follows a certain set of steps, and then produces an output.

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

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$ Think: In above equation, Is $$a$$ always greater than $$b$$?

$$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 (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.

Let us take an example,

If we have to find the HCF of 320 and 132. We apply the Euclid’s 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. So, 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.

$\Rightarrow \boxed{{\text{HCF}}(320,132) = 4}$

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.

✍Note: In short, Euclid's Division Algorithm works because if $$a = b\left( q \right) + r$$ then $${\text{HCF}}(a,b) = {\text{HCF}}(b,r)$$ .

## Generalizing Euclid's Division Algorithm:

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:

$\Rightarrow \boxed{{\text{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 $${{r_n}}$$ 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 $${{r_n}}$$ , which means that $${{r_n}}$$ 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.

## Solved Examples:

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}

We know that the HCF is the remainder in the second last step. Thus,

$\Rightarrow \boxed{{\text{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}

We know that the HCF is the remainder in the second last step. Thus,

$\Rightarrow \boxed{{\text{HCF}}\left( {1400,\;648} \right) = 8}$ Challenge 1: Using Euclid’s Division Algorithm, find the HCF of 768 and 468.

⚡Tip: Use a similar approach as in examples 1 and 2.

Example 3: Express the HCF of 468 and 222 as $$468x + 222y$$, where $$x$$ and $$y$$ are integers.

Solution: Firstly, let us find the HCF of 468 and 222.

By Euclid's Division Algorithm, we have,

\begin{align}468 &= 222\left( 2 \right) + 24\\\;\;222 &= 24\left( 9 \right) + 6\\\;\;24 &= 6\left( 4 \right) + 0\end{align}

We know that the HCF is the remainder in the second last step. Thus,

$\Rightarrow \boxed{{\text{HCF}}(468,222) = 6}$

Now, from the second step of Euclid's Division Algorithm, we can rearrange the equation to isolate 6,

$6 = 222 - \left( {24 \times 9} \right)$

Also, from the first step of Euclid's Division Algorithm, we can get, $$24 = 468 - 222(2)$$, let's substitute this value of 24 in above equation, we have,

\begin{align} 6 &= 222 - [468 - 222(2)](9) \hfill \\ \Rightarrow 6 &= 222 + 222(18) - 468(9) \hfill \\ \Rightarrow 6 &= 468( - 9) + 222(19) \hfill \\ \end{align}

Thus,

$\Rightarrow \boxed{x = - 9},\boxed{y = 19}$ Challenge 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.

## 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 algorithm is a series of well defined steps which gives a procedure for solving a type of a 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?

• Euclids 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 division algorithm for polynomials?

• To understand 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 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, and we can stop. If B = 0 then GCD(A,B)=A, since the GCD(A,0)=A, and we can stop. Write A in quotient remainder form (A = B⋅Q + R)

## How does GCD work?

• Greatest Common Divisor. The greatest common divisor (GCD), also called the greatest common factor, of two numbers is the largest number that divides them both.