5.2: Division Algorithm

When we divide a positive integer (the dividend) by another positive integer (the divisor), we obtain a quotient. We multiply the quotient to the divisor, and subtract the product from the dividend to obtain the remainder. Such a division produces two results: a quotient and a remainder.

This is how we normally divide 23 by 4:

\[ \require{enclose}
\begin{array}{rll}
5 && \\[-3pt]
4 \enclose{longdiv}{23}\kern-.2ex \\[-3pt]
\underline{\phantom{0}20} && \\[-3pt]
\phantom{00}3
\end{array} \nonumber\]

In general, the division \(b\div a\) takes the form

\[ \require{enclose}
\begin{array}{rll}
q && \\[-3pt]
a \enclose{longdiv}{\phantom{0}b}\kern-.2ex \\[-3pt]
\underline{\phantom{0}aq} && \\[-3pt]
\phantom{00}r
\end{array} \nonumber\]

so that \(r=b-aq\), or equivalently, \(b=aq+r\). Of course, both \(q\) and \(r\) are integers. Yet, the following “divisions”

\[{ \require{enclose}\begin{array}{rll}
4 && \\[-3pt]
4 \enclose{longdiv}{23}\kern-.2ex \\[-3pt]
\underline{\phantom{0}16} && \\[-3pt]
\phantom{00}7
\end{array}}{\require{enclose}
\begin{array}{rll}
2 && \\[-3pt]
4 \enclose{longdiv}{23}\kern-.2ex \\[-3pt]
\underline{\phantom{0}8} && \\[-3pt]
\phantom{00}15
\end{array}}{\require{enclose}
\begin{array}{rll}
6 && \\[-3pt]
4 \enclose{longdiv}{23}\kern-.2ex \\[-3pt]
\underline{\phantom{0}24} && \\[-3pt]
\phantom{00}-1
\end{array}}{\require{enclose}
\begin{array}{rll}
7 && \\[-3pt]
4 \enclose{longdiv}{23}\kern-.2ex \\[-3pt]
\underline{\phantom{0}28} && \\[-3pt]
\phantom{00}-5
\end{array}} \nonumber\]

also satisfy the requirement \(b=aq+r\), but that is not what we normally do. This means having \(b=aq+r\) alone is not enough to define what quotient and remainder are. We need a more rigid definition.

Theorem \(\PageIndex{1}\label{thm:divalgo}\)

Given any integers \(a\) and \(b\), where \(a>0\), there exist integers \(q\) and \(r\) such that \[b = aq + r, \nonumber\] where \(0\leq r< a\). Furthermore, \(q\) and \(r\) are uniquely determined by \(a\) and \(b\).

The integers \(b\), \(a\), \(q\), and \(r\) are called the dividend, divisor, quotient, and remainder, respectively. Notice that \(b\) is a multiple of \(a\) if and only if \(r=0\).

The division algorithm describes what happens in long division. Strictly speaking, it is not an algorithm. An algorithm describes a procedure for solving a problem. The theorem does not tell us how to find the quotient and the remainder. Some mathematicians prefer to call it the division theorem. Here, we follow the tradition and call it the division algorithm.

Remark

This is the outline of the proof:

1. Describe how to find the integers \(q\) and \(r\) such that \(b=aq+r\).
2. Show that our choice of \(r\) satisfies \(0\leq r< a\).
3. Establish the uniqueness of \(q\) and \(r\).

Regarding the last part of the proof: to show that a certain number \(x\) is uniquely determined, a typical approach is to assume that \(x'\) is another choice that satisfies the given condition, and show that we must have \(x=x'\).

Proof

We first show the existence of \(q\) and \(r\). Let \[S = \{ b-ax \mid x\in\mathbb{Z} \mbox{ and } b-ax\geq 0 \}. \nonumber\] Clearly, \(S\) is a set of nonnegative integers. To be able to apply the principle of well-ordering, we need to show that \(S\) is nonempty. Here is a constructive proof.

• Case 1. If \(b\geq 0\), we can set \(x=0\). Then \(b-ax=b\geq0\).
• Case 2. If \(b < 0\), set \(x=b\).
• Since \(a\geq1\), we have \(1-a\leq0\). Then \[b-ax = b-ab = b(1-a) \geq 0. \nonumber\]

Since \(S\) is nonempty, it follows from the principle of well-ordering that \(S\) has a smallest element. Call it \(r\). From the definition of \(S\), there exists some integer \(q\) such that \(b − aq = r\).

Step 2: Show that r satisfies the criterion \(0 \leq r < a\).

