Euclid’s Division Algorithm: The word algorithm comes from the 9th-century Persian mathematician al-Khwarizmi. An algorithm means a series of well-defined steps that provide a calculation procedure repeated successively on the results of earlier stages until the desired result is obtained. Euclid’s division algorithm is also an algorithm to compute the highest common factor (HCF) of two given positive integers.

The basis of the Euclidean division algorithm is Euclid’s division lemma. HCF is the number that divides two positive integers. In this article, we will highlight Euclid’s division’s lemma and theorems of the Eucalids lemma with examples and algorithm proof. Continue reading this article!

Euclid’s Division Lemma

Euclid is a Greek Mathematician who has made a lot of contributions to number theory. Among these, Euclid’s Lemma is the most important one. A Lemma is a proven statement that is used to prove other statements. This lemma is simply a restatement of the long division process.

The Theorem of Euclid’s Division Lemma

Let \(a\) and \(b\) be any two positive integers. Then there exist unique integers \(q\) and \(r\) such that
\(a = bq + r,0 \le r < b\)
If \(b\) divides a then \(r=0\). Otherwise, \(r\) satisfies the inequality \(0<r<b\).

Proof: Consider the following arithmetic progression.

\(………, a-3b, a-2b, a-b, a, a+b, a+2b, a+3b,……\)

Clearly, it is an arithmetic progression with a common difference \(‘b’\), and it extends indefinitely in both directions.
Let \(r\) be the smallest non-negative term of this arithmetic progression. Then, there exists a non-negative integer \(q\) such that
\(a – bq = r \to a = bq + r\)
\(a,r\) is the smallest non-negative integer satisfying the above result. 

Therefore, \(0 \le r < b\)
Thus, we have \(a=bq+r\), where \(0 \le r < b\)
We shall now prove the uniqueness of \(q\) and \(r\).
Uniqueness to prove the uniqueness of \(q\) and \(r\), let us assume that there is another pair \({q_1}\) and \({r_1}\) of non-negative integers satisfying the same relation, i.e.,

\(a=bq+r\) and \(a = b{q_1} + {r_1}\)
\( \Rightarrow bq + r = b{q_1} + {r_1}\)
\( \Rightarrow {r_1} – r = b{q_1} – b{q_1}\)
\( \Rightarrow {r_1} – r = b\left( {q – {q_1}} \right)\)

Now, \(b\left( {q – {q_1}} \right) = 0 \Rightarrow {r_1} – r = 0\)
\(\left[{\because \,\,0 \leqslant r < b\,{\text{and}}\,0 \leqslant {r_1} < b \Rightarrow 0 \leqslant {r_1} – r < b} \right]\)
\( \Rightarrow {r_1} = r\)

Now, \({r_1} = r\)
\( \Rightarrow – {r_1} = – r\) [Multiplying both sides by \((-1)\)]
\( \Rightarrow a – {r_1} = a – r\) [Adding a on both sides]
\( \Rightarrow b{q_1} = bq\) \([∵a = bq + r\) and \(\left. {a = b{q_1} + {r_1}} \right]\)
\([∵bq = a – r\) and \(\left. {b{q_1} = a – {r_1}} \right]\)
\(\Rightarrow {q_1} = q\)

Hence, the representation \(a = bq + r,0 \le r < b\) is unique.

What is Euclid Division Algorithm 

Definition: Euclid’s Division Algorithm is the process of applying Euclid’s division lemma in succession several times to obtain some result. Euclid’s division lemma can be applied to find the HCF of any two numbers.

The largest or the greatest among the common divisors of two or more integers is known as the Greatest Common Divisor (GCD) or highest common factor (HCF) of the given integers. The HCF of two or more positive integers always exists, and it is unique. Let the two positive integers be \(a\) and \(b\) where \(a>b\).

Suppose \(b\) is not a divisor of a. In that case, there exist positive integers \(q\) and \(r\) such that \(a=bq+r\), where \(0<r<b\). Common divisors of \(a\) and \(b\) are closely associated with the common divisors of \(b\) and \(r\). Every common divisor of \(b\) and \(r\) is a common divisor of \(a\) and \(b\) and vice-versa, as stated and proved in the given theorem.

State and Prove Division Algorithm

Below are the theorems with algorithm division proofs.

Theorem: If \(a\) and \(b\) are positive integers such that \(a=bq+r\), then every common divisor of \(a\) and \(b\) is a common divisor of \(b\) and \(r\), and vice-versa.

Proof: Let \(c\) be a common divisor of \(a\) and \(b\). Then,

\(c\mid a \Rightarrow a = c{q_1}\)for some integer \({q_1}\)          \(c\mid b \Rightarrow b = c{q_2}\) for some integer \({q_2}\)

Now, 
\(a = bq + r\)
\( \Rightarrow r = a – bq\)
\(\Rightarrow r = c{q_1} – c{q_2}q\)
\( \Rightarrow r = c\left( {{q_1} – {q_2}q} \right)\)
\(\Rightarrow c\mid r\)
\(\Rightarrow c\mid r\) and \(c\mid b\) \([∵c\mid b\) (given)]
\( \Rightarrow c\) is a common divisor of \(b\) and \(r\).

