8.13. References 289
To see how to update the coefficients when at least one ofaandbis odd and
uaCvbis even, show that eitheruandvare both even, or elseu bandvCa
are both even.
Exam Problems
Problem 8.18.
Prove that gcd.mbCr;b/Dgcd.b;r/for all integersm;b;r.
Hint:We proved a similar result in class whenrwas a remainder inŒ0::b/.
Problem 8.19.
Prove by induction that the gcd of a nonempty finite set of integers is an integer
linear combination of the numbers in the set. You may assume that the gcd of two
integers is an integer linear combination of them, which was proved Theorem 8.2.2.
You may also assume the easily verified fact that
gcd.A[B/Dgcd.gcd.A/;gcd.B//; (8.28)for any finite, nonempty setsA;Bof integers.
Be sure to clearly state and label your Induction Hypothesis, Base case(s), and
Induction step.
Problem 8.20.
The Stata Center’s delicate balance depends on two buckets of water hidden in a
secret room. The big bucket has a volume of 25 gallons, and the little bucket has a
volume of 10 gallons. If at any time a bucket contains exactly 13 gallons, the Stata
Center will collapse. There is an interactive display where tourists can remotely
fill and empty the buckets according to certain rules. We represent the buckets as a
state machine.
The state of the machine is a pair.b;l/, wherebis the volume of water in big
bucket, andlis the volume of water in little bucket.
(a)We informally describe some of the legal operations tourists can perform be-
low. Represent each of the following operations as a transition of the state machine.
The first is done for you as an example.
- Fill the big bucket.
.b;l/ !.25;l/: - Empty the little bucket.