201609 Math 122 Assignment 4 Solution Ideas 1. (a) (b) x= a b c d f g(x) = d a c f g f (x) = a e b f x= a b g (x) = c a g g 2 (x) = a b g 2 g(x) = a b Since g g 2 = g 2 g 2 (c) x= a f 2 (x) = a f 4 (x) = a Since f 2 6= , b e b f 1 c d b f c d c d = , g 2 c d e c f b c d e 6 f . But = e f b e d c e f d e e f e f = g 1 . f d f f f 3 = f 3 f = f 4 = , so f 1 = f 3 . 2. (a) Let f : A B and g : B C be functions such that g f is one-to-one and f is onto. Suppose that g(b1 ) = g(b2 ), for some b1 , b2 B. Since f is onto, there exist a1 , a2 A such that f (a1 ) = b1 and f (a2 ) = b2 . Then g f (a1 ) = g(f (a1 )) = g(b1 ) = g(b2 ) = g(f (a2 )) = g f (a2 ). Since gf is ont-to-one, this means a1 = a2 , and, in turn, b1 = f (a1 ) = f (a2 ) = b2 , so g is one-to-one. (b) Let f : A B and g : B C be functions such that g f is onto and g is one-to-one. Let b be an arbitrary element of B and let c = g(b). Since g f is onto, there exists an element a of A such that g f (a) = c. Then g(f (a)) = g(b). Since g is one-to-one, we have f (a) = b. Therefore f is onto. (c) g f = {(1, 1), (2, 2)} = A , but f g = {(a, a), (b, b)} = 6 B (since (c, c) 6 f g). Therefore g is not the inverse of f . 3. (a) We have n = (dk dk1 . . . d1 d0 )3 = dk 3k + dk1 3k1 + d1 31 + d0 30 . Since every power of 3 is odd, a summand di 3i is odd if and only if di is odd. Since the value of the sum is even, the number of odd summands must be even. Hence the base-3 representation of n has an even number of odd digits. The converse is true. The argument is very close to what's above. (b) Let b > 1 be an odd integer. Then, the integer n is even if and only if the base-b representation of n contains an even number of odd digits. 4. (a) Suppose gcd(a/d, b/d) = c. Then c 1, and c|a/d and c|b/d. It follows that cd|a and cd|b. But d is the greatest common divisor of a and b, so cd d. Therefore c 1, and consequently c = 1. (b) Since a|b, we have that b/a is an integer. Since (b/a)a = b, we have that (b/a)|b. (c) Since a|b then there exists k Z so that ak = b. Since (b/a)|c then there exists ` Z so that (b/a)` = c. Therefore bc = b(b/a)` = b(ak/a)` = b(k`). Since k` Z, it follows that b|ac. (d) If gcd(a, b) = a, then, by definition of gcd, a|a (of course) and a|b. 5. (a) Suppose n = k 2 and let k have prime-power decomposition k = pe11 pe22 pekk . Then n has prime-power decomposition n = k 2 = (pe11 pe22 pekk )2 = (pe11 )2 (pe22 )2 (pekk )2 2ek 1 2e2 = p2e 1 p2 pk . Thus every exponent in the prime decomposition of n is even. Conversely, suppose n = pe11 pe22 pekk , where each ei is even. Then for each i we may write ei = 2fi , where fi is an integer. Thus 2fk 1 2f2 n = p2f 1 p2 pk \u0010 \u00112 \u0010 \u00112 \u0010 \u00112 = pf11 pf22 pfkk \u0010 \u00112 = pf11 pf22 pfkk . Thus, n is a perfect square. (b) By part (a) the exponent of 2 in the prime factorization of the LHS would be odd, and the exponent of 2 in the prime factorization of the RHS would be even. The FTA says that a number has only one prime factorization, so the numbers represented by the LHS and RHS can not be equal. Page 2 201609 Math 122 Assignment 5 Due: Monday, November 28 or Tuesday, November 29 in class, before the lecture starts There are five questions (40 marks), and one bonus question (4 marks). 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. (a) Let n = (dk dk1 . . . d1 d0 )10 . Show that 11 | n 11 | d0 d1 + d2 + (1)k dk . (Hint: 10 (1) (mod 11)). (b) Let b > 1 be an integer, and n = (dk dk1 . . . d1 d0 )b . Show that (b 1) | n (b 1) | d0 + d1 + d2 + + dk . (Hint: this is a known result when b = 10. We're showing that it works in any positive base.) 2. (a) Let a Z and k N. Prove that one of the numbers a, a + 1, . . . , a + (k 1) is divisible by k. (b) Let n Z and m N. The least residue of n modulo m is the unique integer among 0, 1, . . . , m 1 to which n is congruent modulo m. For k Z, which numbers can be the least residue of k 2 modulo 4? (c) Prove that no integer which is congruent to 3 modulo 4 can be written as a sum of two squares. That is, if n 3 (mod 4), then there are no integers x and y such that n = x2 + y 2 . (Hint: the contrapositive.) 3. (a) Find the smallest natural number that is divisible by 2 and by 3, and which is simultaneously the fourth power of an integer, and the sixth power of an integer. (b) Suppose that a and b are integers such that ab = 27 38 52 76 and gcd(a, b) = 23 34 5. Is it possible that a = 25 34 5? Why or why not? (c) What is lcm(a, b)? 4. Prove by induction that if n 1 distinct dice are rolled, then the number of outcomes where the sum of the numbers on faces that turn up is an even integer equals the number of outcomes where the sum of the numbers on the faces that turn up is an odd integer. 5. Guess and prove a formula for 1 2 + 3 4 + + (1)n1 n (i.e., one that works for any n 1). 6. (Bonus question: 4 bonus marks) Alice and Bob play the following game. Initially, there is a pile of 20 pebbles. Each player, on their turn, removes either one or two pebbles from the pile. The player who takes the last pebble wins. Suppose that Alice is the first player to take pebbles from the pile. Does she have a strategy that will guarantee she wins the game no matter what Bob does? Explain