Hence, a common divisor of \(a\) and \(b\) is a common divisor of \(b\) and \( r\). Conversely, let \(d\) be a common divisor of \(b\) and \(r\). Then,
\(d\mid b \Rightarrow b = {r_1}d\) for some integer \({r_1}\)
\(d\mid r \Rightarrow r = {r_2}d\) for some integer \({r_2}\)

We will now show that \(d\) is a common divisor of \(a\) and \(b\). We have,
\(a = bq + r\)
\( \Rightarrow a = {r_1}dq + {r_2}d\)
\( \Rightarrow a = \left( {{r_1}q + {r_2}} \right)d\)
\( \Rightarrow d\mid a\)
\(\Rightarrow d\mid a\) and \(d\mid b\) \([∵d\mid b\) (given)]
\( \Rightarrow d\) is a common divisor of \(a\) and \(b\).

To compute the HCF of two positive integers, say \(a\) and \(b\), with \(a>b\) you have to follow the given steps:

Step 1: Apply Euclid’s division lemma to a and b and obtain whole numbers \({q_1}\) and \({r_1}\) such that \(a = b{q_1} + {r_1},0 < {r_1} < b\)

Step 2: If \({r_1} = 0,b\) is the HCF of \(a\) and \(b\).

Step 3: If \({r_1} \ne 0\), apply Euclid’s division lemma to b and obtain two whole numbers \({q_1}\) and \({r_2}\) such that \(b = {q_1}{r_1} + {r_2}\)

Step 4: If \({r_2} = 0\) then \({q_1}\) is the HCF of \(a\) and \(b\).

Step 5: If \({r_2} \ne 0\), then apply Euclid’s division lemma to \({r_1}\) and \({r_2}\) and continue the above process till the remainder \({r_n}\) is zero. The divisor at this stage i.e. \({q_{n – 1}}\)is the HCF of \(a\) and \(b\).

Example: Use Euclid’s division algorithm to find the HCF of \(210\) and \(55\).

Solution: Given integers are \(210\) and \(55\). Here, \(210>55\). Applying Euclid’s division lemma to \(210\) and \(55\) we get,
\(210=55×3+45\)

Since the remainder \(45≠0\). So, we apply the division lemma to the divisor \(55\) and the remainder \(45\) to get
\(55=45×1+10\)

Now, apply the division lemma to the new divisor \(45\) and new remainder \(10\) to get
\(45=10×4+5\)

We now consider the new divisor \(10\) and the new remainder \(5\) and apply the division lemma to get
\(10=5×2+0\)

The remainder at this stage is zero. So, the divisor at this stage is \(5\). Hence, \(5\) is the HCF of \(210\) and \(55\).

Important Points

To find the HCF of three numbers, you have to use the given steps:

Step 1: Find the HCF of any two of the given numbers

Step 2: Find the HCF of the third given number and the HCF obtained in step \(1\).

Step 3: The HCF obtained in step \(2\) is the HCF of three given numbers.

Solved Examples – Euclid’s Division Algorithm

Q.1. Euclid division algorithm HCF questions: A sweet seller has \(420\) Kaju burfi and \(130\) badam burfi. She wants to stack them so that each stack has the same number, and they take up the minor area of the tray. What is the number of burfi that can be placed in each pile for this purpose?
Ans: The area of the tray that is used up in stacking the burfi will be the least if the sweet seller stacks the maximum number of burfi in each stack. Since each stack must have the same number of burfi, the number of stacks will be least if the number of burfi in each stack is equal to the HCF of \(420\) and \(130\).
To find the HCF of \(420\) and \(130\), let us apply Euclid’s division lemma to \(420\) and \(130\) to get
\(420=130×3+30\) 
Let us now consider the divisor \(130\) and the remainder \(30\) and apply the division lemma to get
\(130=30×4+10\) 
Considering now divisor \(30\) and the remainder \(10\) and applying the division lemma, we get
\(30=3×10+0\) 
Since the remainder at this stage is zero. Therefore, the last divisor \(10\) is the HCF of \(420\) and \(130\).
Hence, the sweet seller can make stacks of \(10\) burfi of each kind to cover the least area of the tray.

