CS 70 SPRING 2008 — DISCUSSION #5LUQMAN HODGKINSON, AARON KLEINMAN, MIN XU1. More BucketsExercise 1. Upon hearing that our CS70 class has found a way to consistently defuse their bombs, theterrorists in Die Hard decided to make their puzzles harder to crack by adding more buckets. So now, youhave a 6-gallon bucket, a 10-gallon bucket, and a 15-gallon bucket and the villains order you to get precisely13 gallons of water in one bucket. But before we tackle this problem, let’s do some number theory:(1) Show that given (6, 10, 15), the gcd of any pair of numbers is greater than 1. Now, find the greatestcommon divisor of all three numbers, what is it?(2) Describe mathematically all possible values of the expression 6x + 10y where x, y are integers.(3) Now, describe mathematically all possible values of the expression 6x + 10y + 15z.(4) Use the idea of the two buckets algorithm developed in class to devise a new one to get 13 gallonsof water from the 3 buckets (it doens’t have to be efficient!)(5) Describe informally how you might generalize this algorithm to solve problems involving any numberof buckets?Answer:2. PotpourriExercise 2. Modding is in general an O(n2) operation, but in some cases it can be faster. Prove that if a, bare positive integers, then 2a− 1 mod 2b− 1 = 2(a mod b)− 1. Suppose that x = 2a− 1, y = 2b− 1, what isthe running time of x mod y if max(x, y) is an n-bit number.Exercise 3. Now use the previous exercise and Euclid’s algorithm to prove that gcd(2a− 1, 2b− 1) =2gcd(a,b)− 1.Answer:Date: February 26, 2008.The authors gratefully acknowledge the TA’s of CS70 Past for the use of their previous notes: Chris Crutchfield, AlexFabrikant, David Garmire, Assane Gueye, Amir Kamil, Lorenzo Orecchia, Vahab Pournaghshband, Ben Rubinstein. Theirnotes form the basis for this handout.13. Multiplicative InversesExercise 4. Find the multiplicative inverse of 10 modulo 743.Exercise 5. (1) What is 4! mod 5 ?(2) What is 6! mod 7 ?(3) What is 10! mod 11 ?(4) Can you make a conjecture about the value of (p − 1)! mod p when p is prime? Prove it.Answer:4. A ChallengeExercise 6. Prove or find counterexample: if gcd(m, n) = 1, then gcd(m + n, mn) =
View Full Document
Unlocking...