Mathematics for Computer Science

Chapter 8 Number Theory290

3. 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)