Q.2. Use Euclid’s division algorithm to find the HCF of \(4052\) and \(12576\).
Ans: Given integers are \(4052\) and \(12576\) such that \(12576>4052\). Applying Euclid’s division lemma to \(12576\) and \(4052\), we get
\(12576=4052×3+420\)
Since the remainder \(420≠0\) so, we apply the division lemma to \(4052\) and \(420\) to get
\(4052=420×9+272\)
We consider the new divisor \(420\) and the new remainder \(272\) and apply the division lemma to get
\(420=272×1+148\)
Let us now consider the new divisor \(272\) and the new remainder \(148\) and apply the division lemma to get
\(272=148×1+124\)
We consider now the new divisor \(148\) and the new remainder \(124\) and apply the division lemma to get
\(148=124×1+24\)
We consider now the new divisor \(124\) and the new remainder \(24\) and apply the division lemma to get
\(124=24×5+4\)
We consider the new divisor \(24\) and the new remainder \(4\) and apply the division lemma to get
\(24=4×6+0\)
We observe that the remainder at this stage is zero. The divisor at this stage is \(4\). Therefore, the HCF of \(4052\) and \(12576\) is \(4\).

Q.3. Use Euclid’s division algorithm to find the HCF of \(441, 567\) and \(693\).
Ans: Let us first see the HCF of \(441\) and \(567\) by using Euclid’s lemma. By applying Euclid’s division lemma to the numbers \(441\) and \(567\), we get
\(567=441×1+126\)
We find the remainder is \(126\), which is a non-zero number. So, we apply Euclid’s division lemma to \(441\) (division) and \(126\) (rest) to get
\(441=126×3+63\)
Now, again apply Euclid’s division lemma to the divisor \(126\) and the remainder \(63\) to get 
\(126=63×2+0\)
The remainder at this stage is \(0\). So, the divisor of the last stage, i.e., \(63\), is the HCF of \(441\) and \(567\)
Now, use Euclid’s division lemma to find the HCF of \(63\) and \(693\). We see that
\(693=63×11+0\)
So, the third number, \(693\) and \(63\) (the HCF of the first two numbers, \(441\) and \(567\), is \(63\).
Hence, the HCF of \(441, 567\), and \(693\) is \(63\).

Q.4. Use Euclid’s algorithm to find the HCF of the given numbers \(65\) and \(117\).
Ans: Since \(117>65\), we apply the division lemma to \(117\) and \(65\) to get
\(117=65×1+52\)
Thus, you can see \(52≠0\). You will apply the division lemma to the numbers \(65\) and \(52\) to get
\(65=52×1+13\)
Here \(13≠0\), we apply the division lemma to \(52\) and \(13\) to get
\(52=13×4+0\)
The remainder has now become zero. Therefore, the divisor at this stage is \(13\), the HCF of \(117\) and \(52\) is \(13\).

Q.5. Any contingent of \(616\) members marches behind an army band of \(32\) members in a parade. Now, a couple of groups are said to march in a similar number of columns. What is the maximum number of columns in which they can march?
Ans: The maximum number of columns is the HCF of \(616\) and \(32\). To find the HCF of \(616\) and \(32\), let us apply Euclid’s division lemma to \(616\) and \(32\) to get
\(616=32×19+8\) 
Let us now take the divisor \(32\) as dividend and remainder \(8\) as the divisor and apply Euclid’s division lemma to get
\(32=8×4+0\)
Since the remainder at this stage is zero. Therefore, the last divisor, i.e., \(8\), is the HCF of \(616\) and \(32\).
Hence, the maximum number of columns in which the people can march is \(8\).

Summary

In the given article, we have discussed the definition of Euclid’s division algorithm, and then we talked about Euclid’s division algorithm proof with examples. We glanced at Euclid’s division algorithm formulas and then provided some solved examples along with a few FAQs.

Frequently Asked Question (FAQs) – Euclid’s Division Algorithm

Q.1. Explain Euclid’s division algorithm?
Ans: 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.

Q.2. How to implement Euclid’s division algorithm?
Ans: 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.
It works because if \(a=b(q)+r\), then HCF \((a,b)=HCF(b,r)\).

Q.3. What are examples of Euclid’s division algorithm?
Ans: Let us first see the HCF of \(20\) and \(75\) by using Euclid’s lemma. By applying Euclid’s division lemma to the numbers \(20\) and \(75\), we get
\(75=20×3+15\)
We find the remainder is \(15\), which is a non-zero number. So, we apply Euclid’s division lemma again to get
\(20=15×1+5\)
We find the remainder is \(5\), which is a non-zero number. So, we apply Euclid’s division lemma again to get
\(15=5×3+0\)
The remainder at this stage is \(0\). So, the division at the previous stage, i.e., \(5\), is the HCF of \(75\) and \(20\)

Q.4. What are the uses of Euclid’s division algorithm?
Ans: Euclid’s division algorithm is used to determine the highest common factor (HCF) of any two numbers where we use Euclid’s division lemma.

Q.5. What is the use of Euclid’s division algorithm in class \(10\)?
Ans: Euclid’s division algorithm is the technique to compute the Highest Common Factor (HCF) of any two positive integers. The HCF of two positive integers \(a\) and \(b\) is the most significant positive integer \(d\) that divides both \(a\) and \(b\).

We hope you find this detailed article on Euclid’s division algorithm helpful. If you have any doubts or queries on this topic, feel to ask us in the comment section. Happy learning!

Stay tuned to Embibe for more updates on Euclid’s Division Lemma!