Division Algorithm: Euclid’s Division Lemma, Fundamental Theorem

Division Algorithm, as the name suggests, has to do with the divisibility of integers. Stated simply, it says any positive integer \(p\) can be divided by another positive integer \(q\) in such a way that it leaves a remainder \(r\) that is smaller than \(q.\) Many of us probably acknowledge this as the usual long division process.

Though this result is easy to state and understand, it has numerous applications that are associated with the divisibility properties of integers. We will see a few of them and use them mainly to compute the \(HCF\) of two positive integers.

In this article, we will discuss in detail about Division Algorithm: Euclid’s Division Lemma, Fundamental Theorem, etc. Continue reading to know more.

Define Division Algorithm

The division algorithm is an algorithm in which two integers \(a\) and \(b\) are given and the algorithm computes the quotient \(q\) and remainder \(r,\) where \(0 \le r < \left| b \right|.\) There are several different algorithms that could be implemented.

Let’s say we have to divide \(a\) (dividend) by \(b\) (divisor). Subtract \(b\) from \(a\) repeatedly, i.e. \(a – b – b – b – …\) until we get a result that lies between \(0\) (inclusive) and \(b\) (exclusive) and is the smallest non-negative number obtained by repeated subtraction. The resulting number is the remainder \(r,\) and the number of times that \(b\) is subtracted is called the quotient \(q.\)

That is, for every pair of positive integers \(a\) and \(b,\) we have found whole numbers \(q\) and \(r,\) satisfying the relation: \(a = bq + r,\,0 \le r < b\)
Note that \(q\) or \(r\) can also be zero.

The formal declaration of this result is as follows:
Euclid’s Division Lemma: Given positive integers \(a\) and \(b,\) there exist unique integers \(q\) and \(r\) satisfying \(a = bq + r,\,0 \le r < b.\)

Example of Division Algorithm

To get used to what Euclid’s division lemma is, consider the following pair of integers: \(17,\,6\)
Now, \(17 = 6 \times 2 + 5\) (\(6\) gets into \(17\) two times and gives a remainder \(5\))
\(5 = 12 \times 0 + 5\) (This relationship holds because \(12\) is bigger than \(5\))
\(20 = 4 \times 5 + 0\) (Here \(4\) gets into \(20\) five-times and leaves no remainder)

Division Algorithm Method

The algorithm is a series of well-defined steps which gives a procedure for solving a type of problem.
Euclid’s division algorithm is a methodology to calculate the Highest Common Factor \(\left( {HCF} \right)\) of two specified positive integers.

Remember that the \(HCF\) of two positive integers \(a\) and \(b\) is the largest positive integer \(d\) that divides both \(a\) and \(b.\) Let’s have a look at how the algorithm works through an example.

Suppose we have to calculate the \(HCF\) of the numbers \(455\) and \(42.\) We begin with the bigger whole number \(455.\) Then, we use Euclid’s lemma to get
\(455 = 42 \times 10 + 35\)
Now, consider the divisor \(42\) and the remainder \(35,\) and apply the division lemma to get
\(42 = 35 \times 1 + 7\)
Now, consider the divisor \(35\) and the remainder \(7,\) and apply the division lemma to get
\(35 = 7 \times 5 + 0\)
Notice that the remainder has become zero, and we cannot proceed any further. We claim that the \(HCF\) of \(455\) and \(42\) is the divisor at this stage, i.e., \(7.\) You can easily verify this by listing all the factors of \(455\) and \(42.\)

Why does this method work? It works because of the above result.
So, let us state Euclid’s division algorithm clearly. To obtain the \(HCF\) of two positive integers, say \(c\) and \(d,\) with \(c > d,\) follow the steps below:

Step \(1:\) Apply Euclid’s division lemma to \(c\) and \(d.\) So, we find whole numbers, \(q\) and \(r\) such that \(c = dq + r,\,0 \le r < d.\)

Step \(2:\) If \(r = 0,\,d\;\) is the \(HCF\) of \(c\) and \(d.\) If \(r \ne 0,\) apply the division lemma to \(d\) and \(r.\)

Step \(3:\) To Proceed With the process till the remainder is zero.

This algorithm works because \(HCF(c,\,d) = HCF(d,\,r)\) where the symbol \(HCF(c,\,d)\) denotes the \(HCF\) of \(c\) and \(d,\) etc.
Euclid’s division lemma and algorithm are thus closely interlinked that people often call the former the division algorithm as well. Even though Euclid’s Division Algorithm is stated for only positive integers, it can be extended for all integers except zero, i.e., \(b \ne 0.\)

Fundamental Theorem of Arithmetic

Each composite number can be stated (factorised) as a specific product of primes, and this factorisation is unique, except for the sequence in which the prime factors arise. That is, for any composite number, there is one and only one way to write it as a product of primes unless we are specific about the sequence in which the primes arise.

