M417 Homework 8 Solutions Spring 2004
1. The 3rd Isomorphism Theorem (AKA the Freshman's Delight): Consider groups A < B < C, where A and B are normal subgroups of C. Show that B/A is a normal subgroup of C/A, and that (C/A)/(B/A) is isomorphic to C/B.
Answer: Let f : C -> C/A be the quotient homomorphism, defined as f(c) = cA. This is surjective, so by Problem 2 of homework 7, f(B) = {bA : b is in B} = {all cosets of A in B} = B/A is a normal subgroup of C/A. Let g : C/A -> (C/A)/(B/A) be the quotient homomorphism and consider the composite homomorphism h = gf : C -> C/A -> (C/A)/(B/A). This is surjective since both f : C -> C/A and g : C/A -> (C/A)/(B/A) are. Thus by the 1st Isomorphism Theorem, C/ker(h) is isomorphic to h(C) = (C/A)/(B/A). All we need to do is show that ker(h) = B. But if x is in B, then h(x) = gf(x) = g(xA) is a coset of A in B. But the kernel of a quotient homomorphism is the group you're modding out by. Thus ker(g) = B/A, and xA is a coset of A in B; i.e., xA is in B/A, so g(xA) is the identity in (C/A)/(B/A). This shows that the kernel of h contains B. Now assume x is in C - B (i.e., in C but not in B). Then h(x) = g(xA), but xA is not a coset in B, since x is not in B. This means xB is not in ker(g) = B/A, so g(xA) is not the identity in (C/A)/(B/A), so x is not in ker(h), hence ker(h) is exactly B, as we needed to show.

2. Find all solutions x to:
x mod 37 = 17
x mod 29 =  6

Answer: The set of solutions for x is { 905 + k37*29 : k is an integer }. It is easy to check that 905 is a solution (which you can find directly by either of the two methods discussed in class), and by the Chinese Remainder Theorem, every other solution differs from this one by a multiple of 37*29.

3. Define f : Zm x Zn -> Zmn by f((x, y)) = nx + my mod mn.
• (a) Show that f is a homomorphism.
• (b) If gcd(m, n) = 1, show that f is an isomorphism.
• (c) Find the inverse of f (i.e., find the isomorphism h such that hf = identity and fh = identity) in the case that m = 9 and n = 11.

Answer: (a) Consider f((x,y)+(u,v)). Let a = x + u mod m and let b = y + v mod n, so a + sm = x + u for some s, and b + tn = y + v for some t. Now (x,y)+(u,v) = (a, b) in the group Zm x Zn and f((a, b)) = na + mb mod mn. But f((x, y)) + f((u, v)) = (nx + my) + (nu + mv) mod mn = n(x+u) + m(y+v) mod mn = n(a + sm) + m(b+tn) mod mn = na + mb + mn(s + t) mod mn = na + mb mod mn = f((a, b)) = f((x,y)+(u,v)), so f is a homomorphism.
(b) If gcd(m, n) = 1, then there are x and y such that nx + my = 1. Of course, the given x and y might not be in the ranges 0 <= x < m and 0 <= y < n. So pick s and t such that x + sm and y + tn are in these ranges. Then (x + sm, y + tn) is in Zm x Zn, and f((x + sm, y + tn)) = nx + my + nm(s + t) mod mn = 1 mod mn. Thus 1 is in H = f(Zm x Zn), and since H is a subgroup of Zmn but 1 generates all of Zmn, we see H = Zmn, so f is surjective. Since |Zmn| = |Zm x Zn|*|ker(f)| by Problem 5 on Homework 6, but |Zmn| = mn = |Zm x Zn|, we see |ker(f)| = 1, so f is injective. Thus f is an isomorphism.
(c) For m = 9 and n = 11, we have 5n - 6m = 1, and replacing -6 by 11 - 6 = 5, we have f((5, 5)) = 5n + 5m mod mn = 1. So the inverse h : Zmn -> Zm x Zn must take 1 to (5, 5), and hence h(x) = (5x mod m, 5x mod n). [Note that this is not the same isomorphism we found in class; that one was x -> (x mod m, x mod n). Thus when gcd(m, n) = 1, the easiest isomorphism Zmn -> Zm x Zn to define is x -> (x mod m, x mod n), while the easiest isomorphism Zm x Zn -> Zmn to define going back is (x, y) -> nx + my mod mn, but these are not inverses of each other.]

4. Determine the number of subgroups of Z16 x Z17. Justify your answer.
Answer: Since Z16 x Z17 is isomorphic to the cyclic group Z16*17 = Z272. Thus the number of subgroups of Z16 x Z17 is the same as the number in Z16*17, which is just the number of positive integer factors of 272. Since 16 has 5 factors and 17 only 2, 272 has 5*2 = 10 factors. Thus the number of subgroups is 10.

5. Let N and M be subgroups of a group G.
• (a) If N or M is a normal subgroup of G, show that MN is a subgroup.
• (b) If N and M are normal subgroups of G, show that MN is a normal subgroup of G.

Answer: (a) Since M and N are not empty, MN is nonempty. Say N is normal. Let x and y be in MN. Then x = ab and y = cd, where a and c are in M and b and d are in N. To show MN is closed we must show abcd is in MN. But bc is in Nc, and since N is normal, Nc = cN, so bc = cg for some g in N. Thus abcd = acgn, and since ac is in M and gn is in N, abcd = acgn is in MN as desired. We must also show (xy)-1 is in MN. But (xy)-1 = (abcd)-1 = (d-1)(c-1)(b-1)(a-1). Since (d-1)(c-1) is in N(c-1) = (c-1)N, we know (d-1)(c-1) = (c-1)r for some r in N. Likewise, (b-1)(a-1) = (a-1)s for some s in N, so (c-1)r and (a-1)s are both in MN. As we just saw this means that (xy)-1 = (c-1)r(a-1)s is also in MN. Thus MN is nonempty and closed under multiplication and inversion, so MN is a subgroup. The argument in case M is the normal one is similar.
(b) We now know that MN is a subgroup. Let a be in MN and g in G. We must show that gag-1 is in MN. But a = xy for some x in M and y in N. Thus gag-1 = gxyg-1 = gxg-1gyg-1. But since both M and N are normal, gxg-1 is in M and gyg-1 is in N, hence gag-1 = gxg-1gyg-1 is in MN, as we wanted to show.