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.
Now we're getting somewhere. We know that a = bq + r. Dividing on both sides of the equation by b yields
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:
Here's the computation:
Since r < b, we have fulfilled the requirements of the Division Algorithm, and we're done. Let's summarize the procedure:
- Begin with values of a and b;
- Set q equal to the integer part of a/b;
- Set r = a – bq.
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.
Exercise 3Use the Division Algorithm applet to repeat Exercise 5 in the Prelab section of this chapter. |