1.5   The Division Algorithm

We begin this section with a statement of the Division Algorithm, which you saw at the end of the Prelab section of this chapter:

Theorem 1.2 (Division Algorithm) Let a be an integer and b be a positive integer. Then there exist unique integers q and r such that

a = bq + r    and    0 <= r < b.

Remember learning long division in grade school? (If not, pretend that you do.) Long division is a procedure for dividing a number a by another number b, and coming up with a quotient q and a remainder r. The Division Algorithm is really nothing more than a guarantee that good old long division really works. Although this result doesn't seem too profound, it is nonetheless quite handy. For instance, it is used in proving the Fundamental Theorem of Arithmetic, and will also appear in the next chapter. A proof of the Division Algorithm is given at the end of the "Tips for Writing Proofs" section of the Course Guide.

Now, suppose that you have a pair of integers a and b, and would like to find the corresponding q and r. If a and b are small, then you could find q and r by trial and error. However, suppose that a = 124389001 and b = 593. In this case, trial and error would be extremely tedious. What happens if we try the division using our on-line calculator? Since q is the quotient, it should be close to a/b.

Your browser does not support java.

Now we're getting somewhere. We know that a = bq + r. Dividing on both sides of the equation by b yields

a/b = q + r/b.

Thus it follows that q <= a/b. (Remember that 0 <= r < b.) So, in our above example, it makes sense to take q = 209762, because this is the biggest integer that is less than (or equal to) a/b. (Recall that this is the idea used repeatedly when performing long division by hand.) Setting the mode to "Integers" in the on-line calculator will automatically give you the "integer part" of a/b, which is the required value for q:

Your browser does not support java.
With this choice of q, what is r? That's easy enough, because we must have

abq = r.

Here's the computation:

Your browser does not support java.

Since r < b, we have fulfilled the requirements of the Division Algorithm, and we're done. Let's summarize the procedure:

  1. Begin with values of a and b;
  2. Set q equal to the integer part of a/b;
  3. Set r = abq.

The applet below automates this procedure. Enter values for a and b, and it will return the corresponding values of the quotient q and the remainder r. Try it out.

Your browser does not support java.

Exercise 3

Use the Division Algorithm applet to repeat Exercise 5 in the Prelab section of this chapter.

Section 1.1 | Section 1.2 | Section 1.3 | Section 1.4 | Section 1.5

Chapter 1 | DNT Table of Contents

Copyright © 2001 by W. H. Freeman and Company