Review Problems for Test 2

Math 345

These problems are provided to help you study. The presence of a problem on this handout does not imply that there will be a similar problem on the test. And the absence of a topic does not imply that it won't appear on the test.

1. $U_n$ is the set of elements of $\integer_n$ which are relatively prime to n. It is a group under multiplication mod n. Consider, in particular, the group $U_{13}$ .

(a) Find the order of $5 \in U_{13}$ .

(b) Find $8^{-1}$ in $U_{13}$ .

(c) List the elements of the subgroup $\langle 10 \rangle$ of $U_{13}$ .

2. (a) List the elements of the subgroup of $\integer_{24}$ generated by 10.

(b) List the elements of the subgroup $\langle 10 \rangle$ of

$$U_{21} = \{1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20\}.$$

3. (a) Find the order of 48 in $\integer_{172}$ .

(b) Find the order of 13 in $U_{35}$ .

4. (a) Let G be a group, and let $g \in G$ . Prove that if $n > 0$ and $g^n = 1$ , then n is a multiple of the order of g.

(b) Suppose that G is a group, $g \in G$ , and $g^{12} = 1$ . What are the possibilities for the order of g?

5. (a) Find the order of 142 in $\integer_{156}$ .

(b) Find an element n in $\integer_{156}$ such that n has order 26 but $n > 78$ .

6. (a) Construct a multiplication table for $U_{18}$ , the group of units mod 18.

(b) $U_{18}$ is cyclic. List all the generators of $U_{18}$ .

7. List the elements of all the subgroups of $\integer_{10}$ . What elements generate $\integer_{10}$ ?

8. (a) List the elements of the subgroup of order 12 in $\integer_{24}$ .

(b) Find all the generators of the subgroup of order 12 in $\integer_{24}$ .

9. Find a generator for the following subgroup of $\integer$ :

$$H = \left\{12 x + 30 y - 33 z \Bigm| x, y, z \in \integer\right\}.$$

10. Consider the group $\integer \times \integer$ with the operation of componentwise addition. Prove directly that $\integer \times \integer$ is not cyclic by showing that no element of the group is a generator.

11. Consider the integers $\integer$ with the group operation

$$m \ast n = m + n - 4.$$

Taking for granted that this gives a group structure on $\integer$ , prove that $(\integer, \ast)$ is cyclic by exhibiting a generator. Note: The identity for $(\integer, \ast)$ is 4, and $n^{-1} = 8 - n$ .

12. (a) Give an example of a group G and elements $x, y \in G$ , such that x has order 2 and y has order 4, and $\langle x \rangle \cap \langle y \rangle$ has order 2.

Note: Remember that the intersection of two sets consists of the elements commmon to both, and the intersection of subgroups is a subgroup.

(b) Give an example of a group G and elements $x, y \in G$ , such that x has order 2 and y has order 4, and $\langle x \rangle \cap \langle y \rangle$ has order 1.

13. Suppose x and y are elements of a group G, x has order 9, and y has order 16. The intersection $\langle x \rangle \cap \langle y \rangle$ is a subgroup of G. What is the order of $\langle x \rangle \cap \langle y \rangle$ ?

Hint: If A is a subgroup of B, then $|A| \mid |B|$ . And $\langle x \rangle \cap \langle y \rangle$ is a subgroup of $\langle x \rangle$ and of $\langle y \rangle$ .

14. Reduce $261^{519} \mod{521}$ to a number in the range $\{0, 1, \ldots, 520\}$ . Note: 521 is prime.

15. Reduce $263^{305} \mod{307}$ to a number in the range $\{0, 1, \ldots 306\}$ . Note: 307 is prime.

16. Reduce $448^{217} \mod{449}$ to a number in the range $\{0, 1, \ldots, 448\}$ .

17. Simplify $\dfrac{250!}{63} \mod{251}$ to a number in the range $\{0, 1, \ldots, 250\}$ .

18. Reduce $386! \mod{389}$ to a number in the range $\{0, 1, \ldots 388\}$ . Note: 389 is prime.

19. Prove that $309^{100} + 404^{102} = 1 \mod{101 \cdot 103}$ .

20. List all the elements of $A_4$ in disjoint cycle notation. For each element, give its order. (Remember that $A_4$ is the subgroup of $S_4$ consisting of the even permutations.)

21. Write the following permutation as a product of disjoint cycles and as a product of transpositions. (Multiply permutations from right to left.)

$$\left(\matrix{1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \cr 4 & 8 & 6 & 5 & 1 & 3 & 7 & 2 \cr}\right)$$

22. (a) What is the order of the permutation $(2\ 6\ 4\ 1)(3\ 5)$ ?

(b) What is the order of the permutation $(2\ 6\ 1)(1\ 3\ 5\ 4)$ ?

23. Let X be a set, and let $S_X$ denote the group of permutations of X under function composition.

(a) Suppose $Y \subset X$ , and let

$$H = \{\sigma \in S_X \mid \sigma(Y) = Y\}.$$

Thus, H consists of permutations which send Y to itself. Prove that H is a subgroup of $S_X$ .

(b) Suppose $X = \{1, 2, 3, 4\}$ and $Y = \{1, 4\}$ . List the permutations in $S_4$ which send Y to itself.

24. Compute the product of the permutations and write the answer as a product of disjoint cycles. (Multiply the permutations right to left.)

(a) $(1\ 5\ 3\ 4)(4\ 2\ 6)$ .

(b) $(1\ 6\ 3)^{-1}(3\ 4\ 2)^2$ .

(c) $[(2\ 4)(3\ 4)]^{722}$ .

25. Write $(4\ 6\ 7\ 1)$ as a product of transpositions. Is this permutation odd or even?

26. Compute

$$(2\ 4\ 1\ 3)(3\ 5\ 1\ 6)(2\ 4)(2\ 4\ 1\ 3)^{-1}.$$

27. How many elements of $S_6$ send the set $\{3, 5\}$ into the set $\{3, 5\}$ ?

28. Let $S_{\integer}$ denote the group of permutations of $\integer$ under function composition. Define

$$H = \left\{\sigma \in S_{\integer} \Bigm| \sigma(\integer^+) \subset \integer^+\right\}.$$

Thus, H consists of permutations of the integers which take the positive integers into the positive integers. For example, consider $f: \integer \to \integer$ given by

$$f(x) = x + 3.$$

f is bijective, since its inverse is given by $g(x) = x - 3$ . And if $x > 0$ , then $f(x) = x + 3 > 0 + 3 = 3$ , so $f \in H$ .

Check each subgroup axiom as it applies to H. If the axiom holds, prove it. If the axiom does not hold, give a specific counterexample.

29. Find the order of $(44, 36)$ in $\integer_{56} \times \integer_{40}$

30. (a) Find an element of order 12 in $\integer_6 \times \integer_8$ .

(b) Prove that there is no element of order 16 in $\integer_6 \times \integer_8$ .

31. List the elements of the subgroup $\langle (4, 6) \rangle$ of $\integer_{10} \times \integer_{30}$ .

32. $\integer \times \integer$ is a group under componentwise addition. Let

$$H = \{(x, y) \mid x, y \in \integer \times \integer \mid 2 x = 7 y\}.$$

Prove that H is a subgroup of $\integer \times \integer$ .

33. $\integer \times \integer$ is a group under componentwise addition. Define $f: \integer \times \integer \to \integer \times \integer$ by

$$f(x, y) = (2 x + 3 y, 7 x - y).$$

(a) Prove that f is a group map.

(b) Prove that $\ker f = \{(0, 0)\}$ .

34. (a) List the elements of the subgroup $\langle (3, 7) \rangle$ in $U_8 \times U_{10}$ .

(b) List the elements of the subgroup $\langle 3 \rangle \times \langle 7 \rangle$ in $U_8 \times U_{10}$ .

35. Find a subgroup of order 8 in $\integer_{12} \times \integer_{14}$ . Does this group have any elements of order 8?

36. (a) List the elements of order 8 in $\integer_8 \times \integer_6$ .

(b) List the elements of order 8 in $\integer_4 \times \integer_6$ .

37. Find the primary decomposition and invariant factor decomposition for $\integer_4 \times \integer_6 \times \integer_{75}$ .

38. (a) Determine the largest order of an element of $\integer_{10} \times \integer_{15} \times \integer_{40}$ .

(b) Find a specific element of largest order in $\integer_{10} \times \integer_{15} \times \integer_{40}$ .

39. $\integer_{2} \times \integer_{10}$ and $\integer_{20}$ are abelian groups of order 20. Explain why they aren't isomorphic.

