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. is the set of elements of which are relatively prime to n. It is a group under multiplication mod n. Consider, in particular, the group .

(a) Find the order of .

(b) Find in .

(c) List the elements of the subgroup of .

2. (a) List the elements of the subgroup of generated by 10.

(b) List the elements of the subgroup of

3. (a) Find the order of 48 in .

(b) Find the order of 13 in .

4. (a) Let G be a group, and let . Prove that if and , then n is a multiple of the order of g.

(b) Suppose that G is a group, , and . What are the possibilities for the order of g?

5. (a) Find the order of 142 in .

(b) Find an element n in such that n has order 26 but .

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

(b) is cyclic. List all the generators of .

7. List the elements of all the subgroups of . What elements generate ?

8. (a) List the elements of the subgroup of order 12 in .

(b) Find all the generators of the subgroup of order 12 in .

9. Find a generator for the following subgroup of :

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

11. Consider the integers with the group operation

Taking for granted that this gives a group structure on , prove that is cyclic by exhibiting a generator. Note: The identity for is 4, and .

12. (a) Give an example of a group G and elements , such that x has order 2 and y has order 4, and 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 , such that x has order 2 and y has order 4, and 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 is a subgroup of G. What is the order of ?

Hint: If A is a subgroup of B, then . And is a subgroup of and of .

14. Reduce to a number in the range . Note: 521 is prime.

15. Reduce to a number in the range . Note: 307 is prime.

16. Reduce to a number in the range .

17. Simplify to a number in the range .

18. Reduce to a number in the range . Note: 389 is prime.

19. Prove that .

20. List all the elements of in disjoint cycle notation. For
each element, give its order. (Remember that is the subgroup of
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.)

22. (a) What is the order of the permutation ?

(b) What is the order of the permutation ?

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

(a) Suppose , and let

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

(b) Suppose and . List the permutations in 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) .

(b) .

(c) .

25. Write as a product of transpositions. Is this permutation odd or even?

26. Compute

27. How many elements of send the set into the set ?

28. Let denote the group of permutations of under function composition. Define

Thus, H consists of permutations of the integers which take the positive integers into the positive integers. For example, consider given by

f is bijective, since its inverse is given by . And if , then , so .

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 in

30. (a) Find an element of order 12 in .

(b) Prove that there is no element of order 16 in .

31. List the elements of the subgroup of .

32. is a group under componentwise addition. Let

Prove that H is a subgroup of .

33. is a group under componentwise addition. Define by

(a) Prove that f is a group map.

(b) Prove that .

34. (a) List the elements of the subgroup in .

(b) List the elements of the subgroup in .

35. Find a subgroup of order 8 in . Does this group have any elements of order 8?

36. (a) List the elements of order 8 in .

(b) List the elements of order 8 in .

37. Find the primary decomposition and invariant factor decomposition for .

38. (a) Determine the largest order of an element of .

(b) Find a specific element of largest order in .

39. and are abelian groups of order 20. Explain why they aren't isomorphic.

40. Determine all isomorphism classes of abelian groups of order . 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 be isomorphic to the direct product of two of its proper subgroups?

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

(c) Can 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 and are group maps. Define by

(a) Prove that is a group map.

(b) Prove that

45. (a) Explain why and are not *identical* as sets.

(b) Show that if G and H are groups, then .

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 in .

48. List the elements of the cosets of in .

49. List the elements of the cosets of in .

50. (a) List the cosets of the subgroup of .

(b) What coset of contains 771?

1. is the set of elements of which are relatively prime to n. It is a group under multiplication mod n. Consider, in particular, the group .

(a) Find the order of .

(b) Find in .

(c) List the elements of the subgroup of .

(a)

Therefore, the order of 5 is 4.

(b)

Hence, in .

(c)

Hence,

2. (a) List the elements of the subgroup of generated by 10.

(b) List the elements of the subgroup of .

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

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

3. (a) Find the order of 48 in .

(b) Find the order of 13 in .

(a) Since , the order of 48 is .

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 is cyclic, so I'll do the computation directly. I raise 13 to successive powers (mod 35) until I get 1, the identity in :

Therefore, 13 has order 4 in .

4. (a) Let G be a group, and let . Prove that if and , then n is a multiple of the order of g.

(b) Suppose that G is a group, , and . What are the possibilities for the order of g?

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

Then

Thus, . But m is the smallest positive power of a such that , and . Therefore, r can't be positive, so . This means that , 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 .

(b) Find an element n in such that n has order 26 but .

(a) The order is .

(b) Since the order of n is , I want

Notice that . Therefore, I can ensure that
by taking a multiple of 6 such that k does
*not* have 2 or 13 as a factor. I also want
, so . The easiest way to do this is to take k to be a
prime number greater than 13; I'll use . Thus, .

Now 102 is greater than 78, and , so 102 has order in .

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

(b) is cyclic. List all the generators of .

