CMSC 222 Spring 2021 Assignment 7 The due date for this assignment is 11 PM on Sunday, March 28. Problem 1 Run the Euclidean god algorithm to compute the GCD of 222 and 2021. Show all your work. Solution: Problem 2 Answer the following questions related to "Big-O" computational complexity. For each, you must use the definition of "Big-O". Show all your work. (a) Show that (n + 1) is 0(n). (b) Show that for nonnegative functions f and g, max{f(n), g(n)} is Of(n) + g(n)). (c) Show that if nonnegative functions d, e, f, and g are such that d(n) is 0(f(n)) and e(n) is (g(n)), then the product d(n)e(n) is 0(f(n)g(n)). Solution: Problem 3 Compute, by hand, the value of the following expressions. Give the smallest positive value for each answer. Show all your work, but try to do as little work as possible. (a) 344 mod 5 (b) (-314 + 3230) mod 5 (c) 58" mod 7 (a) (16)1271 mod 17 (e) 654321 mod 77 (hint: one way, use the Chinese Remainder Theorem) Solution: Problem 4 Prove that 52017 + 22017 isn't prime by finding a prime factor. Solution: Problem 5 Suppose that for positive integers a and b, we have god(a, b) = d. What is ged(a/d,b/d)? Give a formal proof of this fact. The fact is that god(a/d, b/d) = 1. Solution: Problem 6 For positive integer n, find a simple formula for 2-1 * = 1 +*+*+ prove it. + , and Solution