- [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-2}b + ... + a^{1}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_{1}and h_{2}are in H and that k_{1}and k_{2}are in K. If h_{1}k_{1}= h_{2}k_{2}, then k_{1}k_{2}^{-1}= h_{1}^{-1}h_{2}, but k_{1}k_{2}^{-1}is in K and h_{1}^{-1}h_{2}is in H, so k_{1}k_{2}^{-1}= h_{1}^{-1}h_{2}is in I, and by assumption must thus be e (since we are assuming |I| = 1). Thus k_{1}k_{2}^{-1}= e so k_{1}= k_{2}, and likewise h_{1}= h_{2}. 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^{2}. But HK is a subset of G, and this means |HK| = prq^{2}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
_{1}, ... , g_{r}are the distinct elements of G, prove that f(g_{1}) + ... + 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_{1}) + ... + f(g_{r}), but we determined above that |Z| = t|G|, so f(g_{1}) + ... + f(g_{r}) = t|G|.