(a)

(b) 5 generates :

To find the other generator, note that is cyclic of order 6. In , the cyclic group of order 6, the generators are 1 and . So the other generator of must be .

7. List the elements of all the subgroups of . What elements generate ?

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

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 .

(b) Find all the generators of the subgroup of order 12 in .

(a) The subgroup of order 12 in is

(b) Since is cyclic, the subgroup of order 12 is a cyclic group of order 12.

Now is cyclic of order 12, and the generators are the elements relatively prime to 12, namely 1, 5, 7, and 11. But and are isomorphic by the function . So the generators of are

9. Find a generator for the following subgroup of :

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

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

First, if , then

Conversely, note that

Hence,

This shows that .

Therefore, .

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

No element of the form can generate: If , then , and the equality of the second components gives a contradiction. This shows that is not in the subgroup generated by , so .

A similar argument shows that no element of the form can generate.

Assume, then, that is a generator, where . I claim that is not a multiple of . For if , then

Equating the second components, I get , so (since ). But equating the first components now gives

This contradiction shows that is not in the subgroup generated by , so .

Therefore, no element of generates, so is not cyclic.

11. Consider the integers with the group operation

Taking for granted that this gives a group structure on , prove that is cyclic by exhibiting a generator.

Notice that

For , write

The pattern above suggests the formula

Since and , the result is true for .

Assume that . Then

This proves the result for , so the result is true for all by induction.

As , the powers give the numbers .

The identity in is 4, so .

To get the numbers greater than 4, just take inverses. If , then

As , the negative powers give the numbers .

This shows that every element in is a power of 3, so 3 is a generator and is cyclic.

12. (a) Give an example of a group G and elements , such that x has order 2 and y has order 4, and has order 2.

(b) Give an example of a group G and elements , such that x has order 2 and y has order 4, and has order 1.

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

Thus, has order 2:

(b) In , consider the subgroups

Then has order 2 and has order 4. Moreover,

So the intersection has order 1.

Here's a more complicated example.

In , the group of symmetries of a square, let r denote rotation through counterclockwise. Then r generates a subgroup of order 4:

is rotation through , and is rotation through .

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:

Now

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

In this case, the intersection 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 is a subgroup of G. What is the order of ?

is a subgroup of , which is a cyclic group of order 9. Therefore, the order of is 1, 3, or 9.

is a subgroup of , which is a cyclic group of order 16. Therefore, the order of is 1, 2, 4, 8, or 16.

The only way of satisfying both of these conditions is if the order of is 1.

14. Reduce to a number in the range . Note: 521 is prime.

By Fermat's Theorem,

Let . Then

Note: In general, to solve an equation like " ", I'd need to find using the Extended Euclidean algorithm. But I happened to notice that 261 was half of , so I had a shortcut.

15. Reduce to a number in the range . Note: 307 is prime.

By Fermat's theorem, . So

Hence, .

Therefore,

16. Reduce to a number in the range .

Since , I have

17. Simplify to a number in the range .

By Wilson's theorem, . So

It follows that , so

18. Reduce to a number in the range . Note: 389 is prime.

Let . Then

19. Prove that .

Since , Fermat's Theorem gives . Since , it follows that

Similarly, , so Fermat's Theorem gives . Since , it follows that

Since is congruent to 1 mod 101 and mod 103, and since , it follows that

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

is the subgroup of even permutations in . This is half of : twelve elements. To list them, note that if a, b, and c are distinct, is even, and these 3-cycles have order 3. And if the pairs and are distinct, then 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 .

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

Right-to-left:

22. (a) What is the order of the permutation ?

(b) What is the order of the permutation ?

(a) has order 4 and 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: .

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

Thus, , and the permutation has order 6.

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

(a) Suppose , and let

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

(b) Suppose and . List the permutations in which send Y to itself.

(a) First, , so .

Suppose , so and . Then

Hence, .

Finally, suppose , so . Then

Therefore, .

Hence, H is a subgroup of .

(b) The permutations in which send Y to itself are , , , and .

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

(a) .

(b) .

(c) .

(a)

(b)

(c) First, .

Since has order 3,

25. Write as a product of transpositions. Is this permutation odd or even?

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

26. Compute

You can do this directly by multiplying out the permutations.

Alternatively, you can use the following fact about the conjugate of a cycle by a permutation: If and are permutations and is written as a product of cycles, then can be found by applying to the elements of the cycles in .

That is, just apply to each of the numbers in , then to each of the numbers in . This gives

27. How many elements of send the set into the set ?

Let be a permutation which sends the set into the set . Since permutations are injective, different elements must go to different places. Thus, either

That is, there are two possibilities.

also permutes the elements among themselves. There are such permutations.

Therefore, there are a total of elements of which send the set into the set .

28. Let denote the group of permutations of under function composition. Define