40. Determine all isomorphism classes of abelian groups of order $2^3\cdot 3^3$ . For each isomorphism class, give the primary decomposition and the corresponding invariant factor decomposition.

41. Suppose G is an abelian group of order 16.

(a) If no element of G has order greater than 2, what are the possible primary decompositions of G?

(b) If G has at least one element of order 8, what are the possible primary decompositions of G?

42. Suppose G is an abelian group of order 1701 and the largest order of an element of G is 63 What are the possible invariant factor decompositions for G?

43. (a) Can $\integer_5$ be isomorphic to the direct product of two of its proper subgroups?

(b) Can $\integer_8$ be isomorphic to the direct product of two of its proper subgroups?

(c) Can $S_3$ be isomorphic to the direct product of two of its proper subgroups?

44. Suppose A, B, C, and D are groups, all with the operation denoted by multiplication. Suppose that $f: A \to C$ and $g: B \to D$ are group maps. Define $f \times g: A \times B \to C \times D$ by

$$(f \times g)(a, b) = (f(a), g(b)).$$

(a) Prove that $f \times g$ is a group map.

(b) Prove that

$$\ker (f \times g) = \{(a, b) \in A \times B \mid a \in \ker f \quad\hbox{and}\quad b \in \ker g\}.$$

45. (a) Explain why $\integer_2 \times \integer_3$ and $\integer_3 \times \integer_2$ are not identical as sets.

(b) Show that if G and H are groups, then $G \times H \approx H \times G$ .

46. (a) Suppose a group has 48 elements. What are the possiblities for the order of a subgroup of G?

(b) A subgroup of a group contains 7 elements. The subgroup has 3 left cosets. What is the order of the group?

47. List the elements of the cosets of $\langle 11 \rangle$ in $U_{30}$ .

48. List the elements of the cosets of $\langle 8 \rangle$ in $\integer_{12}$ .

49. List the elements of the cosets of $\langle (1, (1\ 3)) \rangle$ in $\integer_3 \times S_3$ .

50. (a) List the cosets of the subgroup $4\integer$ of $\integer$ .

(b) What coset of $4\integer$ contains 771?

Solutions to the Review Problems for Test 2

1. $U_n$ is the set of elements of $\integer_n$ which are relatively prime to n. It is a group under multiplication mod n. Consider, in particular, the group $U_{13}$ .

(a) Find the order of $5 \in U_{13}$ .

(b) Find $8^{-1}$ in $U_{13}$ .

(c) List the elements of the subgroup $\langle 10\rangle$ of $U_{13}$ .

(a)

$$\eqalign{ 5^2 & = 12 \mod{13} \cr 5^3 & = 125 = 8 \mod{13} \cr 5^4 & = 625 = 1 \mod{13} \cr}$$

Therefore, the order of 5 is 4.

(b)