For example, here \(2 \times 3 \times 5 \times 7\) as identical to the \(3 \times 5 \times 7 \times 2\) or any other conceivable order in which these primes are being written.
This fact is also stated in the following form: The prime factorisation of a natural number is unique, except for the order of its factors.

In general, given a composite number \(x,\) we factorise it as \(x = {p_1} \times {p_2} \times \ldots \ldots {p_n},\) where \({p_1},\,{p_2}, \ldots ,{p_n}\) are primes and arranged in ascending order, i.e., \({p_1} \le {p_2} \le \ldots \le {p_n}.\) If we merge the same primes, we will get the exponents of primes.
For example, \(32760 = 2 \times 2 \times 2 \times 3 \times 3 \times 5 \times 7 \times 13 = {2^3} \times {3^2} \times 5 \times 7 \times 13.\)

Then, we have taken the decision that the order will be ascending, then the way the number is factorised is unique.

Division Algorithm for Polynomials

When we divide \(3{x^2}\) by \(x,\) we get
\(\frac{{3{x^2}}}{x} = 3x,\) here Dividend \( = 3{x^2},\) Quotient \( = 3x\) and Remainder \( = 0\)
So, \(3{x^2} = x \times 3x + 0\)

Then, the division algorithm for polynomials can be written as
\({\rm{ Dividend }} = {\rm{ (Divisor }} \times {\rm{ Quotient) }} + {\rm{ Remainder }}\)
In general, if \(p\left( x \right)\) and \(g\left( x \right)\) are two polynomials such that degree of \(p\left( x \right) \ge \) degree of \(g\left( x \right)\) and \(g\left( x \right) \ne 0,\) then we can find polynomials \(q\left( x \right)\) and \(r\left( x \right)\) such that: \(p\left( x \right) = g\left( x \right) \times q\left( x \right) + r\left( x \right),\)
Where \(r\left( x \right) = 0\) or degree of \(r\left( x \right) < \) degree of \(g\left( x \right).\) Here we say that \(p\left( x \right)\) divided by \(g\left( x \right),\) gives \(q\left( x \right)\) as quotient and \(r\left( x \right)\) as remainder.

Solved Examples – Division Algorithm

Q.1. Use Euclid’s division algorithm to find the \(HCF\) of \(135\) and \(225.\)
Ans: Now, let us use Euclid’s algorithm to find the \(HCF\) of \(135\) and \(225.\)
We have, \(225 = 135 \times 1 + 90\)
\(135 = 90 \times 1 + 45\)
\(90 = 45 \times 2 + 0\)
Therefore, the \(HCF\) of \(135\) and \(225\) is \(45.\)

Q.2. Two tankers contain \(850\) litres and \(680\) litres of water, respectively. Find the highest possible capacity of a container that can measure the water of either tanker an exact number of times.
Ans: Clearly, the maximum capacity of the container in the \(HCF\) of \(850\) and \(680\) in litres. So, let us find the \(HCF\) of \(850\) and \(680\) by Euclid’s division algorithm.
We have, \(850 = 680 \times 1 + 170\)
\(680 = 170 \times 4 + 0\)
So, the \(HCF\) of \(850\) and \(680\) is \(170.\)
Hence, the capacity of the container must be \(170.\)

Q.3. Find the largest number that divides \(2053\) and \(967\) and leaves a remainder of \(5\) and \(7\) respectively.
Ans: It is given that on dividing \(2053\) by the required number, there is a remainder of \(5.\) This means that \(2053 – 5 = 2048\) is exactly divisible by the required number.
Similarly, \(967 – 7 = 960\) is also exactly divisible by the required number.
Also, the necessary number is the greatest number satisfying the above condition. Thus, it is the \(HCF\) of \(2048\) and \(960.\)
Let us now find the \(HCF\) of \(2048\) and \(960\) by Euclid’s division algorithm.
We have, \(2048 = 960 \times 2 + 128\)
\(960 = 128 \times 7 + 64\)
\(128 = 64 \times 2 + 0\)
Clearly, the \(HCF\) of \(2048\) and \(960\) is the last divisor i.e., \(64.\) Hence, the required number is \(64.\)

