Division Algorithm

The division algorithm is an algorithm in which given 2 integers \(N\) and \(D\), it computes their quotient \(Q\) and remainder \(R\), where \( 0 \leq R < |D|\). There are many different algorithms that could be implemented, and we will focus on division by repeated subtraction. This is very similar to thinking of multiplication as repeated addition. \[\]

Mac Berger is falling down the stairs. He slips from the top stair to the \(2^\text{nd},\) then to the \(4^\text{th},\) to the \(6^\text{th},\) and so on and so forth. If you're standing on the \(11^\text{th}\) stair, how many steps would Mac Berger hit before reaching you?

To solve problems like this, we will need to learn about the division algorithm. We will explain how to think about division as repeated subtraction, and apply these concepts to solving several real-world examples using the fundamentals of mathematics!

Let's say we have to divide \(N\) (dividend) by \(D \) (divisor). We will take the following steps:

Step 1: Subtract \( D \) from \(N \) repeatedly, i.e. \( N - D - D - D - \cdots \) until we get a result that lies between 0 (inclusive) and \(D\) (exclusive) and is the smallest non-negative number obtained by repeated subtraction.

Step 2: The resulting number is known as the remainder \(R\), and the number of times that \(D\) is subtracted is called the quotient \(Q\).

Let's experiment with the following examples to be familiar with this process:

Describe the distribution of 7 slices of pizza among 3 people using the concept of repeated subtraction.

---

We have 7 slices of pizza to be distributed among 3 people. We initially give each person one slice, so we give out 3 slices leaving \( 7-3 = 4 \). We then give each person another slice, so we give out another 3 slices leaving \( 4 - 3 = 1 \). We are now unable to give each person a slice. So, each person has received 2 slices, and there is 1 slice left. \(_\square\)

Divide 21 by 5 and find the remainder and quotient by repeated subtraction.

---

Subtracting 5 from 21 repeatedly till we get a result between 0 and 5. This gives us

\[ \begin{array} { r l l } 21 & -5 & = 16 \\ 16 & -5 & = 11 \\ 11 & -5 & = 6 \\ 6 & -5 & = 1 .\\ \end{array} \]

At this point, we cannot subtract 5 again. Hence 4 is the quotient (we subtracted 5 from 21 four times) and 1 is the remainder. We say that

\[ 21 = 5 \times 4 + 1. \ _\square \]

What happens if \(N\) is negative? Then, we cannot subtract \(D\) from it, since that would make the term even more negative. Instead, we want to add \(D\) to it, which is the inverse function of subtraction. This will result in the quotient being negative. Remember that the remainder should, by definition, be non-negative. Let's look at another example:

Find the remainder when \(-21\) is divided by \(5.\)

---

We now have to add 5 to -21 repeatedly or, in other words, we have to subtract -5 repeatedly till we get a result between 0 and 5. This gives us

\[ \begin{array} { r l l } -21 & +5 & = -16 \\ -16 & +5 & = -11 \\ -11 & +5 & =- 6 \\ -6 & +5 & = -1 \\ -1 & + 5 & = 4. \\ \end{array} \]

At this point, we cannot add 5 again. Hence, the quotient is -5 (because the dividend is negative) and the remainder is 4. We say that

\[ -21 = 5 \times (-5 ) + 4 . \ _\square\]

Let us recap the definitions of various terms that we have come across.

• Division algorithm: Let \(N\) and \(D\) be integers. Then there exist unique integers \(Q\) and \(R\) such that \(N = Q \times D + R,\) where \(0 \leq R < |D|.\)
• Dividend/Numerator (N): The number which gets divided by another integer is called as the dividend or numerator.
• Divisor/Denominator (D): The number which divides the dividend is called as the divisor or denominator.
• Quotient (Q): The result obtained as the division of the dividend by the divisor is called as the quotient.
• Remainder (R): If the dividend is not divided completely by the divisor, then the number left at the end of the division is called the remainder.

Now, try out the following problem to check if you understand these concepts:

Through the above examples, we have learned how the concept of repeated subtraction is used in the division algorithm. If you are familiar with long division, you could use that to help you determine the quotient and remainder in a faster manner.

