## 2.1   The Division Algorithm Revisited

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

Theorem (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.

Recall that at the end of the last chapter, you computed q and r for a given a and b. Here's the computation for a = 123456789 and b = 369:

Your browser does not support java.

Thus, for this choice of a and b, we have q = 334571 and r = 90. In Exercise 2 of the Prelab section, you were asked to compute gcd(a, b) and gcd(b, r) for different choices of a and b. If we perform this computation for the values of a and b given above, we get

Your browser does not support java.

#### Research Question 1

Compute the values of gcd(a, b) and gcd(b, r) as above for different pairs a and b of 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