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)Letabe an integer andbbe a positive integer. Then there exist unique integersqandrsuch thata=bq+rand 0r<b.Remember learning long division in grade school? (If not, pretend that you do.) Long division is a procedure for dividing a number

aby another numberb, and coming up with a quotientqand a remainderr. 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

aandb, and would like to find the correspondingqandr.Ifaandbare small, then you could findqandrby trial and error. However, suppose thata= 124389001 andb= 593. In this case, trial and error would be extremely tedious. What happens if we try the division using our on-line calculator? Sinceqis the quotient, it should be close toa/b.Now we're getting somewhere. We know that

a=bq+r. Dividing on both sides of the equation bybyieldsa/b=q+r/b.Thus it follows that

qa/b. (Remember that 0r<b.) So, in our above example, it makes sense to takeq= 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" ofa/b, which is the required value forq:With this choice of q, what isr? That's easy enough, because we must havea–bq=r.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
aandb;- Set
qequal to the integer part ofa/b;- Set
r=a–bq.The applet below automates this procedure. Enter values for

aandb, and it will return the corresponding values of the quotientqand the remainderr. Try it out.

## 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

Copyright © 2001 by W. H. Freeman and Company