Homework 2 Solutions Enrique Trevi˜ no September 23, 2014 1 Chapter 3 Problem 1. (Exercise 2) Which of the following multiplication tables defined on the set G = {a, b, c, d} form a group? Support your answer in each case. (a) ◦ a a a b b c c d d b c b d a ◦ a a a b b c c d d b c d b c d a d c d a b c b a ◦ a a a b b c c d d b b c d a ◦ a b c d b c d b c d a c d b a d d b c c d c a b d a d b c (b) (c) c c d a b d d a b c (d) a a b c d Solution 1. (a) It’s not a group since it doesn’t have an identity. The easy way to see that it does not have an identity is that no row of the Cayley table matches the top row. (b) The identity is a. All elements have inverses (the inverse of a is a, the inverse of b is b, the inverse of c is c and the inverse of d is d). The operation is closed by definition. The only thing left to check is associativity. When checking associativity, we have to check that for any x, y, z ∈ {a, b, c, d}, that x(yz) = (xy)z. There are 43 = 64 ways of picking x, y, z, but we can ignore whenever one of them is the identity, since the triple product collapses to a double product. Therefore there are 33 = 27 ways. 1 To simplify our work, we’re going to the following. We’ll create the table of all possible x(by) (labeled ?) and then a table of all (xb)y labeled (◦). ? b b b c c d d c d c d b a a b ◦ b b b c c d d c d c d b a a b Since the tables of ? and ◦ match, the operation is associative with respect to b. Now let ? be the table x(cy) and ◦ be the table of (xc)y. ? b c d b c b a c b c d d a d c ◦ b b c c b d a c d b a c d d c Since the tables of ? and ◦ match, the operation is associative with respect to c. Now let ? be the table x(dy) and ◦ be the table of (xd)y. ? b c d b d a b c a d c d b c d ◦ b c d b d a b c a d c d b c d Since the tables of ? and ◦ match, the operation is associative with respect to d. So we’ve verified that associativity works by checking all possibilities of writing x(yz) and (xy)z and verifying they are the same. Therefore it is a group! (c) The identity is a. All elements have inverses (the inverse of a is a, the inverse of b is b, the inverse of c is c and the inverse of d is d). The operation is closed by definition. The only thing left to check is associativity. When checking associativity, we have to check that for any x, y, z ∈ {a, b, c, d}, that x(yz) = (xy)z. There are 43 = 64 ways of picking x, y, z, but we can ignore whenever one of them is the identity, since the triple product collapses to a double product. Therefore there are 33 = 27 ways. To simplify our work, we’re going to the following. We’ll create the table of all possible x(by) (labeled ?) and then a table of all (xb)y labeled (◦). ? b c d b d a b c a b c d b c d ◦ b c d b d a b c a b c d b c d 2 Since the tables of ? and ◦ match, the operation is associative with respect to b. Now let ? be the table x(cy) and ◦ be the table of (xc)y. ? b c d b a b c c b c d d c d a ◦ b b a c b d c c b c d d c d a Since the tables of ? and ◦ match, the operation is associative with respect to c. Now let ? be the table x(dy) and ◦ be the table of (xd)y. ? b c d b b c d c c d a d d a b ◦ b b b c c d d c c d a d d a b Since the tables of ? and ◦ match, the operation is associative with respect to d. So we’ve verified that associativity works by checking all possibilities of writing x(yz) and (xy)z and verifying they are the same. Therefore it is a group! (d) The identity is a. However, d does not have an inverse, so it is not a group. Problem 2. (Exercise 5) Describe the symmetries of a square and prove that the set of symmetries is a group. Give a Cayley table for the symmetries. How many ways can the vertices of a square be permuted? Is each permutation necessarily a symmetry of the square? The symmetry group of the square is denoted by D4 . Solution 2. There are eight symmetries: 1. The identity which we will call id. 2. Reflecting with respect to a vertical line, µ1 . 3. Reflecting with respect to a horizontal line, µ2 . 4. Reflecting with respect to the diagonal BD, µ3 . 5. Reflecting with respect to the diagonal AC, µ4 . 6. Rotating 90 degrees counter-clockwise: ρ1 . 7. Rotating 180 degrees counter-clockwise: ρ2 . 8. Rotating 270 degrees counter-clockwise: ρ3 . 3 The result of composing one symmetry with another can be seen in the following table: ◦ id µ1 µ2 µ3 µ4 ρ1 ρ2 ρ3 id id µ1 µ2 µ3 µ4 ρ1 ρ2 ρ3 µ1 µ1 id ρ2 ρ3 ρ1 µ4 µ2 µ3 µ2 µ2 ρ2 id ρ1 ρ3 µ3 µ1 µ4 µ3 µ3 ρ1 ρ3 id ρ2 µ1 µ4 µ2 µ4 µ4 ρ3 ρ1 ρ2 id µ2 µ3 µ1 ρ1 ρ1 µ3 µ4 µ2 µ1 ρ2 ρ3 id ρ2 ρ2 µ2 µ1 µ4 µ3 ρ3 id ρ1 ρ3 ρ3 µ3 µ3 µ1 µ2 id ρ1 ρ2 Not all permutations of ABCD result in a symmetry. For example the permutation BACD, i.e., changing A for B and keeping C and D fixed is not a symmetry since the angle ∠CAB changes from 90◦ to 45◦ with that permutation. Problem 3. (Exercise 7) Let S = R \ {−1} and define a binary operation on S by a ∗ b = a + b + ab. Prove that (S, ∗) is an abelian group. Solution 3. First let’s show that ∗ is closed, i.e., that if a, b ∈ S, then a ∗ b ∈ S. Since S is every real except −1 then we want to show that if a 6= −1 and b 6= −1, then a ∗ b 6= −1. For the sake of contradiction, suppose a ∗ b = −1. Then a + b + ab = −1 a(b + 1) + b = −1 a(b + 1) = −(b + 1). Since b 6= −1, then we can divide both sides by b + 1. But then we have that a = −1, which contradicts that a 6= −1. Therefore a ∗ b 6= −1, so a ∗ b ∈ S, so ∗ is a binary operation on S. Now let’s show that ∗ is associative. Suppose a, b, c ∈ S. (a ∗ b) ∗ c = (ab + a + b) ∗ c = (ab + a + b)(c) + (ab + a + b) + c = abc + ac + bc + ab + a + b + c = a(bc + c + b) + a + (bc + b + c) = a(b ∗ c) + a + (b ∗ c) = a ∗ (b ∗ c). Therefore ∗ is associative. Let’s show that 0 is the identity for S. Let a ∈ S. Then a ∗ 0 = a + 0 + 0 = a and 0 ∗ a = 0 + 0 + a = a. Therefore 0 ∗ a = a ∗ 0 = a, so 0 is the identity of S. To finish our proof that S is a group, we need to show every element has an inverse. Let a ∈ S. We want to find an inverse for a, so we want to find a b 6= −1 such that a ∗ b = 0. a∗b=0 ab + a + b = 0 b(a + 1) = −a b=− Since a 6= −1, b exists and a ∗ b = 0, so b = − a . a+1 a 1 is the inverse of a. Note that b = −1 + 6= −1, so a+1 a+1 b ∈ S. We’ve shown that S is a group together with the operation ∗. To show that it is an abelian group we must prove that ∗ is commutative. Let a, b ∈ S. Then a ∗ b = ab + a + b = ba + b + a = b ∗ a, therefore it is an abelian group. 4 Problem 4. (Exercise 14) Given the groups R∗ and Z, let G = R∗ × Z. Define a binary operation ◦ on G by (a, m) ◦ (b, n) = (ab, m + n). Show that G is a group under this operation. Solution 4. To show that G is a group we must show that the binary operation is closed, that the operation is associative, that there is an identity element in G and that every element of G has an inverse. Let’s prove this one by one: 1. Suppose that (a, m) ∈ G and (b, n) ∈ G. Since a and b are nonzero reals, then ab is a nonzero real, so ab ∈ R∗ . Since m and n are integers, then m + n ∈ Z. Therefore (ab, m + n) ∈ R∗ × Z = G. 2. Suppose (a, m), (b, n), (c, r) ∈ R∗ × Z. Then (a, m) ◦ ((b, n) ◦ (c, r)) = (a, m) ◦ (bc, n + r) = (abc, m + n + r), and ((a, m) ◦ (b, n)) ◦ (c, r) = (ab, m + n) ◦ (c, r) = (abc, m + n + r). Therefore the operation is associative. 3. The identity of G is (1, 0). Indeed if (a, m) ∈ G, then (a, m) ◦ (1, 0) = (a, m) = (1, 0) ◦ (a, m). 4. Suppose that (a, m) ∈ G, then the inverse of (a, m) is 1 , −m ∈ G, a since (a, m) ◦ 1 1 , −m = (1, 0) = , −m ◦ (a, m). a a Therefore G is a group. Problem 5. (Exercise 16) Give a specific example of some group G and elements g, h ∈ G where (gh)n 6= g n hn . Solution 5. Consider the group D4 (from Exercise 5). Let g = µ1 and h = µ3 and let n = 2. Then (gh)2 = (µ1 ◦ µ3 )2 = (ρ1 )2 = ρ2 , while g 2 h2 = (µ21 ) ◦ (µ23 ) = id ◦ id = id. Since ρ2 6= id, then (gh)2 6= g n hn . Problem 6. (Exercise 17) Give an example of three different groups with eight elements. Why are the groups different? Solution 6. The groups Z8 , Z4 × Z2 , and Z2 × Z2 × Z2 have 8 elements. Let’s show they are all different. To show their difference we’ll look at the subgroups they have. Z8 has only one subgroup with 2 elements, namely {0, 4}, while Z4 × Z2 has 3 subgroups with 2 elements: {(0, 0), (2, 0)}, {(0, 0), (0, 1)}, and {(0, 0), (2, 1)}. On the other hand, Z2 × Z2 × Z2 has 7 subgroups with 2 elements: {(0, 0, 0), (1, 0, 0)}, {(0, 0, 0), (1, 0, 1)}, {(0, 0, 0), (1, 1, 0)}, {(0, 0, 0), (1, 1, 1)}, {(0, 0, 0), (0, 1, 0)}, {(0, 0, 0), (0, 1, 1)}, {(0, 0, 0), (0, 0, 1)}. Since all three groups have a different set of subgroups of order 2, they can’t be the same group. Problem 7. (Exercise 24) Let a and b be elements in a group G. Prove that abn a−1 = (aba−1 )n for n ∈ Z. 5 Solution 7. For n = 0, ab0 a−1 = aa−1 = e and (aba−1 )0 = e too, so they match. Let’s prove it by induction for n ∈ N. If n = 1, then clearly ab1 a−1 = (aba−1 )1 . Suppose that for some k ≥ 1, then abk a−1 = (aba−1 )k . Let’s prove that abk+1 a−1 = (aba−1 )k+1 . Since (aba−1 )k = abk a−1 , then (aba−1 )k+1 = (aba−1 )k (aba−1 ) = abk a−1 (aba−1 ) = abk (a−1 a)ba−1 = abk ba−1 = abk+1 a−1 . Therefore the statement is true for all n ∈ N. We’re left with trying to prove the statement for n < 0. Suppose n = −m where m ∈ N. We want to show ab−m a−1 = (aba−1 )−m . Now, (aba−1 )−1 = (ab−1 a−1 ), so (aba−1 )−m = (ab−1 a−1 )m . But since m ∈ N, then (ab−1 a−1 )m = ab−m a−1 . Therefore (aba−1 )−m = ab−m a−1 . So the statement is true for negative numbers as well. Now we’ve shown it for all n ∈ Z. Problem 8. (Exercise 25) Let U (n) be the group of units in Zn . If n > 2, prove that there is an element k ∈ U (n) such that k 2 = 1 and k 6= 1. Solution 8. gcd (n, n − 1) = 1, therefore n − 1 ∈ U (n). (n − 1)2 ≡ (−1)2 ≡ 1 mod n. Since n > 2, then n − 1 > 1, so n − 1 6= 1. Therefore k = n − 1 satisfies the conditions in the problem. Problem 9. (Exercise 30) Show that if a2 = e for all elements a in a group G, then G must be abelian. Solution 9. Let a, b ∈ G. We want to prove ab = ba. Since the square of any element is e, then (aba)2 = e, but (aba)2 = (aba)(aba) = (ab)(aa)(ba) = (ab)(ba). So (ab)(ba) = e and (ab)(ab) = e, therefore by Proposition 3.7 (left-cancelation law), ab = ba. Problem 10. (Exercise 33) Find all the subgroups of Z3 × Z3 . Use this information to show that Z3 × Z3 is not the same group as Z9 . Solution 10. The subgroups of Z3 × Z3 are (a) {(0, 0)}, (b) {(0, 0), (1, 0), (2, 0)}, (c) {(0, 0), (0, 1), (0, 2)}, (d) {(0, 0), (1, 1), (2, 2)}, (e) {(0, 0), (1, 2), (2, 1)}, (f) Z3 × Z3 . Meanwhile, the subgroups of Z9 are: (a) {0}, (b) {0, 3, 6}, (c) Z9 . Since there are a different number of subgroups in each group Z3 × Z3 6= Z9 . 6 Problem 11. (Exercise 34) Find all the subgroups of the symmetry group of an equilateral triangle. Solution 11. Define id, ρ1 , ρ2 , µ1 , µ2 , and µ3 as the 6 symmetries of an equilateral triangle. id is the identity symmetry, ρ1 is rotating 120◦ , ρ2 is rotating 240◦ and µ1 , µ2 , µ3 are the three possible reflections. Then the subgroups are: • {id}, • {id, µ1 }, • {id, µ2 }, • {id, µ3 }, • {id, ρ1 , ρ2 }, • {id, µ1 , µ2 , µ3 , ρ1 , ρ2 }. It is not hard to see that there are no other subgroups. Indeed any subgroup must have id. If you have ρ1 , then you must have ρ2 and viceversa since ρ1 ◦ ρ1 = ρ2 and ρ2 ◦ ρ2 = ρ1 . If you have µi and ρj in the subgroup, then you must have the whole group because ρ1 µi 6= ρ2 µi , ρ1 µi 6= µi , ρ2 µi 6= µi and neither of them is the identity. So you have at least 6 distinct elements: µi , ρ1 µi , ρ2 µi , id, µi , ρ1 , ρ2 . But the whole group of symmetries consists of 6 elements. That means the only subgroups are the subgroups listed. Problem 12. (Exercise 36) Let H = {2k : k ∈ Z}. Show that H is a subgroup of Q∗ . Solution 12. Let’s prove it the old-fashioned way by showing that H ⊆ Q∗ , that 1 ∈ H, that H is closed under multiplication and that every element of H has an inverse in H. 1 Let h ∈ H, then h = 2k for some integer k. If k ≥ 0, then h ∈ N, so h ∈ Q∗ . If k < 0, then h = 2−k , so ∗ ∗ ∗ it is a ratio of two integers, so h ∈ Q . Therefore h ∈ Q , so H ⊆ Q . Since 20 = 1, we have 1 ∈ H. Now suppose that h1 ∈ H and h2 ∈ H, then h1 = 2k1 and h2 = 2k2 for some integers k1 and k2 . Then h1 h2 = 2k1 +k2 . Since k1 + k2 ∈ Z, then h1 h2 ∈ H, so H is closed. Finally, suppose h ∈ H. Then there exists an integer k such that h = 2k . Now, 2−k ∈ H and 2k · 2−k = 0 2 = 1 = 2−k · 2k , so 2−k is the inverse of h and it is in H. Alternative Solutions: For the sake of illustrating the different ways of showing subset-ness, we’ll prove it by using Proposition 3.10 this time. We prove that H ⊆ Q∗ the same way as above. We prove H is nonempty by picking any integer k and saying 2k ∈ H. Finally, we need to show that g ∈ H and h ∈ H, then gh−1 ∈ H. Suppose g, h ∈ H. Then there exist integers k and ` such that 2k = g and 2` = h. Now, gh−1 = g 2k = ` = 2k−` ∈ H. h 2 Therefore gh−1 ∈ H, so H is a subgroup of Q∗ . Problem 13. (Exercise 37) Let n = 0, 1, 2, . . . and nZ = {nk : k ∈ Z}. Prove that nZ is a subgroup of Z. Show that these subgroups are the only subgroups of Z. Solution 13. First let’s show nZ is a subgroup for any n ∈ N ∪ {0}: (a) First let’s show addition is closed on nZ. If a, b ∈ nZ, then there exist k1 , k2 ∈ Z such that a = k1 n and b = k2 n. Then a + b = k1 n + k2 n = (k1 + k2 )n ∈ nZ. (b) The identity of Z, 0, is an element of nZ, since 0 = n × 0, so 0 ∈ nZ. (c) Finally, let’s show that any element of nZ has an inverse. Indeed if a ∈ nZ, then a = k1 n for some integer k1 . Then −a = −k1 n = (−k1 )n ∈ nZ. Therefore the inverse of a is also an element of nZ. 7 By (a), (b) and (c), nZ is a subgroup of Z with the addition operation. Now, we want to show that all subgroups of Z are of the form nZ with n ∈ N ∪ {0}. Suppose H ⊆ Z is a subgroup. If H = {0}, then H = 0Z. Suppose H 6=}0}. By the Well-Ordering principle, there exists a nonzero element n ∈ H such that |n| is minimal. Since H is a subgroup of Z, then the inverse of n is also in H, i.e., −n ∈ H. Since n and −n, then we can assume without loss of generality that n is positive. Since H is a subgroup, then all multiples of n must be in H. This means that nZ ⊆ H. Now suppose that there is an element m ∈ H such that m 6∈ nZ. By the division algorithm, there exist integers q and r such that: m = qn + r, where 0 ≤ r < n. Since m 6∈ nZ, then r 6= 0. Since m ∈ H and qn ∈ H, then −qn ∈ H, so m − qn ∈ H. Therefore r ∈ H. But 0 < r < n which implies that |r| < |N |, which contradicts the minimality of |n|. This means no element m exists. That proves that H = nZ. Problem 14. (Exercise 40) Prove that √ G = {a + b 2 : a, b ∈ Q and a and b are not both zero} is a subgroup of R∗ under the group operation of multiplication. Solution 14. Since every element of G is a real number, then to show G ⊆√R∗ , we need only show that √ b 2 = −a. 0 6∈ G. Suppose 0 ∈ G. Then there exist a, b ∈ Q not both 0 such that a + b 2 = 0. Therefore √ If b = 0, then a = 0. But a and b can’t both be zero. Therefore b = 6 0. Since b = 6 0, then 2 = −a/b ∈ Q, √ but 2 is not rational. This√contradicts the assumption that 0 ∈ G. Therefore 0 6∈ G and hence G ⊆ R∗ . 1 ∈ G because 1 = 1 + 0 2. So the identity is in G. Suppose g, h ∈ G. Let’s show that gh ∈ G and that g −1 ∈ G. This would prove that √ G is a subgroup of R∗ . √ Since g ∈ G, then g = a + b 2 for some rationals a, b (not both 0). Similarly, h = c + d 2 for some rationals c and d (not both 0). Now, √ √ √ √ √ gh = (a + b 2)(c + d 2) = ac + ad 2 + bc 2 + 2bd = (ac + 2bd) + (ad + bc) 2. Since ac + 2bd ∈ Q and ad + bc ∈ Q, then gh ∈ G (unless ac + 2bd = 0 and ad + bc = 0). To make sure gh ∈ G, we must make sure that ac + 2bd and ad + bc are not both zero at the same time if a, b, c, d satisfy the conditions above. For the sake of contradiction, suppose that ac + 2bd = 0 and ad + bc = 0. If d = 0, then ac = 0 and bc = 0. Since c 6= 0, then a = 0 and b = 0, contradicting that a and b can’t both be zero. Therefore d 6= 0. Since ad + bc = 0, then a = −bc/d. Since ac + 2bd = 0, then ac + 2bd = 0 −bc c + 2bd = 0 d −bc2 + 2bd2 = 0 2bd2 = bc2 . If b = 0, then a = −bc/d = 0, so both a and b √ are zero, contradicting√the assumptions. Therefore b 6= 0. Since b 6= 0, then 2d2 = c2 . But that means that 2 = |c/d| ∈ Q. Since 2 is not rational, this is impossible. Therefore ad + bc and ac + 2bd can’t both be 0, so gh ∈ G. √ To√finish off, we need to show that g −1 ∈ G. Since a and b are not both zero, then a − b 2 6= 0 (since a − b 2 ∈ G ⊆ R∗ ). √ √ √ √ 1 a−b 2 a−b 2 a b −1 √ √ √ g = = = 2 = − 2 = r + t 2. a − 2b2 a2 − 2b2 a2 − 2b2 a+b 2 (a + b 2)(a − b 2) r and t are rational. Furthermore, they can’t both be 0, because otherwise a = b = 0 (which contradicts the assumption). Therefore g −1 ∈ G. This completes the proof that G is a subgroup of R∗ . 8