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:
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
Research Question 1Compute 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! |