(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 , so and . Then

Therefore, .

Since , it follows that .

Consider the function given by

f is bijective: Its inverse is . Thus, . Moreover, if , then , so

Hence, , and so . Thus, .

However, , since .

Thus, H is not a subgroup of .

29. Find the order of in .

The order of 44 in is

The order of 36 in is

Hence, the order of in is .

30. (a) Find an element of order 12 in .

(b) Prove that there is no element of order 16 in .

(a) 2 has order 3 in and 2 has order 4 in , so has order in .

(b) Let . Suppose a has order m in and b has order n in . The order of is .

Assume that .

The divisors of 6 and 8 are

Thus, and .

If or , then , which is a contradiction. Hence, or .

If , then

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

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

In no case do I have .

This final contradiction shows that no element of has order 16.

31. List the elements of the subgroup of .

32. is a group under componentwise addition. Let

Prove that H is a subgroup of .

Since , it follows that .

Suppose . Then

Hence,

Suppose . Then

Hence,

Therefore,

33. is a group under componentwise addition. Define by

(a) Prove that f is a group map.

(b) Prove that .

(a) A direct computation:

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

Write

Then by properties of matrix multiplication,

(b) Suppose . Then

Hence,

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

Plugging this into gives , so . Therefore, . Hence, .

34. (a) List the elements of the subgroup in .

(b) List the elements of the subgroup in .

Note that the operations are multiplication mod 8 in and multiplication mod 10 in .

(a) consists of powers of .

(b) First,

consists of pairs where the first component is in and the second component is in :

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

35. Find a subgroup of order 8 in . Does this group have any elements of order 8?

Since and , neither nor 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 and a subgroup of order 2 in . Thus, is a subgroup of order 8 in .

If , then the order of is . But , so , and , so . No combination of these numbers will give . Hence, there are no elements of order 8.

36. (a) List the elements of order 8 in .

(b) List the elements of order 8 in .

(a) Let denote the order of x. If , then the order of is . Suppose . By Lagrange's theorem, I also have

Thus, and . Of the 16 possible combinations of values, the ones that give are

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

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

Thus, the elements of order 8 in are

(b) Let denote the order of x. If , then the order of is . Suppose . By Lagrange's theorem, I also have

Thus, and . Of the 12 possible combinations of values, no combination gives . Hence, has no elements of order 8.

37. Find the primary decomposition and invariant factor decomposition for .

The primary decomposition is

The invariant factor decomposition is .

38. (a) Determine the largest order of an element of .

(b) Find a specific element of largest order in .

(a) The largest possible order of an element is

Alternative method: The primary decomposition is

From this, I find that the invariant factor decomposition is

The top factor is , so the largest order of an element is 120.

(b) is an element of order .

39. and are abelian groups of order 20. Explain why they aren't isomorphic.

has elements of order 20 --- for instance, 1 has order 20.

If , then

Therefore, no element of has order greater than 10.

Therefore, and aren't isomorphic.

40. Determine all isomorphism classes of abelian groups of order . For each isomorphism class, give the primary decomposition and the corresponding invariant factor decomposition.

Factor and into prime powers:

The primary decompositions and their corresponding invariant factor decompositions are:

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

has order 16, has order 8, has order 4, and 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 , then

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

(b) If , then .

Therefore, elements of have order at most 4.

If , then

Therefore, elements of have order at most 4.

I already showed that elements of have order at most 2.

Therefore, if G has at least one element of order 8, G cannot be isomorphic to , , or .

On the other hand, has order 8, and 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

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 . The invariant factor decomposition for G has the form

Here and .

The possible factorizations of 27 are , , and 27. Now , so the last one is ruled out. The possible invariant factor decompositions are

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

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

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

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

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

Using multiplicative notation, for all , while for all . Then if ,

Therefore, elements of have order no greater than 4.

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

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

(c) Proper subgroups of have order 2 or 3, so they're isomorphic to (order 2) or (order 3). Both and are abelian, and the product of abelian groups is abelian --- but is nonabelian. So 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 and are group maps. Define by

(a) Prove that is a group map.

(b) Prove that

flushpar (a) Let . Then

Therefore, is a group map.

(b) Let . By definition,

means and means . Therefore,

Conversely, suppose

means , and means . Therefore,

Hence, .

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

45. (a) Explain why and are not *identical* as sets.

(b) Show that if G and H are groups, then .

(a) consists of ordered pairs , where and . consists of ordered pairs , where and .

Thus, for example, an element can't be an element of : x is an element of , but to be in it should be an element of .

(b) Define by

f is a group map: If and , then

Define by

Then

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 elements.

47. List the elements of the cosets of in .

48. List the elements of the cosets of in .

49. List the elements of the cosets of in .

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

The cosets are

50. (a) List the cosets of the subgroup of .

(b) What coset of contains 771?

(a)

(b) Since , I have .

*We are all special cases.* - *Albert Camus*

Copyright 2020 by Bruce Ikenaga