$$\vbox{\offinterlineskip \halign{& \vrule # & \strut \hfil \quad # \quad \hfil \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & 13 & & - & & 5 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & 8 & & 1 & & 3 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & 5 & & 1 & & 2 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & 3 & & 1 & & 1 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & 2 & & 1 & & 1 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & 1 & & 2 & & 0 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} }} $$

$$\eqalign{ 8 \cdot 5 + 13 \cdot (-3) & = 1 \cr 8 \cdot 5 & = 1 \mod{13} \cr}$$

Hence, $8^{-1} = 5$ in $U_{13}$ .

(c)

$$\eqalign{ 10^2 & = 100 = 9 \mod{13} \cr 10^3 & = 1000 = 12 \mod{13} \cr 10^4 & = 10000 = 3 \mod{13} \cr 10^5 & = 100000 = 4 \mod{13} \cr 10^6 & = 1000000 = 1 \mod{13} \cr}$$

Hence,

$$\langle 10\rangle = \{1, 10, 9, 12, 3, 4, 1\}.\quad\halmos$$

2. (a) List the elements of the subgroup of $\integer_{24}$ generated by 10.

(b) List the elements of the subgroup $\langle 10 \rangle$ of $U_{21}$ .

(a) I add 10 to itself (mod 24) until I get back to 0:

$$\langle 10\rangle = \{0, 10, 20, 6, 16, 2, 12, 22, 8, 18, 4, 14\}. \quad\halmos$$

$$U_{21} = \{1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20\}.$$

(b) I multiply 10 by itself (mod 21) until I get back to 1:

$$\langle 10 \rangle = \{1, 10, 16, 13, 4, 19\}.\quad\halmos$$

3. (a) Find the order of 48 in $\integer_{172}$ .

(b) Find the order of 13 in $U_{35}$ .

(a) Since $(48,172) = 4$ , the order of 48 is $\dfrac{172}{4} = 43$ .

In other words, if you add 48 to itself 43 times, you'll get 0 mod 172, and no smaller multiple of 48 gives 0.

(b) I don't know that $U_{35}$ is cyclic, so I'll do the computation directly. I raise 13 to successive powers (mod 35) until I get 1, the identity in $U_{35}$ :

$$13^2 = 169 = 29, \quad 13^3 = 2197 = 27, \quad 13^4 = 28561 = 1.$$

Therefore, 13 has order 4 in $U_{35}$ .

4. (a) Let G be a group, and let $g \in G$ . Prove that if $n > 0$ and $g^n = 1$ , then n is a multiple of the order of g.

(b) Suppose that G is a group, $g \in G$ , and $g^{12} = 1$ . What are the possibilities for the order of g?

(a) Let m be the order of g, so $a^m = 1$ . By the Division Algorithm,

$$n = q m + r, \quad\hbox{where}\quad 0 \le r < m.$$

Then

$$1 = a^n = a^{q m + r} = (a^m)^q \cdot a^r = 1 \cdot a^r = a^r.$$

Thus, $a^r = 1$ . But m is the smallest positive power of a such that $a^m = 1$ , and $0 \le r < m$ . Therefore, r can't be positive, so $r = 0$ . This means that $n = q m$ , so n is multiple of the order of g.

(b) By (a), the order of g must divide 12. Therefore, the order of g could be 1, 2, 3, 4, 6, or 12.

5. (a) Find the order of 142 in $\integer_{156}$ .

(b) Find an element n in $\integer_{156}$ such that n has order 26 but $n > 78$ .

(a) The order is $\dfrac{156}{(142, 156)} = \dfrac{156}{2} = 78$ .

(b) Since the order of n is $\dfrac{156}{(n, 156)}$ , I want

$$\dfrac{156}{(n, 156)} = 26, \quad\hbox{or}\quad (n, 156) = \dfrac{156}{26} = 6.$$

Notice that $156 = 6 \cdot (2 \cdot 13)$ . Therefore, I can ensure that $(n, 156) = 6$ by taking a multiple $6 k$ of 6 such that k does not have 2 or 13 as a factor. I also want $6 k > 78$ , so $k > 13$ . The easiest way to do this is to take k to be a prime number greater than 13; I'll use $k = 17$ . Thus, $n = 6 k = 6 \cdot 17 = 102$ .

Now 102 is greater than 78, and $(102, 156) = 6$ , so 102 has order $\dfrac{156}{6} = 26$ in $\integer_{156}$ .

6. (a) Construct a multiplication table for $U_{18}$ , the group of units mod 18.

(b) $U_{18}$ is cyclic. List all the generators of $U_{18}$ .

(a)

$$\vbox{\offinterlineskip \halign{& \vrule # & \strut \hfil \quad # \quad \hfil \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr & & & 1 & & 5 & & 7 & & 11 & & 13 & & 17 & \cr height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr & 1 & & 1 & & 5 & & 7 & & 11 & & 13 & & 17 & \cr height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr & 5 & & 5 & & 7 & & 17 & & 1 & & 11 & & 13 & \cr height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr & 7 & & 7 & & 17 & & 13 & & 5 & & 1 & & 11 & \cr height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr & 11 & & 11 & & 1 & & 5 & & 13 & & 17 & & 7 & \cr height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr & 13 & & 13 & & 11 & & 1 & & 17 & & 7 & & 5 & \cr height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr & 17 & & 17 & & 13 & & 11 & & 7 & & 5 & & 1 & \cr height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} }}\quad\halmos $$

(b) 5 generates $U_{18}$ :

$$\langle 5 \rangle = \{1, 5, 7, 17, 13, 11\}.$$

To find the other generator, note that $U_{18}$ is cyclic of order 6. In $\integer_6$ , the cyclic group of order 6, the generators are 1 and $-1 = 5$ . So the other generator of $U_{18}$ must be $5^{-1} = 11$ .

7. List the elements of all the subgroups of $\integer_{10}$ . What elements generate $\integer_{10}$ ?

There is one subgroup of order n for each natural number n dividing 10. Hence, there are subgroups of order 1, 2, 5, and 10. I have

$$\eqalign{ \langle 1 \rangle & = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\} \cr \langle 2 \rangle & = \{0, 2, 4, 6, 8\} \cr \langle 5 \rangle & = \{0, 5\} \cr \langle 0 \rangle & = \{0\} \cr}$$

The generators are 1, 3, 7, and 9: The elements which are relatively prime to 10.

8. (a) List the elements of the subgroup of order 12 in $\integer_{24}$ .

(b) Find all the generators of the subgroup of order 12 in $\integer_{24}$ .

(a) The subgroup of order 12 in $\integer_{24}$ is

$$\langle 2 \rangle = \{0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22\}. \quad\halmos$$

(b) Since $\integer_{24}$ is cyclic, the subgroup $\langle 2 \rangle$ of order 12 is a cyclic group of order 12.

Now $\integer_{12}$ is cyclic of order 12, and the generators are the elements relatively prime to 12, namely 1, 5, 7, and 11. But $\integer_{12}$ and $\langle 2 \rangle$ are isomorphic by the function $f(x) = 2 x \mod{24}$ . So the generators of $\langle 2 \rangle$ are

$$2 \cdot 1 = 2, \quad 2 \cdot 5 = 10, \quad 2 \cdot 7 = 14, \quad 2 \cdot 11 = 22.\quad\halmos$$

9. Find a generator for the following subgroup of $\integer$ :

$$H = \left\{12 x + 30 y - 33 z \Bigm| x, y, z \in \integer\right\}.$$

Note that H must be cyclic, since it's a subgroup of $\integer$ .

The greatest common divisor of 12, 30, and -33 is 3, so I'll show that 3 generates H:

$$H = \langle 3 \rangle.$$

First, if $12 x + 30 y - 33 z \in H$ , then

$$12 x + 30 y - 33 z = 3(4 x + 10 y - 11 z) \in \langle 3 \rangle.$$

Conversely, note that

$$3 = 12 \cdot 0 + 30 \cdot (-1) - 33 \cdot (-1) \in H.$$

Hence,

$$3 n = 12 \cdot 0 + 30 \cdot (-n) - 33 \cdot (-n) \in H.$$

This shows that $\langle 3 \rangle \subset H$ .

Therefore, $H = \langle 3 \rangle$ .

10. Consider the group $\integer \times \integer$ with the operation of componentwise addition. Prove directly that $\integer \times \integer$ is not cyclic by showing that no element of the group is a generator.

No element of the form $(x, 0)$ can generate: If $n \cdot (x, 0) = (1, 1)$ , then $(x, 0) = (1, 1)$ , and the equality of the second components gives a contradiction. This shows that $(1, 1)$ is not in the subgroup generated by $(x, 0)$ , so $\langle (x, 0) \rangle \ne \integer \times \integer$ .

A similar argument shows that no element of the form $(0, y)$ can generate.

Assume, then, that $(x, y)$ is a generator, where $x, y \ne 0$ . I claim that $(1, 0)$ is not a multiple of $(x, y)$ . For if $(1, 0) = n \cdot (x, y)$ , then

$$\eqalign{ (1, 0) & = n \cdot (x, y) \cr (1, 0) & = (n x, n y) \cr}$$

Equating the second components, I get $n y = 0$ , so $n = 0$ (since $y \ne 0$ ). But equating the first components now gives

$$1 = n x = 0 \cdot x = 0.$$

This contradiction shows that $(1, 0)$ is not in the subgroup generated by $(x, y)$ , so $\langle (x, y) \rangle \ne \integer \times \integer$ .

Therefore, no element of $\integer \times \integer$ generates, so $\integer \times \integer$ is not cyclic.

11. Consider the integers $\integer$ with the group operation

$$m \ast n = m + n - 4.$$

Taking for granted that this gives a group structure on $\integer$ , prove that $(\integer, \ast)$ is cyclic by exhibiting a generator.

Notice that

$$\eqalign{ 3 \ast 3 & = 3 + 3 - 4 = 2 \cr 3 \ast (3 \ast 3) & = 3 \ast 2 = 3 + 2 - 4 = 1 \cr 3 \ast (3 \ast (3 \ast 3)) & = 3 \ast 1 = 3 + 1 - 4 = 0 \cr}$$

For $n \ge 1$ , write

$$3^n = \overbrace{3 \ast 3 \ast \cdots \ast 3}^{\rm n\ times}.$$

The pattern above suggests the formula

$$3^n = 4 - n \quad\hbox{for}\quad n \ge 1.$$

Since $3^1 = 3$ and $4 - 1 = 3$ , the result is true for $n = 1$ .

Assume that $3^n = 4 - n$ . Then

$$\eqalign{ 3^{n+1} & = 3 \ast 3^n \cr & = 3 + 3^n - 4 \cr & = 3 + (4 - n) - 4 \cr & = 3 - n \cr & = 4 - (n + 1) \cr}$$

This proves the result for $n + 1$ , so the result is true for all $n \ge 1$ by induction.

As $n = 1, 2, 3, \ldots$ , the powers $3^n = 4 - n$ give the numbers $3, 2, 1, 0, -1, \ldots$ .

The identity in $(\integer, \ast)$ is 4, so $3^0 = 4$ .

To get the numbers greater than 4, just take inverses. If $n \ge 1$ , then

$$3^{-n} = (3^n)^{-1} = (4 - n)^{-1} = 8 - (4 - n) = 4 + n.$$

As $n = 1, 2, 3, \ldots$ , the negative powers $3^{-n} = 4 + n$ give the numbers $5, 6, 7, \ldots$ .

This shows that every element in $\integer$ is a power of 3, so 3 is a generator and $(\integer, \ast)$ is cyclic.

12. (a) Give an example of a group G and elements $x, y \in G$ , such that x has order 2 and y has order 4, and $\langle x \rangle \cap \langle y \rangle$ has order 2.

(b) Give an example of a group G and elements $x, y \in G$ , such that x has order 2 and y has order 4, and $\langle x \rangle \cap \langle y \rangle$ has order 1.

(a) In $\integer_4$ , the element 1 has order 4 and the element 2 has order 2. I have

$$\langle 1 \rangle = \{0, 1, 2, 3\} \quad\hbox{and}\quad \langle 2 \rangle = \{0, 2\}.$$

Thus, $\langle 1 \rangle \cap \langle 2 \rangle$ has order 2:

$$\langle 1 \rangle \cap \langle 2 \rangle = \{0, 2\}.\quad\halmos$$

(b) In $\integer_2 \times \integer_4$ , consider the subgroups

$$\langle (1, 0) \rangle = \{(0, 0), (1, 0)\} \quad\hbox{and}\quad \langle (0, 1) \rangle = \{(0, 0), (0, 1), (0, 2), (0, 3)\}.$$

Then $(1, 0)$ has order 2 and $(0, 1)$ has order 4. Moreover,

$$\langle (1, 0) \rangle \cap \langle (0, 1) \rangle = \{(0, 0)\}.$$

So the intersection has order 1.

Here's a more complicated example.

In $D_4$ , the group of symmetries of a square, let r denote rotation through $90^\circ$ counterclockwise. Then r generates a subgroup of order 4:

$$\langle r \rangle = \{\id, r, r^2, r^3\}.$$

$r^2$ is rotation through $180^\circ$ , and $r^3$ is rotation through $270^\circ$ .

Let m denote a reflection --- say reflection across a line through the center bisecting opposite sides of the square. Then m generates a subgroup of order 2:

$$\langle m \rangle = \{\id, m\}.$$

Now

$$\langle r \rangle \cap \langle m \rangle = \{\id\}.$$

To see that m can't be an element of $\langle r \rangle$ , note that m "flips the square over", whereas none of the rotations r, $r^2$ or $r^3$ do this. So the two subgroups can't overlap in two elements, because this would mean $m \in \langle r \rangle$ .

In this case, the intersection $\langle r \rangle \cap \langle m \rangle$ has order 1.

13. Suppose x and y are elements of a group G, x has order 9, and y has order 16. The intersection $\langle x \rangle \cap \langle y \rangle$ is a subgroup of G. What is the order of $\langle x \rangle \cap \langle y \rangle$ ?

$\langle x \rangle \cap \langle y \rangle$ is a subgroup of $\langle x \rangle$ , which is a cyclic group of order 9. Therefore, the order of $\langle x \rangle \cap \langle y \rangle$ is 1, 3, or 9.

$\langle x \rangle \cap \langle y \rangle$ is a subgroup of $\langle y \rangle$ , which is a cyclic group of order 16. Therefore, the order of $\langle x \rangle \cap \langle y \rangle$ is 1, 2, 4, 8, or 16.

The only way of satisfying both of these conditions is if the order of $\langle x \rangle \cap \langle y \rangle$ is 1.

14. Reduce $261^{519} \mod{521}$ to a number in the range $\{0, 1, \ldots, 520\}$ . Note: 521 is prime.

By Fermat's Theorem,

$$261^{520} = 1 \mod{521}.$$

Let $x = 261^{519} \mod{521}$ . Then

$$\eqalign{ x & = 261^{519} \mod{521} \cr 261 \cdot x & = 261 \cdot 261^{519} \mod{521} \cr 261x & = 261^{520} \mod{521} \cr 261x & = 1 \mod{521} \cr 2 \cdot 261x & = 2 \cdot 1 \mod{521} \cr 522x & = 2 \mod{521} \cr x & = 2 \mod{521} \cr}$$

Note: In general, to solve an equation like "$261x = 1 \mod{521}$ ", I'd need to find $261^{-1} \mod{521}$ using the Extended Euclidean algorithm. But I happened to notice that 261 was half of $522 = 1 \mod{521}$ , so I had a shortcut.

15. Reduce $263^{305} \mod{307}$ to a number in the range $\{0, 1, \ldots 306\}$ . Note: 307 is prime.

By Fermat's theorem, $263^{306} = 1 \mod{307}$ . So

$$\eqalign{ x & = 263^{305} \mod{307} \cr 263 x & = 263^{306} = 1 \mod{307} \cr}$$

$$\vbox{\offinterlineskip \halign{& \vrule # & \strut \hfil \quad # \quad \hfil \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & 307 & & - & & 7 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & 263 & & 1 & & 6 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & 44 & & 5 & & 1 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & 43 & & 1 & & 1 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & 1 & & 43 & & 0 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} }} $$

$$\eqalign{ 6 \cdot 307 + (-7) \cdot 263 & = 1 \cr (-7) \cdot 263 & = 1 \mod{307} \cr 300 \cdot 263 & = 1 \mod{307} \cr}$$

Hence, $263^{-1} = 300 \mod{307}$ .

Therefore,

$$\eqalign{ 300 \cdot 263 x & = 300 \cdot 1 \mod{307} \cr x & = 300 \mod{307} \cr} \quad\halmos$$

16. Reduce $448^{217} \mod{449}$ to a number in the range $\{0, 1, \ldots, 448\}$ .

Since $448 = -1 \mod{449}$ , I have

$$448^{217} = (-1)^{217} = -1 = 448 \mod{449}.\quad\halmos$$

17. Simplify $\dfrac{250!}{63} \mod{251}$ to a number in the range $\{0, 1, \ldots, 250\}$ .

By Wilson's theorem, $250! = -1 \mod{251}$ . So

$$\eqalign{ x & = \dfrac{250!}{63} \mod{251} \cr \noalign{\vskip2pt} 63 x & = 250! = -1 \mod{251} \cr}$$

$$\vbox{\offinterlineskip \halign{& \vrule # & \strut \hfil \quad # \quad \hfil \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & 251 & & - & & 4 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & 63 & & 3 & & 1 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & 62 & & 1 & & 1 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & 1 & & 62 & & 0 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} }} $$

$$1 = (63, 251) = 4 \cdot 63 + (-1) \cdot 251.$$

It follows that $63^{-1} = 4 \mod{251}$ , so

$$\eqalign{ 4 \cdot 63 x & = 4 \cdot (-1) \mod{251} \cr x & = -4 = 247 \mod{251} \quad\halmos \cr}$$

18. Reduce $386! \mod{389}$ to a number in the range $\{0, 1, \ldots 388\}$ . Note: 389 is prime.

Let $x = 386! \mod{389}$ . Then

$$\eqalign{ x & = 386! \mod{389} \cr 388 \cdot 387 \cdot x & = 388 \cdot 387 \cdot 386! \mod{389} \cr 388 \cdot 387 \cdot x & = 388! \mod{389} \cr 388 \cdot 387 \cdot x & = -1 \mod{389} \cr (-1) \cdot (-2) \cdot x & = -1 \mod{389} \cr 2x & = -1 \mod{389} \cr 195 \cdot 2x & = 195 \cdot -1 \mod{389} \cr 390x & = -195 \mod{389} \cr x & = 194 \mod{389} \quad\halmos \cr}$$

19. Prove that $309^{100} + 404^{102} = 1 \mod{101 \cdot 103}$ .

Since $101 \notdiv 309$ , Fermat's Theorem gives $309^{100} = 1 \mod{101}$ . Since $101 \mid 404$ , it follows that

$$309^{100} + 404^{102} = 1 + 0 = 1 \mod{101}.$$

Similarly, $103 \notdiv 404$ , so Fermat's Theorem gives $404^{102} = 1 \mod{103}$ . Since $103 \mid 309$ , it follows that

$$309^{100} + 404^{102} = 0 + 1 = 1 \mod{103}.$$

Since $309^{100} + 404^{102}$ is congruent to 1 mod 101 and mod 103, and since $(101, 103) = 1$ , it follows that

$$309^{100} + 404^{102} = 1 \mod{101 \cdot 103}.\quad\halmos$$

20. List all the elements of $A_4$ in disjoint cycle notation. For each element, give its order.

$A_4$ is the subgroup of even permutations in $S_4$ . This is half of $S_4$ : twelve elements. To list them, note that if a, b, and c are distinct, $(a\ b\ c) = (a\ c)(a\ b)$ is even, and these 3-cycles have order 3. And if the pairs $\{a, b\}$ and $\{c, d\}$ are distinct, then $(a\ b)(c\ d)$ is even, and has order 2. (In particular, such a product of transpositions is different from the 3-cycles mentioned earlier.)

If you simply list all possible 3-cycles and all possible products of disjoint transpositions (and the identity), you wind up with 12 elements --- all of $A_4$ .

$$\vbox{\offinterlineskip \halign{& \vrule # & \strut \hfil \quad # \quad \hfil \cr \noalign{\hrule} height2pt & \omit & & \omit & \cr & Element of $A_4$ & & Order & \cr height2pt & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & \cr & \hbox{id} & & 1 & \cr height2pt & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & \cr & $(1\ 2)(3\ 4)$ & & 2 & \cr height2pt & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & \cr & $(1\ 3)(2\ 4)$ & & 2 & \cr height2pt & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & \cr & $(1\ 4)(2\ 3)$ & & 2 & \cr height2pt & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & \cr & $(1\ 2\ 3)$ & & 3 & \cr height2pt & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & \cr & $(1\ 2\ 4)$ & & 3 & \cr height2pt & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & \cr & $(1\ 3\ 4)$ & & 3 & \cr height2pt & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & \cr & $(1\ 3\ 2)$ & & 3 & \cr height2pt & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & \cr & $(1\ 4\ 2)$ & & 3 & \cr height2pt & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & \cr & $(1\ 4\ 3)$ & & 3 & \cr height2pt & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & \cr & $(2\ 3\ 4)$ & & 3 & \cr height2pt & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & \cr & $(2\ 4\ 3)$ & & 3 & \cr height2pt & \omit & & \omit & \cr \noalign{\hrule} }}\quad\halmos$$

21. Write the following permutation as a product of disjoint cycles and as a product of transpositions. (Multiply permutations from right to left.)

$$\left(\matrix{1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \cr 4 & 8 & 6 & 5 & 1 & 3 & 7 & 2 \cr}\right)$$

Right-to-left:

$$\left(\matrix{ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \cr 4 & 8 & 6 & 5 & 1 & 3 & 7 & 2 \cr}\right) = (1\ 4\ 5)(2\ 8)(3\ 6) = (1\ 5)(1\ 4)(2\ 8)(3\ 6).\quad\halmos$$

22. (a) What is the order of the permutation $(2\ 6\ 4\ 1)(3\ 5)$ ?

(b) What is the order of the permutation $(2\ 6\ 1)(1\ 3\ 5\ 4)$ ?

(a) $(2\ 6\ 4\ 1)$ has order 4 and $(3\ 5)$ has order 2. Since the cycles are disjoint, they commute, and the order of the product is the least common multiple of the orders of the factors: $[4, 2] = 4$ .

(b) The cycles are not disjoint, so I have to multiply and write the product in disjoint cycle form first:

$$\matrix{ & 1 & 2 & 3 & 4 & 5 & 6 \cr (1\ 3\ 5\ 4) & & & & & & \cr & 3 & 2 & 5 & 1 & 4 & 6 \cr (2\ 6\ 1) & & & & & & \cr & 3 & 6 & 5 & 2 & 4 & 1 \cr}$$

Thus, $(2\ 6\ 1)(1\ 3\ 5\ 4) = (1\ 3\ 5\ 4\ 2\ 6)$ , and the permutation has order 6.

23. Let X be a set, and let $S_X$ denote the group of permutations of X under function composition.

(a) Suppose $Y \subset X$ , and let

$$H = \{\sigma \in S_X \mid \sigma(Y) = Y\}.$$

Thus, H consists of permutations which send Y to itself. Prove that H is a subgroup of $S_X$ .

(b) Suppose $X = \{1, 2, 3, 4\}$ and $Y = \{1, 4\}$ . List the permutations in $S_4$ which send Y to itself.

(a) First, $\id(Y) = Y$ , so $\id \in H$ .

Suppose $\sigma, \tau \in H$ , so $\sigma(Y) = Y$ and $\tau(Y) = Y$ . Then

$$(\sigma \cdot \tau)(Y) = \sigma[\tau(Y)] = \sigma(Y) = Y.$$

Hence, $\sigma \cdot \tau \in H$ .

Finally, suppose $\sigma \in H$ , so $\sigma(Y) = Y$ . Then

$$\eqalign{ \sigma^{-1}[\sigma(Y)] & = \sigma^{-1}(Y) \cr Y & = \sigma^{-1}(Y) \cr}$$

Therefore, $\sigma^{-1} \in H$ .

Hence, H is a subgroup of $S_X$ .

(b) The permutations in $S_4$ which send Y to itself are $\id$ , $(1\ 4)$ , $(2\ 3)$ , and $(1\ 4) (2\ 3)$ .

24. Compute the product of the permutations and write the answer as a product of disjoint cycles. (Multiply the permutations right to left.)

(a) $(1\ 5\ 3\ 4)(4\ 2\ 6)$ .

(b) $(1\ 6\ 3)^{-1}(3\ 4\ 2)^2$ .

(c) $[(2\ 4)(3\ 4)]^{722}$ .

(a)

$$\matrix{ 1 & 2 & 3 & 4 & 5 & 6 & \cr & & & & & & (4\ 2\ 6) \cr 1 & 6 & 3 & 2 & 5 & 4 & \cr & & & & & & (1\ 5\ 3\ 4) \cr 5 & 6 & 4 & 2 & 3 & 1 & \cr}$$

$$(1\ 5\ 3\ 4)(4\ 2\ 6) = (1\ 5\ 3\ 4\ 2\ 6).\quad\halmos$$

(b)

$$(1\ 6\ 3)^{-1}(3\ 4\ 2)^2 = (3\ 6\ 1)(3\ 2\ 4) = (1\ 3\ 2\ 4\ 6).$$

$$\matrix{ 1 & 2 & 3 & 4 & 5 & 6 & \cr & & & & & & (3\ 2\ 4) \cr 1 & 4 & 2 & 3 & 5 & 6 & \cr & & & & & & (3\ 6\ 1) \cr 3 & 4 & 2 & 6 & 5 & 1 & \cr}$$

(c) First, $(2\ 4)(3\ 4) = (2\ 4\ 3)$ .

$$\matrix{ 2 & 3 & 4 & \cr & & & (3\ 4) \cr 2 & 4 & 3 & \cr & & & (2\ 4) \cr 4 & 2 & 3 & \cr}$$

Since $(2\ 4\ 3)$ has order 3,

$$[(2\ 4)(3\ 4)]^{722} = (2\ 4\ 3)^{722} = [(2\ 4\ 3)^3]^{240} \cdot (2\ 4\ 3)^2 = \hbox{id} \cdot (2\ 4\ 3)^2 = (2\ 3\ 4).\quad\halmos$$

25. Write $(4\ 6\ 7\ 1)$ as a product of transpositions. Is this permutation odd or even?

$$(4\ 6\ 7\ 1) = (4\ 1)(4\ 7)(4\ 6).$$

Since it's a product of 3 transpositions, it is odd.

26. Compute

$$(2\ 4\ 1\ 3)(3\ 5\ 1\ 6)(2\ 4)(2\ 4\ 1\ 3)^{-1}.$$

You can do this directly by multiplying out the permutations.

$$\matrix{ 1 & 2 & 3 & 4 & 5 & 6 & \cr & & & & & & (3\ 1\ 4\ 2) \cr 4 & 3 & 1 & 2 & 5 & 6 & \cr & & & & & & (2\ 4) \cr 2 & 3 & 1 & 4 & 5 & 6 & \cr & & & & & & (3\ 5\ 1\ 6) \cr 2 & 5 & 6 & 4 & 1 & 3 & \cr & & & & & & (2\ 4\ 1\ 3) \cr 4 & 5 & 6 & 1 & 3 & 2 & \cr}$$

Alternatively, you can use the following fact about the conjugate of a cycle by a permutation: If $\sigma$ and $\tau$ are permutations and $\tau$ is written as a product of cycles, then $\sigma \tau \sigma^{-1}$ can be found by applying $\sigma$ to the elements of the cycles in $\tau$ .

That is, just apply $(2\ 4\ 1\ 3)$ to each of the numbers in $(3\ 5\ 1\ 6)$ , then to each of the numbers in $(2\ 4)$ . This gives

$$(2\ 4\ 1\ 3)(3\ 5\ 1\ 6)(2\ 4)(2\ 4\ 1\ 3)^{-1} = (2\ 5\ 3\ 6)(4\ 1).\quad\halmos$$

27. How many elements of $S_6$ send the set $\{3, 5\}$ into the set $\{3, 5\}$ ?

Let $\sigma \in S_6$ be a permutation which sends the set $\{3, 5\}$ into the set $\{3, 5\}$ . Since permutations are injective, different elements must go to different places. Thus, either

$$\sigma(3) = 3 \quad\hbox{and}\quad \sigma(5) = 5, \quad\hbox{or}\quad \sigma(3) = 5 \quad\hbox{and}\quad \sigma(5) = 3.$$

That is, there are two possibilities.

$\sigma$ also permutes the elements $\{1, 2, 4, 6\}$ among themselves. There are $4! = 24$ such permutations.

Therefore, there are a total of $24\cdot 2 = 48$ elements of $S_6$ which send the set $\{3, 5\}$ into the set $\{3, 5\}$ .

28. Let $S_{\integer}$ denote the group of permutations of $\integer$ under function composition. Define

$$H = \left\{\sigma \in S_{\integer} \Bigm| \sigma(\integer^+) \subset \integer^+\right\}.$$

(H is the set of permutations of the set of integers that take positive integers to positive integers.)

Check each subgroup axiom as it applies to H. If the axiom holds, prove it. If the axiom does not hold, give a specific counterexample.

Suppose that $\tau, \sigma \in H$ , so $\tau(\integer^+) \subset \integer^+$ and $\sigma(\integer^+) \subset \integer^+$ . Then

$$(\tau \cdot \sigma)(\integer^+) = \tau(\sigma(\integer^+)) \subset \tau(\integer^+) \subset \integer^+.$$

Therefore, $\tau \cdot \sigma \in H$ .

Since $\id(\integer^+) = \integer^+ \subset \integer^+$ , it follows that $\id \in H$ .

Consider the function $f: \integer \to \integer$ given by

$$f(n) = n + 1.$$

f is bijective: Its inverse is $f^{-1}(n) = n - 1$ . Thus, $f \in S_{\integer}$ . Moreover, if $n \in \integer^+$ , then $n > 0$ , so

$$f(n) = n + 1 > 0 + 1 = 1.$$

Hence, $f(n) \in \integer^+$ , and so $f(\integer^+) \subset \integer^+$ . Thus, $f \in H$ .

However, $f^{-1} \notin H$ , since $f^{-1}(1) = 0 \notin \integer^+$ .

Thus, H is not a subgroup of $S_{\integer}$ .

29. Find the order of $(44, 36)$ in $\integer_{56} \times \integer_{40}$ .

The order of 44 in $\integer_{56}$ is

$$\dfrac{56}{(56, 44)} = \dfrac{56}{4} = 14.$$

The order of 36 in $\integer_{40}$ is

$$\dfrac{40}{(40, 36)} = \dfrac{40}{4} = 10.$$

Hence, the order of $(44, 36)$ in $\integer_{56} \times \integer_{40}$ is $[14, 10] = 70$ .

30. (a) Find an element of order 12 in $\integer_6 \times \integer_8$ .

(b) Prove that there is no element of order 16 in $\integer_6 \times \integer_8$ .

(a) 2 has order 3 in $\integer_6$ and 2 has order 4 in $\integer_8$ , so $(2, 2)$ has order $[3, 4] = 12$ in $\integer_6 \times \integer_8$ .

(b) Let $(a, b) \in \integer_6 \times \integer_8$ . Suppose a has order m in $\integer_6$ and b has order n in $\integer_8$ . The order of $(a, b)$ is $[m, n]$ .

Assume that $[m, n] = 16$ .

The divisors of 6 and 8 are

$$6:\ 1,\, 2,\ 3,\ 6$$

$$8:\ 1,\ 2,\ 4,\ 8$$

Thus, $m \in \{1, 2, 3, 6\}$ and $n \in \{1, 2, 4, 8\}$ .

If $m = 3$ or $m = 6$ , then $3 \mid m \mid [m, n] = 16$ , which is a contradiction. Hence, $m = 1$ or $m = 2$ .

If $m = 1$ , then

$$16 = [m, n] = [1, n] = n.$$

But 16 is not a divisor of 8, as n is assumed to be. This is a contradiction.

Finally, suppose $m = 2$ . Since there are only 4 possibilities for n, I'll just check cases:

$$[2, 1] = 2, \quad [2, 2] = 2, \quad [2, 4] = 4, \quad [2, 8] = 8.$$

In no case do I have $[m, n] = 16$ .

This final contradiction shows that no element of $\integer_6 \times \integer_8$ has order 16.

31. List the elements of the subgroup $\langle (4, 6) \rangle$ of $\integer_{10} \times \integer_{30}$ .

$$\langle (4, 6) \rangle = \{(0, 0), (4, 6), (8, 12), (2, 18), (6, 24)\}.\quad\halmos$$

32. $\integer \times \integer$ is a group under componentwise addition. Let

$$H = \{(x, y) \mid x, y \in \integer \times \integer \mid 2 x = 7 y\}.$$

Prove that H is a subgroup of $\integer \times \integer$ .

Since $2 \cdot 0 = 0 = 7 \cdot 0$ , it follows that $(0, 0) \in H$ .

Suppose $(x, y) \in H$ . Then

$$\eqalign{ 2 x & = 7 y \cr -2 x & = -7 y \cr 2 (-x) & = 7 (-y) \cr}$$

Hence,

$$-(x, y) = (-x, -y) \in H.$$

Suppose $(a, b), (c, d) \in H$ . Then

$$2 a = 7 b \quad\hbox{and}\quad 2 c = 7 d.$$

Hence,

$$\eqalign{ 2 a + 2 c & = 7 b + 7 d \cr 2 (a + c) & = 7 (b + d) \cr}$$

Therefore,

$$(a, b) + (c, d) = (a + c, b + d) \in H.\quad\halmos$$

33. $\integer \times \integer$ is a group under componentwise addition. Define $f: \integer \times \integer \to \integer \times \integer$ by

$$f(x, y) = (2 x + 3 y, 7 x - y).$$

(a) Prove that f is a group map.

(b) Prove that $\ker f = \{(0, 0)\}$ .

(a) A direct computation:

$$f[(a, b) + (c, d)] = f(a + c, b + d) = (2 (a + c) + 3 (b + d), 7 (a + c) - (b + d) = (2 a + 2 c + 3 b + 3 d, 7 a + 7 c - b - d) =$$

$$((2 a + 3 b) + (2 c + 3 d), (7 a - b) + (7 c - d) = (2 a + 3 b, 7 a - b) + (2 c + 3 d, 7 c - d) = f(a, b) + f(c, d).$$

Alternatively, note that f can be represented using matrix multiplication:

$$f\left(\left[\matrix{x \cr y \cr}\right]\right) = \left[\matrix{ 2 & 3 \cr 7 & -1 \cr}\right] \left[\matrix{x \cr y \cr}\right].$$

Write

$$A = \left[\matrix{ 2 & 3 \cr 7 & -1 \cr}\right], \quad u = \left[\matrix{a \cr b \cr}\right], \quad v = \left[\matrix{c \cr d \cr}\right].$$

Then by properties of matrix multiplication,

$$f(u + v) = A (u + v) = A u + A v = f(u) + f(v).\quad\halmos$$

(b) Suppose $(x, y) \in \ker f$ . Then

$$f(x, y) = (2 x + 3 y, 7 x - y) = (0, 0).$$

Hence,

$$2 x + 3 y = 0, \quad 7 x - y = 0.$$

Multiply the second equation by 3 and add it to the first equation:

$$\eqalign{ 2 x + 3 y & = 0 \cr 21 x - 3 y & = 0 \cr \noalign{\vskip2pt \hrule \vskip2pt} 23 x & = 0 \cr x & = 0 \cr}$$

Plugging this into $7 x - y = 0$ gives $-y = 0$ , so $y = 0$ . Therefore, $(x, y) = (0, 0)$ . Hence, $\ker f = \{(0, 0)\}$ .

34. (a) List the elements of the subgroup $\langle (3, 7) \rangle$ in $U_8 \times U_{10}$ .

(b) List the elements of the subgroup $\langle 3 \rangle \times \langle 7 \rangle$ in $U_8 \times U_{10}$ .

Note that the operations are multiplication mod 8 in $U_8$ and multiplication mod 10 in $U_{10}$ .

(a) $\langle (3, 7) \rangle$ consists of powers of $(3, 7)$ .

$$\langle (3, 7) \rangle = \{(1, 1), (3, 7), (1, 9), (3, 3)\}.\quad\halmos$$

(b) First,

$$\langle 3 \rangle = \{1, 3\} \quad\hbox{in}\quad U_8.$$

$$\langle 7 \rangle = \{1, 7, 9, 3\} \quad\hbox{in}\quad U_{10}.$$

$\langle 3 \rangle \times \langle 7 \rangle$ consists of pairs where the first component is in $\langle 3 \rangle$ and the second component is in $\langle 7 \rangle$ :

$$\langle 3 \rangle \times \langle 7 \rangle = \{(1, 1), (1, 7), (1, 9), (1, 3), (3, 1), (3, 7), (3, 9), (3, 3)\}.\quad\halmos$$

Note that the answers to (a) and (b) are different!

35. Find a subgroup of order 8 in $\integer_{12} \times \integer_{14}$ . Does this group have any elements of order 8?

Since $8 \notdiv 12$ and $8 \notdiv 14$ , neither $\integer_{12}$ nor $\integer_{14}$ has a subgroup of order 8.

But I can get a subgroup of order 8 by taking the product of a subgroup of order 4 in $\integer_{12}$ and a subgroup of order 2 in $\integer_{14}$ . Thus, $\langle 3 \rangle \times \langle 7 \rangle$ is a subgroup of order 8 in $\integer_{12} \times \integer_{14}$ .

If $(a, b) \in \integer_{12} \times \integer_{14}$ , then the order of $(a, b)$ is $[\ord(a), \ord(b)]$ . But $\ord(a) \mid 12$ , so $\ord(a) = 1, 2, 3, 4, 6, 12$ , and $\ord(b) \mid 14$ , so $\ord(b) = 1, 2, 7, 14$ . No combination of these numbers will give $[\ord(a), \ord(b)] = 8$ . Hence, there are no elements of order 8.

36. (a) List the elements of order 8 in $\integer_8 \times \integer_6$ .

(b) List the elements of order 8 in $\integer_4 \times \integer_6$ .

(a) Let $\ord(x)$ denote the order of x. If $(a, b) \in \integer_8 \times \integer_6$ , then the order of $(a, b)$ is $[\ord(a), \ord(b)]$ . Suppose $[\ord(a), \ord(b)] = 8$ . By Lagrange's theorem, I also have

$$\ord(a) \mid 8 \quad\hbox{and}\quad \ord(b) \mid 6.$$

Thus, $\ord(a) = 1, 2, 4, 8$ and $\ord(b) = 1, 2, 3, 6$ . Of the 16 possible combinations of values, the ones that give $[\ord(a), \ord(b)] = 8$ are

$$\ord(a) = 8 \quad\hbox{and}\quad \ord(b) = 1, 2.$$

The elements of order 8 in $\integer_8$ are 1, 3, 5, and 7.

The elements of order 1 or 2 in $\integer_6$ are 0 and 3.

Thus, the elements of order 8 in $\integer_8 \times \integer_6$ are

$$(1, 0), \quad (3, 0), \quad (5, 0), \quad (7, 0), \quad (1, 3), \quad (3, 3), \quad (5, 3), \quad (7, 3).\quad\halmos$$

(b) Let $\ord(x)$ denote the order of x. If $(a, b) \in \integer_4 \times \integer_6$ , then the order of $(a, b)$ is $[\ord(a), \ord(b)]$ . Suppose $[\ord(a), \ord(b)] = 8$ . By Lagrange's theorem, I also have

$$\ord(a) \mid 4 \quad\hbox{and}\quad \ord(b) \mid 6.$$

Thus, $\ord(a) = 1, 2, 4$ and $\ord(b) = 1, 2, 3, 6$ . Of the 12 possible combinations of values, no combination gives $[\ord(a), \ord(b)] = 8$ . Hence, $\integer_4 \times \integer_6$ has no elements of order 8.

37. Find the primary decomposition and invariant factor decomposition for $\integer_4 \times \integer_6 \times \integer_{75}$ .

The primary decomposition is

$$\integer_4 \times \integer_2 \times \integer_3 \times \integer_3 \times \integer_{25}.$$

$$\matrix{ 2 & 4 \cr 3 & 3 \cr & 25 \cr \noalign{\vskip2pt \hrule \vskip2pt} 2 & 300 \cr}$$

The invariant factor decomposition is $\integer_6 \times \integer_{300}$ .

38. (a) Determine the largest order of an element of $\integer_{10} \times \integer_{15} \times \integer_{40}$ .

(b) Find a specific element of largest order in $\integer_{10} \times \integer_{15} \times \integer_{40}$ .

(a) The largest possible order of an element is

$$[10, 15, 40] = 120.$$

Alternative method: The primary decomposition is

$$\integer_2 \times \integer_5 \times \integer_3 \times \integer_5 \times \integer_8 \times \integer_5.$$

From this, I find that the invariant factor decomposition is

$$\integer_5 \times \integer_{10} \times \integer_{120}.$$

The top factor is $\integer_{120}$ , so the largest order of an element is 120.

(b) $(1, 1, 1)$ is an element of order $[10, 15, 40] = 120$ .

39. $\integer_{2} \times \integer_{10}$ and $\integer_{20}$ are abelian groups of order 20. Explain why they aren't isomorphic.

$\integer_{20}$ has elements of order 20 --- for instance, 1 has order 20.

If $(x,y) \in \integer_{2} \times \integer_{10}$ , then

$$10\cdot (x,y) = (10x, 10y) = (0,0).$$

Therefore, no element of $\integer_{2} \times \integer_{10}$ has order greater than 10.

Therefore, $\integer_{2} \times \integer_{10}$ and $\integer_{20}$ aren't isomorphic.

40. Determine all isomorphism classes of abelian groups of order $2^3 \cdot 3^3$ . For each isomorphism class, give the primary decomposition and the corresponding invariant factor decomposition.

Factor $2^3$ and $3^3$ into prime powers:

$$2^3: \quad 2^3, 2 \cdot 2^2, 2 \cdot 2 \cdot 2$$

$$3^3: \quad 3^3, 3 \cdot 3^2, 3 \cdot 3 \cdot 3$$

The primary decompositions and their corresponding invariant factor decompositions are:

$$\vbox{\offinterlineskip \halign{& \vrule # & \strut \hfil \quad # \quad \hfil \cr \noalign{\hrule} height2pt & \omit & & \omit & \cr & Primary decomposition & & Invariant factor decomposition & \cr height2pt & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & \cr & $\integer_8 \times \integer_{27}$ & & $\integer_{216}$ & \cr height2pt & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & \cr & $\integer_8 \times \integer_3 \times \integer_9$ & & $\integer_3 \times \integer_{72}$ & \cr height2pt & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & \cr & $\integer_8 \times \integer_3 \times \integer_3 \times \integer_3$ & & $\integer_3 \times \integer_3 \times \integer_{24}$ & \cr height2pt & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & \cr & $\integer_2 \times \integer_4 \times \integer_{27}$ & & $\integer_2 \times \integer_{108}$ & \cr height2pt & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & \cr & $\integer_2 \times \integer_4 \times \integer_3 \times \integer_9$ & & $\integer_6 \times \integer_{36}$ & \cr height2pt & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & \cr & $\integer_2 \times \integer_4 \times \integer_3 \times \integer_3 \times \integer_3$ & & $\integer_3 \times \integer_6 \times \integer_{12}$ & \cr height2pt & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & \cr & $\integer_2 \times \integer_2 \times \integer_2 \times \integer_{27}$ & & $\integer_2 \times \integer_2 \times \integer_{54}$ & \cr height2pt & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & \cr & $\integer_2 \times \integer_2 \times \integer_2 \times \integer_3 \times \integer_9$ & & $\integer_2 \times \integer_6 \times \integer_{18}$ & \cr height2pt & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & \cr & $\integer_2 \times \integer_2 \times \integer_2 \times \integer_3 \times \integer_3 \times \integer_3$ & & $\integer_6 \times \integer_6 \times \integer_6$ & \cr height2pt & \omit & & \omit & \cr \noalign{\hrule} }}\quad\halmos $$

41. Suppose G is an abelian group of order 16.

(a) If no element of G has order greater than 2, what are the possible primary decompositions of G?

(b) If G has at least one element of order 8, what are the possible primary decompositions of G?

(a) The primary decompositions for abelian groups of order 16 are

$$\integer_{16}, \quad \integer_2 \times \integer_8, \quad \integer_4 \times \integer_4, \quad \integer_2 \times \integer_2 \times \integer_4, \quad \integer_2 \times \integer_2 \times \integer_2 \times \integer_2.$$

$1 \in \integer_{16}$ has order 16, $(0, 1) \in \integer_2 \times \integer_8$ has order 8, $(1, 1) \in \integer_4 \times \integer_4$ has order 4, and $(0, 0, 1) \in \integer_2 \times \integer_2 \times \integer_4$ has order 4. So if no element of G has order greater than 2, then G cannot be isomorphic to any of the first four groups.

On the other hand, if $(a, b, c, d) \in \integer_2 \times \integer_2 \times \integer_2 \times \integer_2$ , then

$$2(a, b, c, d) = (0, 0, 0, 0).$$

This proves that every element of $\integer_2 \times \integer_2 \times \integer_2 \times \integer_2$ has order at most 2. Therefore, if no element of G has order greater than 2, the primary decomposition of G is

$$G \approx \integer_2 \times \integer_2 \times \integer_2 \times \integer_2.\quad\halmos$$

(b) If $(a, b) \in \integer_4 \times \integer_4$ , then $4(a, b) = (0, 0)$ .

Therefore, elements of $\integer_4 \times \integer_4$ have order at most 4.

If $(a, b, c) \in \integer_2 \times \integer_2 \times \integer_4$ , then

$$4(a, b, c) = (0, 0, 0).$$

Therefore, elements of $\integer_2 \times \integer_2 \times \integer_4$ have order at most 4.

I already showed that elements of $\integer_2 \times \integer_2 \times \integer_2 \times \integer_2$ have order at most 2.

Therefore, if G has at least one element of order 8, G cannot be isomorphic to $\integer_4 \times \integer_4$ , $\integer_2 \times \integer_2 \times \integer_4$ , or $\integer_2 \times \integer_2 \times \integer_2 \times \integer_2$ .

On the other hand, $2 \in \integer_{16}$ has order 8, and $(0,1) \in \integer_2 \times \integer_8$ has order 8. These groups do have elements of order 8.

Hence, if G has at least one element of order 8, the possible primary decompositions of G are

$$\integer_{16} \quad\hbox{or}\quad \integer_2 \times \integer_8.\quad\halmos$$

42. Suppose G is an abelian group of order 1701 and the largest order of an element of G is 63 What are the possible invariant factor decompositions for G?

It would be really tedious to list all the possible invariant factor decompositions for groups of order 1701. However, this isn't necessary.

Note that $\dfrac{1701}{63} = 27$ . The invariant factor decomposition for G has the form

$$\integer_{d_1} \times \integer_{d_2} \times \cdots \times \integer_{d_n} \times \integer_{63}.$$

Here $d_1 \mid d_2 \mid \cdots \mid d_n \mid 63$ and $d_1 d_2 \cdots d_n = 27$ .

The possible factorizations of 27 are $3 \cdot 3 \cdot 3$ , $3 \cdot 9$ , and 27. Now $27 \notdiv 63$ , so the last one is ruled out. The possible invariant factor decompositions are

$$\integer_3 \times \integer_3 \times \integer_3 \times \integer_{63} \quad\hbox{and}\quad \integer_3 \times \integer_9 \times \integer_{63}.\quad\halmos$$

43. (a) Can $\integer_5$ be isomorphic to the direct product of two of its proper subgroups?

(b) Can $\integer_8$ be isomorphic to the direct product of two of its proper subgroups?

(c) Can $S_3$ be isomorphic to the direct product of two of its proper subgroups?

(a) $\integer_5$ does not have any proper subgroups, so it can't be isomorphic to the direct product of two of its proper subgroups.

(b) Suppose $\integer_8$ is isomorphic to $A \times B$ , where A and B are proper subgroups of $\integer_8$ . Then one of A, B has order 2, while the other has order 4. Suppose without loss of generality that $|A| = 2$ and $|B| = 4$ .

Using multiplicative notation, $x^2 = 1$ for all $x \in A$ , while $y^4 = 1$ for all $y \in B$ . Then if $(x, y) \in A \times B$ ,

$$(x, y) ^4 = (x^4, y^4) = (1, 1).$$

Therefore, elements of $A \times B$ have order no greater than 4.

However, $\integer_8$ has elements of order 8 (such as 1).

This contradiction proves that $\integer_8$ can't be isomorphic to the direct product of two of its proper subgroups.

(c) Proper subgroups of $S_3$ have order 2 or 3, so they're isomorphic to $\integer_2$ (order 2) or $\integer_3$ (order 3). Both $\integer_2$ and $\integer_3$ are abelian, and the product of abelian groups is abelian --- but $S_3$ is nonabelian. So $S_3$ can't be isomorphic to the direct product of two of its proper subgroups.

44. Suppose A, B, C, and D are groups, all with the operation denoted by multiplication. Suppose that $f: A \to C$ and $g: B \to D$ are group maps. Define $f \times g: A \times B \to C \times D$ by

$$(f \times g)(a, b) = (f(a), g(b)).$$

(a) Prove that $f \times g$ is a group map.

(b) Prove that

$$\ker (f \times g) = \{(a, b) \in A \times B \mid a \in \ker f \quad\hbox{and}\quad b \in \ker g\}.$$

flushpar (a) Let $(a, b), (c, d) \in A \times B$ . Then

$$(f \times g)\left[(a, b) \cdot (c, d)\right] = (f \times g)(a c, b d) = (f(a c), g(b d)) = (f(a) f(c), g(b) g(d)) =$$

$$(f(a), g(b)) \cdot (f(c), g(d)) = (f \times g)(a, b) \cdot (f \times g)(c, d).$$

Therefore, $f \times g$ is a group map.

(b) Let $(a, b) \in \ker (f \times g)$ . By definition,

$$(f \times g)(a, b) = (1, 1), \quad\hbox{so}\quad (f(a), g(b)) = (1, 1), \quad\hbox{hence}\quad f(a) = 1 \quad\hbox{and}\quad g(b) = 1.$$

$f(a) = 1$ means $a \in \ker f$ and $g(b) = 1$ means $b \in \ker g$ . Therefore,

$$(a, b) \in \{(a, b) \in A \times B \mid a \in \ker f \quad\hbox{and}\quad b \in \ker g\}.$$

Conversely, suppose

$$(a, b) \in \{(a, b) \in A \times B \mid a \in \ker f \quad\hbox{and}\quad b \in \ker g\}.$$

$a \in \ker f$ means $f(a) = 1$ , and $b \in ker g$ means $g(b) = 1$ . Therefore,

$$(f(a), g(b)) = (1, 1), \quad\hbox{so}\quad (f \times g)(a, b) = (1, 1).$$

Hence, $(a, b) \in \ker (f \times g)$ .

Since each of the sets is contained in the other, it follows that

$$\ker (f \times g) = \{(a, b) \in A \times B \mid a \in \ker f \quad\hbox{and}\quad b \in \ker g\}.\quad\halmos$$

45. (a) Explain why $\integer_2 \times \integer_3$ and $\integer_3 \times \integer_2$ are not identical as sets.

(b) Show that if G and H are groups, then $G \times H \approx H \times G$ .

(a) $\integer_2 \times \integer_3$ consists of ordered pairs $(x, y)$ , where $x \in \integer_2$ and $y \in \integer_3$ . $\integer_3 \times \integer_2$ consists of ordered pairs $(x, y)$ , where $x \in \integer_3$ and $y \in \integer_2$ .

Thus, for example, an element $(x, y) \in \integer_2 \times \integer_3$ can't be an element of $\integer_3 \times \integer_2$ : x is an element of $\integer_2$ , but to be in $\integer_3 \times \integer_2$ it should be an element of $\integer_3$ .

(b) Define $f: G \times H \to H \times G$ by

$$f(g, h) = (h, g) \quad\hbox{for}\quad g \in G, \quad h \in H.$$

f is a group map: If $a, c \in G$ and $b, d \in H$ , then

$$f\left((a, b)(c, d)\right) = f\left(a c, b d\right) = \left(b d, a c\right) = (b, a)(d, c) = f(a, b) f(c, d).$$

Define $g: H \times G \to G \times H$ by

$$g(h, g) = (g, h) \quad\hbox{for}\quad g \in G, \quad h \in H.$$

Then

$$f\left[g(h, g)\right] = f(g, h) = (h, g),$$

$$g\left[f(g, h)\right] = g(h, g) = (g, h).$$

Therefore, f and g are inverses. Thus, f is bijective, so f is an isomorphism.

46. (a) Suppose a group has 48 elements. What are the possiblities for the order of a subgroup of G?

(b) A subgroup of a group contains 7 elements. The subgroup has 3 left cosets. What is the order of the group?

(a) By Lagrange's theorem, the order of a subgroup must divide the order of the group. Therefore, a subgroup of a group of order 48 can have 1, 2, 3, 4, 6, 8, 12, 16, 24, or 48 elements.

(b) By Lagrange's theorem, the order of a group equals the order of a subgroup times the index of the subgroup --- i.e. the number of left or right cosets. Therefore, the group has order $7\cdot 3 = 21$ elements.

47. List the elements of the cosets of $\langle 11 \rangle$ in $U_{30}$ .

$$\eqalign{ \langle 11 \rangle & = \{1, 11\} \cr 7 \cdot \langle 11 \rangle & = \{7, 17\} \cr 13 \cdot \langle 11 \rangle & = \{13, 23\} \cr 19 \cdot \langle 11 \rangle & = \{19, 29\} \cr} \quad\halmos$$

48. List the elements of the cosets of $\langle 8 \rangle$ in $\integer_{12}$ .

$$\eqalign{ \langle 8 \rangle & = \{0, 8, 4\} \cr 1 + \langle 8 \rangle & = \{1, 9, 5\} \cr 2 + \langle 8 \rangle & = \{2, 10, 6\} \cr 3 + \langle 8 \rangle & = \{3, 11, 7\} \cr} \quad\halmos$$

49. List the elements of the cosets of $\langle (1, (1\ 3)) \rangle$ in $\integer_3 \times S_3$ .

Remember that the operation is addition mod 3 in the first component and permutation multiplication (right to left) in the second. For example,

$$(0, (1\ 2)) \cdot (2, (1\ 3)) = (0 + 2, (1\ 2)(1\ 3)) = (2, (1\ 3\ 2)).$$

The cosets are

$$\eqalign{ \langle (1, (1\ 3)) \rangle & = \{(0, \id), (1, (1\ 3)), (2, \id), (0, (1\ 3)), (1, \id), (2, (1\ 3))\} \cr (0, (1\ 2) \cdot \langle (1, (1\ 3)) \rangle & = \{(0, (1\ 2)), (1, (1\ 3\ 2)), (2, (1\ 2)), (0, (1\ 3\ 2)), (1, (1\ 2)), (2, (1\ 3\ 2))\} \cr (0, (2\ 3) \cdot \langle (1, (1\ 3)) \rangle & = \{(0, (2\ 3)), (1, (1\ 2\ 3)), (2, (2\ 3)), (0, (1\ 2\ 3)), (1, (2\ 3)), (2, (1\ 2\ 3))\} \cr} \quad\halmos$$

50. (a) List the cosets of the subgroup $4\integer$ of $\integer$ .

(b) What coset of $4\integer$ contains 771?

(a)

$$4\integer = \{\ldots, -8, -4, 0, 4, 8, \ldots\},$$

$$1 + 4\integer = \{\ldots, -7, -3, 1, 5, 9, \ldots\},$$

$$2 + 4\integer = \{\ldots, -6, -2, 2, 6, 10, \ldots\},$$

$$3 + 4\integer = \{\ldots, -5, -1, 3, 7, 11, \ldots\}.\quad\halmos$$

(b) Since $771 = 3 \mod{4}$ , I have $771 \in 3 + 4\integer$ .

We are all special cases. - Albert Camus

Contact information

Bruce Ikenaga's Home Page

Copyright 2020 by Bruce Ikenaga