## Math 417 Homework 9 Solutions

• [1] Problem #14 on p. 145: Suppose that K is a proper subgroup of H, and H is a proper subgroup of G. If |K| = 42 and |G| = 420, what are the possible orders of H?

By Lagrange's Theorem, we know |K| divides |H|, so |H| = 42k for some k (bigger than 1 since K is a proper subgroup of H). Likewise, 42k divides 420, so k divides 420/42 = 10. Since H is a proper subgroup of G, we know k < 10, so either k = 2 or k = 5, and hence either |H| = 2(42) = 84, or |H| = 5(42) = 210.

• [2] Problem #16 on p. 145: If a is any integer relatively prime to n, prove that aphi(n) mod n = 1.

First note that if a mod n = b mod, then for any positive integer r we have ar mod n = br mod n. (To see this, we must check that ar and br have the same remainder after division by n if a and b do; i.e., that n divides ar - br if n divides a - b. But ar - br = (a - b)(ar-1 + ar-2b + ... + a1br-2 + br-1, and since n divides a - b and a - b divides ar - br, it follows that n divides ar - br, as we wanted to show.) Now let b = a mod n. Thus 0 <= b < n. Moreover, since gcd(a, n) = 1, it follows also that gcd(b, n) = 1. (If not, then some integer bigger s than 1 divides both b and n. But a = qn + b for some integer q since a mod n = b, so s divides a, contradicting our assumption that gcd(a, n) = 1.) We now see that b is in U(n). Thus b|U(n)| mod n = 1 by Corollary 4 on p. 138. But |U(n)| = phi(n), so aphi(n) mod n = bphi(n) mod n = 1, as we wanted to show.

• [3] Problem #30 on p. 145: Every subgroup of Dn of odd order is cyclic.

Let H be a subgroup of odd order. Recall (from Homework 2) that every element of Dn is either a rotation or a reflection. Since H has odd order, Lagrange's Theorem tells us that H contains no reflections (if H contains a reflection f, then f has order 2 so 2 divides |H|, ion which case |H| could not be odd). Thus every element of H is a rotation. Bu the subset of all rotations in Dn is a subgroup, and in fact a cyclic subgroup, generated by the rotation through an angle of 360/n degrees. Thus H is cyclic, since it is a subgroup of a cyclic group.

• [4] Problem #38 on p. 145: Let H and K be subgroups of a group G of order pqr, where p, q and r are distinct primes. If |H| = pq and |K| = qr, prove that the intersection (call it I) of H and K has order q.

Since |I| divides both |H| and |K|, we see that |I divides both qr and qp. But the only common factors of qr and qp are 1 and q. So suppose |I| = 1. Let HK denote the subset {g in G : g = hk for some h in H and some k in K}. Suppose h1 and h2 are in H and that k1 and k2 are in K. If h1k1 = h2k2, then k1k2-1 = h1-1h2, but k1k2-1 is in K and h1-1h2 is in H, so k1k2-1 = h1-1h2 is in I, and by assumption must thus be e (since we are assuming |I| = 1). Thus k1k2-1 = e so k1 = k2, and likewise h1 = h2. Thus the map f : HxK -> HK defined by f((h, k)) = hk is injective. It is obviously surjective, so it is bijective, hence |HK| = |H||K| = prq2. But HK is a subset of G, and this means |HK| = prq2 is bigger than |G| = pqr, which is impossible. Thus |I| = 1 must be false, so |I| = q.

• [5] Let G be a subgroup of Sn, thus G is a group of permutations of the set A = {1, 2, ..., n}, and define the function f : G -> N by f(g) = ng, where ng is the number of elements i of {1, 2, ..., n} such that g(i) = i.
• (a) Prove that any two orbits of G in A are either equal or disjoint.
• (b) If g1, ... , gr are the distinct elements of G, prove that f(g1) + ... + f(gr) = t|G|, where t is the number of orbits of G in A.

(a) Let B = OrbG(x) and C = OrbG(y) be orbits. Assume that B and C have an element, say z, in common. Let w be in B. Then w = j(x) for some j in G. Likewise, z = g(x) for some g in G and z = h(y) for some h in G. Now we see g(j-1(w)) = g(x) = z = h(y), so w = j(g-1(h(y))) = (j(g-1)h)(y) is in C. Thus C contains B, and in the same way we see that B contains C, so B = C.

(b) Consider the set Z = {(g, a) : g is in G, a is in A, and g(a) = a}. For each a in A, let Za be {g in G : (g, a) is in Z}. Of course, g is in Za if and only if g(a) = a, hence Za = stabG(a), thus |Za| = |stabG(a)| = |G|/|orbG(a)|. If b is any element of orbG(a), then by (a) we know orbG(a) and orbG(b) have b in common, so they are equal. Thus |orbG(a)| = |orbG(b)|, so |Za| = |G|/|orbG(a)| = |G|/|orbG(b)| = |Zb|. Thus |Za| is the same for all the elements of orbG(a). So if you add together the orders of |Zb| for every element b of orbG(a), you get |G|/|orbG(a)| times |orbG(a)|, which is just |G|. Now if you add together |Za| for every element of A, you just get |G| times the number of orbits; i.e., you get t|G|. But the subsets Za are disjoint and their union is Z, so if you add together |Za| for every element of A you get |Z|, hence |Z| = t|G|. Now given g in G, define Zg to be {a in A : (g, a) is in Z}. But note that |Zg| = |{a in A : g(a) = a}| = f(g). But just as before, if you add up |Zg| for all g in G you just get |Z|, so |Z| = f(g1) + ... + f(gr), but we determined above that |Z| = t|G|, so f(g1) + ... + f(gr) = t|G|.