Next, we show that \(0 \leq r < a\). The definition of \(S\) tells us immediately that \(r \geq 0\), so we only need to show that \(r < a\). Suppose, on the contrary, \(r \geq a\). Then \(r = a + t\) for some integer \(t \geq 0\). Now \(b − aq = r = a + t\) implies that \[0 \leq t = b − aq − a = b − a(q + 1). \nonumber\]

So \(t \in S\). Now \(t = r − a < r\) suggests that we have found another element in \(S\) which is even smaller than \(r\). This contradicts the minimality of \(r\). Therefore \(r < a\).

Finally, we have to establish the uniqueness of both \(q\) and \(r\). Let \(q'\) and \(r'\) be integers such that \[b=aq'+r', \qquad 0\leq r'< a. \nonumber\] From \(aq+r = b = aq'+r'\), we find \(a(q-q') = r'-r\). Hence \[a\,|q-q'| = |r'-r|. \nonumber\] Since \(|r'-r|\) is an integer, if \(|r'-r|\neq0\), we would have \(a\leq |r'-r|\). From \(0\leq r,r'<a\), we deduce that \(|r'-r|<a\), which clearly contradicts our observation that \(a\leq|r'-r|\). Hence, \(|r'-r|=0\). Then \(r'=r\). It follows that \(q'=q\). So the quotient \(q\) and the remainder \(r\) are unique.

Since \(S\) is nonempty, it follows from the principle of well-ordering that \(S\) has a smallest element. Call it \(r\). From the definition of \(S\), there exists some integer \(q\) such that \(b-aq=r\).

Next, we show that \(0\leq r<a\). The definition of \(S\) tells us immediately that \(r\geq0\), so we only need to show that \(r<a\). Suppose, on the contrary, \(r\geq a\). Then \(r = a+t\) for some integer \(t\geq 0\). Now \(b-aq = r = a + t\) implies that \[0 \leq t = b-aq-a = b-a(q+1). \nonumber\] So \(t\in S\). Now \(t = r-a < r\) suggests that we have found another element in \(S\) which is even smaller than \(r\). This contradicts the minimality of \(r\). Therefore \(r < a\).

You should not have any problem dividing a positive integer by another positive integer. This is the kind of long division that we normally perform. It is more challenging to divide a negative integer by a positive integer. When \(b\) is negative, the quotient \(q\) will be negative as well, but the remainder \(r\) must be nonnegative. In a way, \(r\) is the deciding factor: we choose \(q\) such that the remainder \(r\) satisfies the condition \(0\leq r<a\).

In general, for any integer \(b\), dividing \(b\) by \(a\) produces a decimal number. If the result is not an integer, round it down to the next smaller integer (see Example 6.1.3). It is the quotient \(q\) that we want, and the remainder \(r\) is obtained from the subtraction \(r=b-aq\). For example, \[\frac{-22}{\;\;7} = -3.1428\ldots\,. \nonumber\] Rounding it down produces the quotient \(q=-4\), and the remainder is \(r=-22-7(-4)=6\); and we do have \(-22=7\cdot(-4)+6\).

hands-on Exercise \(\PageIndex{1}\label{he:divalgo-01}\)

Compute the quotients \(q\) and the remainders \(r\) when \(b\) is divided by \(a\):

1. \(b= 128\), \(a=7\)
2. \(b=-128\), \(a=7\)
3. \(b=-389\), \(a=16\)

Be sure to verify that \(b=aq+r\).

The division algorithm can be generalized to any nonzero integer \(a\).

Corollary \(\PageIndex{2}\label{cor:divalgo}\)

Given any integers \(a\) and \(b\) with \(a\neq 0\), there exist uniquely determined integers \(q\) and \(r\) such that \(b = aq +r\), where \(0\leq r < |a|\).

Proof

