Chapter 8 Number Theory290
- Pour the big bucket into the little bucket. You should have two cases defined
in terms of the state.b;l/: if all the water from the big bucket fits in the little
bucket, then pour all the water. If it doesn’t, pour until the little jar is full,
leaving some water remaining in the big jar.
(b)Use the Invariant Principle to show that, starting with empty buckets, the Stata
Center will never collapse. That is, the state.13;x/in unreachable. (In verifying
your claim that the invariant is preserved, you may restrict to the representative
transitions of part (a).)
Problem 8.21.
Let
mD 2952474117 ;
nD 2372211211197 ;
pD 2534760421930 :
(a)What is the gcd.m;n;p/?
(b)What is theleast common multiple, lcm.m;n;p/?
Letk.n/be the largest power ofkthat dividesn, wherek > 1. That is,
k.n/WWDmaxfijkidividesng:
IfAis a nonempty set of nonnegative integers, define
k.A/WWDfk.a/ja 2 Ag:
(c)Expressk.gcd.A//in terms ofk.A/.
(d)Letpbe a prime number. Expressp.lcm.A//in terms ofp.A/.
(e)Give an example of integersa;bwhere 6 .lcm.a;b// >max. 6 .a/; 6 .b//.
(f)Let
Q
Abe the product of all the elements inA. Expressp.n/.
Q
A/in terms
ofp.A/.
(g)LetBalso be a nonempty set of nonnegative integers. Conclude that
gcd.A[B/Dgcd.gcd.A/;gcd.B//: (8.29)
Hint:Considerp./of the left and right hand sides of (8.29). You may assume
min.A[B/Dmin.min.A/;min.B//: (8.30)