Q.4. If the \(HCF\) of \(210\) and \(55\) is expressible in the form \(210 \times 5 + 55y,\) find \(y.\)
Ans: Applying Euclid’s division lemma on \(210\) and \(55,\) we get
\(210 = 55 \times 3 + 45\, \ldots \ldots {\rm{ (i) }}\)
Since the remainder \(45 \ne 0.\) So, now apply division lemma on the divisor \(55\) and the remainder \(45\) to get
\(55 = 45 \times 1 + 10\, \ldots \ldots {\rm{ (ii) }}\)
We consider the divisor \(45\) and the remainder \(10\) and apply division lemma to get
\(45 = 4 \times 10 + 5\, \ldots \ldots {\rm{ (iii) }}\)
We consider the divisor \(10\) and the remainder \(5\) and apply division lemma to get
\(10 = 5 \times 2 + 0\, \ldots \ldots {\rm{ (iv) }}\)
We observe that the remainder at this stage is zero. So, the last divisor i.e., \(55\) is the \(HCF\) of \(210\) and \(55.\)
Therefore, \(210 \times 5 + 55y = 5\)
\( \Rightarrow 55y = 5 – 210 \times 5 = 5 – 1050\)
\( \Rightarrow 55y = – 1045\)
\( \Rightarrow y = \frac{{ – 1045}}{{55}} = – 19\)
Hence, the \(y\) value is \( – 19.\)

Q.5. In the workshop, the number of attendees in Science, Social and Mathematics are \(60,\,84\) and \(108,\) respectively. Find the least number of rooms necessary when in each room the exact same number of attendees are to be seated and all of them being in the same subject.
Ans: The number of attendees in each room must be \(HCF\) of \(60,\,84\) and \(108.\)
To find the \(HCF\) of \(60,\,84\) and \(108,\) we first find the \(HCF\) of \(60\) and \(84\) by Euclid’s division algorithm:
That is, \(84 = 60 \times 1 + 24\)
\(60 = 24 \times 2 + 12\)
\(24 = 12 \times 2 + 0\)
So, the \(HCF\) of \(60\) and \(84\) is \(12.\)
Now, we find the \(HCF\) of \(12\) and \(108.\)
Clearly, the \(HCF\) of \(12\) and \(108\) is \(12.\)
Hence, the \(HCF\) of \(60,\,84\) and \(108\) is \(12.\)
Therefore, in each room maximum \(12\) attendees can be seated.
We have,
Total number of attendees \( = 60 + 84 + 108 = 252\)
Therefore, number of rooms required \( = \frac{{252}}{{12}} = 21.\)

Summary

In this article, we learnt about the definition of the division algorithm, the example of the division algorithm, division algorithm method, fundamental theorem of arithmetic, division algorithm for polynomials, solved examples on division algorithm, frequently asked questions on division algorithm. The learning outcome of this article is how to use the division algorithm to compute the \(HCF\) of two positive integers.

Frequently Asked Questions

We have provided some frequently asked questions about division algorithm here:

Q.1. What is the division algorithm? Explain with example?
Ans: The algorithm is a series of well-defined steps which gives a procedure for solving a type of problem.
Euclid’s division algorithm is a methodology to calculate the Highest Common Factor \(\left( {HCF} \right)\) of two specified positive integers. Remember that the \(HCF\) of two positive integers \(a\) and \(b\) is the largest positive integer \(d\) that divides both \(a\) and \(b.\)
Let’s have a look at how the algorithm works through an example. Suppose we have to calculate the \(HCF\) of the numbers \(455\) and \(42.\) We begin with the bigger whole number \(455.\) Then, we use Euclid’s lemma to get,
\(455 = 42 \times 10 + 35\)
Now consider the divisor \(42\) and the remainder \(35,\) and apply the division lemma to get,
\(42 = 35 \times 1 + 7\)
Now consider the divisor \(35\) and the remainder \(7\)\ and apply the division lemma to get,
\(35 = 7 \times 5 + 0\)
Hence, the \(HCF\) of \(455\) and \(42\) is \(7.\)

Q.2. What is the meaning of algorithms?
Ans: An algorithm is a sequence of well-defined steps that solve a type of problem.

Q.3. What is the division algorithm for lower classes (class \(5?\)
Ans: Division algorithm for class \(5\) is, \({\rm{ Dividend }} = {\rm{ Divisor }} \times {\rm{ Quotient }} \times {\rm{ Remainder}}{\rm{. }}\)
The remainder must always be lesser than the divisor.

Q.4. What is Euclid Division Lemma?
Ans: Euclid’s division lemma tells us about the divisibility of integers. It is quite easy to state and understand. It states that any positive integer \(a\) can be divided by any other positive integer \(b\) in such a way that it leaves a remainder \(r\) that is smaller than \(b.\) This is nothing but the usual long division process. Euclid’s division lemma provides us with a step-wise procedure to compute the \(HCF\) of two positive integers. This step-wise procedure is known as Euclid’s algorithm. We will use the same for finding the \(HCF\) of positive integers.

Q.5. What is the division algorithm formula for grade \(10\) students?
Ans: Euclid’s Division Lemma: Given positive integers \(a\) and \(b,\) there exist unique integers \(q\) and \(r\) satisfying \(a = bq + r,\,0 \le r < b.\)

We hope this detailed article on division algorithm helped you in your studies. If you have any doubts or queries regarding this topic, feel to ask us in the comment section.