Now that you have an understanding of division algorithm, you can apply your knowledge to solve problems involving division algorithm. Let's start with working out the example at the top of this page:

Mac Berger is falling down the stairs. He slips from the top stair to the \(2^\text{nd},\) then to the \(4^\text{th},\) to the \(6^\text{th}\) and so on and so forth. If you're standing on the \(11^\text{th}\) stair, how many steps would Mac Berger hit before reaching you?

---

Let Mac Berger fall \(m\) times till he reaches you. Using the division algorithm, we get \(11 = 2 \times 5 + 1\). Hence, Mac Berger will hit 5 steps before finally reaching you. \(_\square\)

Let's look at other interesting examples and problems to better understand the concepts:

Your birthday cake had been cut into equal slices to be distributed evenly to 5 people. But since one person couldn't make it to the party, those slices were eventually distributed evenly among 4 people, with each person getting 1 additional slice than originally planned and two slices left over. How many equal slices of cake were cut initially out of your birthday cake?

---

Let \(x\) be the number of slices cut initially, and \(n\) the number of slices each of the 5 people was supposed to get. Then since each person gets the same number of slices, on applying the division algorithm we get \(x=5\times n. \qquad (1)\)

Now, since the slices were actually distributed evenly among 4 people leaving behind 2 slices, using the division algorithm we have \(x=4\times (n+1)+2. \qquad (2)\)

Equating \((1)\) and \((2),\) we have \(5n=4n+6 \implies n=6\). Putting \(n=6\) into \((1)\) or \((2)\) gives \(x=30\), which tells us that the total number of slices of your birthday cake was \(30.\) \(_\square\)

There are 24 hours in one complete day. How many complete days are contained in 2500 hours?

---

To get the number of days in 2500 hours, we need to divide 2500 by 24. Hence, using the division algorithm we can say that

\[2500=24 \times 104+4.\]

Since the quotient comes out to be 104 here, we can say that 2500 hours constitute of 104 complete days. \(_\square\)

You are walking along a row of trees numbered from 789 to 954. How many trees will you find marked with numbers which are multiples of 8?

---

When we divide 798 by 8 and apply the division algorithm, we can say that \(789=8\times 98+5\). Hence the smallest number after 789 which is a multiple of 8 is 792.

Similarly, dividing 954 by 8 and applying the division algorithm, we find \(954=8\times 119+2\) and hence we can conclude that the largest number before 954 which is a multiple of 8 is \(954-2=952.\)

So the number of trees marked with multiples of 8 is

\[\dfrac{952-792}{8}+1=21. \ _\square\]

A wise man said, "An ounce of practice is worth more than a tonne of preaching!" So let's have some practice and solve the following problems:

The division algorithm might seem very simple to you (and if so, congrats!). It actually has deeper connections into many other areas of mathematics, and we will highlight a few of them. These extensions will help you develop a further appreciation of this basic concept, so you are encouraged to explore them further!

1. Euclidean Algorithm

Main article: Euclidean Algorithm

The Euclidean algorithm offers us a way to calculate the greatest common divisor of two integers, through repeated applications of the division algorithm. It is based off of the following fact:

If \(a, b, q, r \) are integers such that \(a=bq+r\), then \( \gcd(a,b) = \gcd(b,r).\ _\square \)

2. Modular Arithmetic

Main article: Modular Arithmetic

Modular arithmetic is a system of arithmetic for integers, where we only perform calculations by considering their remainder with respect to the modulus. It is useful when solving problems in which we are mostly interested in the remainder.

For example, since \( 15 = 2 \times 7 + 1 \) and \( 29 = 4 \times 7 + 1 \), we know that 15 and 29 leave the same remainder when divided by 7. In the language of modular arithmetic, we say that

\[ 15 \equiv 29 \pmod{7} . \]

3. Polynomial Division

Main article: Polynomial Division

Polynomial division refers to performing the division algorithm on polynomials instead of integers. For example,

\[ a(x) = b(x) \times d(x) + r(x),\]

where the remainder \(r(x)\) is a polynomial with degree smaller than the degree of the divisor \(d(x) \).