201609 Math 122 Assignment 4 Due: Monday, November 14 or Tuesday, November 15, in class, before the lecture starts There are five questions (40 marks), and one bonus question (4 marks), on the two pages. Please feel free to discuss these problems with each other. In the end, each person must write up their own solution, in their own words, in a way that reflects their own understanding. Complete solutions are those which are coherently written, and include appropriate justifications. 1. Let f and g be the functions from {a, b, c, d, e, f } to {a, b, c, d, e, f } given in the following table: x= a b c d e f f (x) = c d a e f b g(x) = b c a e f d (a) Find f g and g f . (b) If the function g maps a set to itself, then g 2 is defined to be g g. For the function g above, show that g 1 = g 2 . (c) Find f 2 and f 4 = (f 2 )2 . What does this tell you about f 1 ? 2. Let f : A B and g : B C be functions. Prove: (a) If g f is one-to-one and f is onto, then g is one-to-one. (b) If g f is onto and g is one-to-one, then f is onto. (c) Let A = {1, 2} and B = {a, b, c}. Let the functions f and g be f = {(1, a), (2, b)} and g = {(a, 1), (b, 2), (c, 1)}. Verify that g f = A , and then explain why g is not the inverse of f . 3. Recall that an integer n is even if there is an integer k such that n = 2k. Notice that this depends only on the integer n, and not the base in which n is represented. (a) Suppose b N is even. Let n = (dk dk1 . . . d1 d0 )b . Show that if n is even, then d0 is even. Is the converse true? (b) Suppose n = (dk dk1 . . . d1 d0 )3 is even. Show that an even number of dk , dk1 , . . . , d0 are odd. Is the converse true? (c) Is the statement in (b) still true if 3 is replaced by any odd number b > 1? 4. (a) Let d = gcd (a, b). Show that gcd (a/d, b/d) = 1. (b) Prove that if a|b, then (b/a)|b. (c) Prove that if a|b and (b/a)|c, then b|ac. (d) Suppose gcd (a, b) = a. Prove that a|b. 5. (a) Show that a natural number n is a perfect square (that is, equals k 2 for some k N) if and only if every exponent in its prime decomposition is even. (b) Explain why the Fundamental Theorem of Arithmetic implies that there are no natural numbers a and b such that 2a2 = b2 . 6. (Bonus problem, 4 bonus marks) Let n be a positive integer. Consider the n + 1 numbers 1, 11, 111, 1111, . . . , 11 1, where the last of these has n + 1 digits. Explain why some two of these numbers must have the same remainder when divided by n, and then use this information to show that some multiple of n has 0 and 1 as its only digits. Is it true that for any number d, with 0 d 9, there is a multiple of n with 0 and d as its only digits? Page 2