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 a^phi(n) mod n = 1.

First note that if a mod n = b mod, then for any positive integer r we have a^r mod n = b^r mod n. (To see this, we must check that a^r and b^r have the same remainder after division by n if a and b do; i.e., that n divides a^r - b^r if n divides a - b. But a^r - b^r = (a - b)(a^r-1 + a^r-2b + ... + a¹b^r-2 + b^r-1, and since n divides a - b and a - b divides a^r - b^r, it follows that n divides a^r - b^r, 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 a^phi(n) mod n = b^phi(n) mod n = 1, as we wanted to show.
[3] Problem #30 on p. 145: Every subgroup of D_n of odd order is cyclic.

Let H be a subgroup of odd order. Recall (from Homework 2) that every element of D_n 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 D_n 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 h₁ and h₂ are in H and that k₁ and k₂ are in K. If h₁k₁ = h₂k₂, then k₁k₂^-1 = h₁^-1h₂, but k₁k₂^-1 is in K and h₁^-1h₂ is in H, so k₁k₂^-1 = h₁^-1h₂ is in I, and by assumption must thus be e (since we are assuming |I| = 1). Thus k₁k₂^-1 = e so k₁ = k₂, and likewise h₁ = h₂. 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| = prq². But HK is a subset of G, and this means |HK| = prq² is bigger than |G| = pqr, which is impossible. Thus |I| = 1 must be false, so |I| = q.
[5] Let G be a subgroup of S_n, thus G is a group of permutations of the set A = {1, 2, ..., n}, and define the function f : G -> N by f(g) = n_g, where n_g 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 g₁, ... , g_r are the distinct elements of G, prove that f(g₁) + ... + f(g_r) = t|G|, where t is the number of orbits of G in A.
(a) Let B = Orb_G(x) and C = Orb_G(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 Z_a be {g in G : (g, a) is in Z}. Of course, g is in Z_a if and only if g(a) = a, hence Z_a = stab_G(a), thus |Z_a| = |stab_G(a)| = |G|/|orb_G(a)|. If b is any element of orb_G(a), then by (a) we know orb_G(a) and orb_G(b) have b in common, so they are equal. Thus |orb_G(a)| = |orb_G(b)|, so |Z_a| = |G|/|orb_G(a)| = |G|/|orb_G(b)| = |Z_b|. Thus |Z_a| is the same for all the elements of orb_G(a). So if you add together the orders of |Z_b| for every element b of orb_G(a), you get |G|/|orb_G(a)| times |orb_G(a)|, which is just |G|. Now if you add together |Z_a| for every element of A, you just get |G| times the number of orbits; i.e., you get t|G|. But the subsets Z_a are disjoint and their union is Z, so if you add together |Z_a| for every element of A you get |Z|, hence |Z| = t|G|. Now given g in G, define Z_g to be {a in A : (g, a) is in Z}. But note that |Z_g| = |{a in A : g(a) = a}| = f(g). But just as before, if you add up |Z_g| for all g in G you just get |Z|, so |Z| = f(g₁) + ... + f(g_r), but we determined above that |Z| = t|G|, so f(g₁) + ... + f(g_r) = t|G|.