Loading [MathJax]/extensions/TeX/boldsymbol.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

5.2: Division Algorithm

( \newcommand{\kernel}{\mathrm{null}\,}\)

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

This page titled 5.2: Division Algorithm is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Harris Kwong (OpenSUNY) .

Support Center

How can we help?