We only have to consider the case of \(a<0\). Since \(-a>0\), the original Euclidean Algorithm assures that there exist uniquely determined integers \(q'\) and \(r\) such that \[b = (-a)\cdot q' + r, \nonumber\] where \(0\leq r<-a=|a|\). Therefore, we can set \(q=-q'\).

example \(\PageIndex{1}\label{eg:divalgo-01}\)

Not every calculator or computer program computes \(q\) and \(r\) the way we want them done in mathematics. The safest solution is to compute \(|b| \div |a|\) in the usual way, inspect the remainder to see if it fits the criterion \(0\leq r<|a|\). If necessary, adjust the value of \(q\) so that the remainder \(r\) satisfies the requirement \(0\leq r<|a|\). Here are some examples: \[\begin{array}{|r|r|r@{\;=\;}l|r|r|} \hline b & a & b & aq+r & q & r \\ \hline 14 & 4 & 14 & 4\cdot3+2 & 3 & 2 \\ -14 & 4 & -14 & 4\cdot(-4)+2 & -4 & 2 \\ -17 & -3 & -17 & (-3)\cdot6+1 & 6 & 1 \\ 17 & -3 & 17 & (-3)\cdot(-5)+2 & -5 & 2 \\ \hline \end{array} \nonumber\]

The quotient \(q\) can be positive or negative, and the remainder \(r\) is always nonnegative.

Definition

Given integers \(a\) and \(b\), with \(a\neq 0\), let \(q\) and \(r\) denote the unique integers such that \(b=aq+r\), where \(0\leq r<|a|\). Define the binary operators \(\mathrm{ div }\) and \(\bmod\) as follows:

Therefore, \(b ~ \mathrm{ div } ~ a\) gives the quotient, and \(b\bmod a\) yields the remainder of the integer division \(b\div a\). Recall that \(b ~ \mathrm{ div } ~ a\) can be positive, negative, or even zero. But \(b\bmod a\) is always a nonnegative integer less than \(|a|\).

example \(\PageIndex{2}\label{eg:divalgo-02}\)

From the last example, we have

• \(14 ~ \mathrm{ div } ~ 4 = 3\), and \(14\bmod 4 = 2\).
• \(-14 ~ \mathrm{ div } ~ 4 =-4\), and \(-14\bmod 4 = 2\).
• \(-17 ~ \mathrm{ div } ~ -3 = 6\), and \(-17\bmod-3 = 1\).
• \(17 ~ \mathrm{ div } ~ -3 =-5\), and \(17\bmod-3 = 2\).

Do not forget to check the computations, and remember that \(a\) need not be positive.

hands-on Exercise \(\PageIndex{2}\label{he:divalgo-02}\)

Complete the following table:

\[\begin{array}{|r|r|r|r|} \hline b & a & b ~ \mathrm{ div } ~ a & b\bmod a \\ \hline 334 & 15 & \qquad\qquad & \qquad\qquad \\ 334 & -15 & & \\ -334 & 15 & & \\ -334 & -15 & & \\ \hline \end{array} \nonumber\] Do not forget: \(b\bmod a\) is always nonnegative.

example \(\PageIndex{3}\label{eg:divalgo-03}\)

Let \(n\) be an integer such that \[n ~ \mathrm{ div } ~ 6 = q, \qquad \mbox{and} \qquad n\bmod6 = 4. \nonumber\] Determine the values of \((2n+5) ~ \mathrm{ div } ~ 6\), and \((2n+5)\bmod6\).

Solution

The given information implies that \(n=6q+4\). Then \[2n+5 = 2(6q+4)+5 = 12q+13 = 6(2q+2)+1. \nonumber\] Therefore, \((2n+5) ~ \mathrm{ div } ~ 6 = 2q+2\), and \((2n+5)\bmod6 = 1\).

hands-on Exercise \(\PageIndex{3}\label{he:divalgo-03}\)

Let \(n\) be an integer such that \[n ~ \mathrm{ div } ~ 11 = q, \qquad\mbox{and}\qquad n\bmod11 = 5. \nonumber\] Compute the values of \((6n-4) ~ \mathrm{ div } ~ 11\) and \((6n-4)\bmod11\).

example \(\PageIndex{4}\label{eg:divalgo-04}\)

Suppose today is Wednesday. Which day of the week is it a year from now?

Solution

Denote Sunday, Monday, … , Saturday as Day 0, 1, …  6, respectively. Today is Day 3. A year (assuming 365 days in a year) from today will be Day 368. Since \[368 = 7\cdot52+4, \nonumber\] it will be Day 4 of the week. Therefore, a year from today will be Thursday.

hands-on Exercise \(\PageIndex{4}\label{he:divalgo-04}\)

Suppose today is Friday. Which day of the week is it 1000 days from today?

Any integer divided by 7 will produce a remainder between 0 and 6, inclusive. Define \[A_i = \{ x\in\mathbb{Z} \mid x\bmod 7 = i \} \quad\mbox{ for } 0\leq i\leq 6, \nonumber\] we find \[\mathbb{Z} = A_0\cup A_1\cup A_2\cup A_3\cup A_4\cup A_5\cup A_6, \nonumber\] where the sets \(A_i\) are pairwise disjoint. The collection of sets \[\{A_0,A_1,A_2,A_3,A_4,A_5,A_6\} \nonumber\] is called a partition of \(\mathbb{Z}\), because every integer belongs to one and only one of these seven subsets. We also say that \(\mathbb{Z}\) is a disjoint union of \(A_0,A_1,\ldots,A_6\). The same argument also applies to the division by any integer \(n\geq2\).

In general, a collection or family of finite sets \(\{S_1,S_2,\ldots, S_n\}\) is called a partition of the set \(S\) if \(S\) is the disjoint union of \(S_1,S_2,\ldots\,S_n\). Partition is a very important concept, because it divides the elements of \(S\) into \(n\) classes \(S_1,S_2,\ldots,S_n\) such that every element of \(S\) belongs to a unique class. We shall revisit partition again when we study relations in Chapter 7.

Summary and Review

• The division of integers can be extended to negative integers.
• Given any integer \(b\), and any nonzero integer \(a\), there exist uniquely determined integers \(q\) and \(r\) such that \(b=aq+r\), where \(0\leq r<|a|\).
• We call \(q\) the quotient, and \(r\) the remainder.
• The reason we have unique choices for \(q\) and \(r\) is the criterion we place on \(r\). It has to satisfy the requirement \(0\leq r<|a|\).
• In fact, the criterion \(0\leq r<|a|\) is the single most important deciding factor in our choice of \(q\) and \(r\).
• We define two binary operations on integers. The \(\mathrm{ div }\) operation yields the quotient, and the \(\bmod\) operation produces the remainder, of the integer division \(b\div a\). In other words, \(b ~ \mathrm{ div } ~ a=q\), and \(b\bmod a=r\).

Exercises 5.2

exercise \(\PageIndex{1}\label{ex:divalgo-01}\)

Find \(b ~ \mathrm{ div } ~ a\) and \(b\bmod a\), where

1. \(a= 13\), \(b= 300\)
2. \(a= 11\), \(b=-120\)
3. \(a=-22\), \(b= 145\)

exercise \(\PageIndex{2}\label{ex:divalgo-02}\)

Find \(b ~ \mathrm{ div } ~ a\) and \(b\bmod a\), where

1. \(a= 19\), \(b= 79\)
2. \(a= 59\), \(b= 18\)
3. \(a= 16\), \(b=-823\)
4. \(a=-16\), \(b= 172\)
5. \(a=- 8\), \(b=- 67\)
6. \(a=-12\), \(b=-134\)

exercise \(\PageIndex{3}\label{ex:divalgo-03}\)

Prove that \[b\bmod a \in\{0,1,2,\ldots,|a|-1\} \nonumber\] for any integers \(a\) and \(b\), where \(a\neq0\).

exercise \(\PageIndex{4}\label{ex:divalgo-04}\)

Prove that among any three consecutive integers, one of them is a multiple of 3.

Hint

Let the three consecutive integers be \(n\), \(n+1\), and \(n+2\). What are the possible values of \(n\bmod3\)? What does this translate into, according to the division algorithm? In each case, what would \(n\), \(n+1\), and \(n+2\) look like?

exercise \(\PageIndex{5}\label{ex:divalgo-05}\)

Prove that \(n^3-n\) is always a multiple of 3 for any integer \(n\) by

1. A case-by-case analysis.
2. Factoring \(n^3-n\).

exercise \(\PageIndex{6}\label{ex:divalgo-06}\)

Prove that the set \(\{n,n+4,n+8,n+12,n+16\}\) contains a multiple of 5 for any positive integer \(n\).

exercise \(\PageIndex{7}\label{ex:divalgo-07}\)

Let \(m\) and \(n\) be integers such that \[m ~ \mathrm{ div } ~ 5 = s, \qquad m\bmod5=1, \qquad n ~ \mathrm{ div } ~ 5 = t, \qquad n\bmod5=3. \nonumber\] Determine

1. \((m+n) ~ \mathrm{ div } ~ 5\)
2. \((m+n)\bmod5\)
3. \((mn) ~ \mathrm{ div } ~ 5\)
4. \((mn)\bmod5\)

exercise \(\PageIndex{8}\label{ex:divalgo-08}\)

Let \(m\) and \(n\) be integers such that \[m ~ \mathrm{ div } ~ 8 = s, \qquad m\bmod8=3, \qquad n ~ \mathrm{ div } ~ 8 = t, \qquad n\bmod8=6. \nonumber\] Determine

1. \((m+2) ~ \mathrm{ div } ~ 8\)
2. \((m+2)\bmod8\)
3. \((3mn) ~ \mathrm{ div } ~ 8\)
4. \((3mn)\bmod8\)
5. \((5m+2n) ~ \mathrm{ div } ~ 8\)
6. \((5m+2n)\bmod8\)
7. \((3m-2n) ~ \mathrm{ div } ~ 8\)
8. \((3m-2n)\bmod8\)