Loading [MathJax]/jax/element/mml/optable/BasicLatin.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:

5423020_003

In general, the division b÷a takes the form

qa0b0aq_00r

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

4423016_007242308_00156423024_0017423028_005

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 5.2.1

Given any integers a and b, where a>0, there exist integers q and r such that b=aq+r, where 0r<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 0r<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={baxxZ and bax0}. 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 b0, we can set x=0. Then bax=b0.
  • Case 2. If b<0, set x=b.
  • Since a1, we have 1a0. Then bax=bab=b(1a)0.

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 baq=r.

Step 2: Show that r satisfies the criterion 0r<a.

Next, we show that 0r<a. The definition of S tells us immediately that r0, so we only need to show that r<a. Suppose, on the contrary, ra. Then r=a+t for some integer t0. Now baq=r=a+t implies that 0t=baqa=ba(q+1).

So tS. Now t=ra<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,0r<a. From aq+r=b=aq+r, we find a(qq)=rr. Hence a|qq|=|rr|. Since |rr| is an integer, if |rr|0, we would have a|rr|. From 0r,r<a, we deduce that |rr|<a, which clearly contradicts our observation that a|rr|. Hence, |rr|=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 baq=r.

Next, we show that 0r<a. The definition of S tells us immediately that r0, so we only need to show that r<a. Suppose, on the contrary, ra. Then r=a+t for some integer t0. Now baq=r=a+t implies that 0t=baqa=ba(q+1). So tS. Now t=ra<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 0r<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=baq. For example, 227=3.1428. Rounding it down produces the quotient q=4, and the remainder is r=227(4)=6; and we do have 22=7(4)+6.

hands-on Exercise 5.2.1

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 5.2.2

Given any integers a and b with a0, there exist uniquely determined integers q and r such that b=aq+r, where 0r<|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)q+r, where 0r<a=|a|. Therefore, we can set q=q.

example 5.2.1

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|÷|a| in the usual way, inspect the remainder to see if it fits the criterion 0r<|a|. If necessary, adjust the value of q so that the remainder r satisfies the requirement 0r<|a|. Here are some examples: babaq+rqr1441443+232144144(4)+24217317(3)6+16117317(3)(5)+252

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

Definition

Given integers a and b, with a0, let q and r denote the unique integers such that b=aq+r, where 0r<|a|. Define the binary operators div and mod 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?