Below is a statement of the Division Algorithm, as given in the Prelab section of this chapter:

Theorem (Division Algorithm)Letabe an integer andbbe a positive integer. Then there exist unique integersqandrsuch that

a=bq+rand 0r<b.Recall that at the end of the last chapter, you computed

qandrfor a givenaandb. Here's the computation fora= 123456789 andb= 369:

Thus, for this choice of

aandb, we haveq= 334571 andr= 90. In Exercise 2 of the Prelab section, you were asked to compute gcd(a,b) and gcd(b,r) for different choices ofaandb. If we perform this computation for the values ofaandbgiven above, we get

## Research Question 1

Compute the values of gcd(

a,b) and gcd(b,r) as above for different pairsaandbof your choosing until you have enough data to form a conjecture concerning the relationship between gcd(a,b) and gcd(b,r). As always, once you have formed your conjecture, try to prove it!

Section 2.1 | Section 2.2 | Section 2.3 | Section 2.4 | Section 2.5

Copyright © 2001 by W. H. Freeman and Company