Math 345

These problems are provided to help you study. The presence of a problem on this sheet does not imply that there will be a similar problem on the test, and the absence of a topic from this sheet does not imply that the topic will not appear on the test.

1. A binary operation is defined on by

(a) Prove or disprove: is associative.

(b) Prove or disprove: is commutative.

(c) Prove or disprove: has an identity element.

2. Use the associative law (for 3 elements at a time) to show that if G is a group and , then

3. Let p be a prime number.

(a) How many elements of have multiplicative inverses?

(b) How many elements of have multiplicative inverses?

4. For each set below, check the axioms for a group. If an axiom is violated, give a specific counterexample.

(a) The set under multiplication mod 10.

(b) The set of matrices with real entries under matrix multiplication.

(c) The set of positive integers under multiplication.

(d) The set of integers under the operation .

(e) The set of rational numbers under division.

(f) The following set of matrices under matrix addition:

(g) The set of all pairs of real numbers , where , under the operation

5. Describe the symmetries of each of the following figures.

6. Let G be a group and let . Simplify the following expressions as much as possible:

(a)

(b) .

(c) .

(d) .

7. Let G be a group and let . Solve the following equation for x:

8. Let G be a group and let . Solve the following equation for x:

9. Let a and b be elements of a group G, with . Suppose that the integers m and n are relatively prime. Prove that either or .

Hint: Use proof by contradiction. Suppose that and m and n are relatively prime. Assume the negation of the conclusion (what is the negation of " "?) and derive a contradiction. To do this, use and a fact about linear combinations.

10. (a) Give an example of a finite nonabelian group.

(b) Give an example of an infinite group which is not countable.

11. Let G be a group, let , and suppose that . Prove that for all ,

12. (a) Find the inverse of in the group .

(b) Explain why is *not* a group under
addition.

13. In each case, a group and a subset of the group are given. Check each axiom for a subgroup as applied to the subset. If the axiom holds, prove it. If the axiom does not hold, give a specific counterexample.

(a) The subset of the group of real numbers under addition.

(b) The following subset of :

(c) The subset J of the group under vector addition consisting of vectors which satisfy .

(d) The subset in an abelian group G.

(e) The subset . ( is a group under component-wise addition [i.e. vector addition].)

(f) The subset , where is a fixed matrix and 0 denotes the zero matrix.

14. Suppose that G is a group, H is a subgroup of G, and . Let

Prove that is a subgroup of G.

15. Suppose H and K are subgroups of a group G, and suppose that

Define

Prove that is a subgroup of G.

16. Suppose G is a group with operation and H is a group with operation . What equation must be true for a function to be a group map?

17. Consider the following function :

Is f a group homomorphism?

18. In each case, determine whether the function is a homomorphism.

(a) is the group of polynomials with real coefficients under polynomial addition and is defined by

(So, for example, if , then .)

(b) is defined by

(c) is defined by

(Here is a group under component-wise addition [i.e. "vector addition"], so .)

(d) is the determinant function, is the group of invertible real matrices under matrix multiplication, and is the group of nonzero real numbers under multiplication.

(e) is defined by

19. The function defined by is a group map.

(a) Find .

(b) Find .

(c) Find .

Note: Remember that is the set of elements which f takes to 6. What elements produce 6 as an output when they're plugged into f?

20. Define by

( is the group of nonzero reals under multiplication.)

(a) Prove that f is a group map.

(b) Find and .

21. Define by . Is f a group map?

22. Let G and H be groups, and let be a group map. Let . Prove that if g has finite order, then the order of divides the order of g.

23. is a group under the operation

Define by

Show that f is an isomorphism.

24. Prove that if is an invertible group map, then is a group map. (Thus, if f is an isomorphism, then its inverse is as well.)

25. Suppose n and x are integers, ,

Prove that or .

26. Suppose that n and x are integers, n is odd,

Prove that .

27. Find the greatest common divisor of 3462 and 118 and write it as a linear combination of 3462 and 118 with integer coefficients.

28. Use the Extended Euclidean Algorithm to find in .

29. Prove that if m is an integer, then or 2. Give specific values of m which show that both cases can occur.

30. Prove that if , then .

31. If two integers differ by 1000, can they both be divisible by 7?

32. Find the greatest common divisor and the least common multiple of and , where p, q, and r are distinct primes.

33. If p, q, and r are distinct prime numbers, how many positive divisors does have?

34. (a) For what integers n is prime?

(b) Calvin Butterball says: "Since doesn't factor, is always prime." Is Calvin correct?

35. Suppose and . Prove that .

36. Suppose x and n are positive integers. Prove that

37. Prove that if , then

38. Prove that there is no integer x such that .

39. Solve the equation .

40. Compute .

41. Recall that

Suppose p is an odd prime. Compute

42. Prove that if , then is not divisible by 7.

43. Prove that there are no integers m and n such that .

44. Solve the following modular equation and simplify your answer to a number in the range .

45. (a) Prove that the following equation has no solutions:

(b) Bonzo McTavish says that the following equation has no solutions:

Bonzo says: "In the last problem, 6 and 12 weren't relatively prime, so you couldn't find and that's why the equation had no solutions. In this problem, 2 and 10 aren't relatively prime, so this equation has no solutions, either."

Show that Bonzo is incorrect.

1. A binary operation is defined on by

(a) Prove or disprove: is associative.

(b) Prove or disprove: is commutative.

(c) Prove or disprove: has an identity element.

(a)

Since , it follows that is not associative.

(b) Let . Then

Hence, is commutative.

(c) Suppose e is an identity for . Then in particular, . But

Hence, . This contradiction shows that there is no identity element for .

2. Use the associative law (for 3 elements at a time) to show that if G is a group and , then

(The associative law (for 3 elements at a time) can be used to show that "any two groupings" of a product are equal --- but usually, this kind of verification is omitted as being obvious and tedious. But you should understand by example how you could get from one such grouping to another by regrouping 3 elements at a time.

3. Let p be a prime number.

(a) How many elements of have multiplicative inverses?

(b) How many elements of have multiplicative inverses?

(a) The elements in which have multiplicative inverses are the elements which are relatively prime to p. Since p is prime, 1, 2, ..., are all relatively prime to p. Therefore, these elements of have multiplicative inverses.

(b) The elements in which have multiplicative inverses
are the elements which are relatively prime to . I'll count the
number of elements which are *not* relatively prime to and
subtract this from , the number of elements in .

If is *not* relatively prime to ,
then it must have a common factor with other than 1. The only
factors of other than 1 are p and , and both of these
are divisible by the prime p. Thus, is
*not* relatively prime to if and only if it's divisible by
p.

What elements of are divisible by p? Here are the multiples of p:

There are p of them; that is, there are p elements of which are *not* relatively prime to .
Hence, there are elements which are relatively prime to ---
and therefore, elements which have multiplicative
inverses.

Here's a specific example. Suppose . In , the elements which are relatively prime to 3 are

There are 6 of them, and .

4. For each set below, check the axioms for a group. If an axiom is violated, give a specific counterexample.

(a) The set under multiplication mod 10.

(b) The set of matrices with real entries under matrix multiplication.

(c) The set of positive integers under multiplication.

(d) The set of integers under the operation .

(e) The set of rational numbers under division.

(f) The following set of matrices under matrix addition:

(g) The set of all pairs of real numbers , where , under the operation

(a) Here's the multiplication table:

The table shows that set is closed under the operation. Multiplication of integers is associative, so this multiplication is associative. The element 1 is an identity for the operation. Finally, every element has an inverse: , , , and .

Therefore, the set is a group under the operation.

(b) The set is closed under the operation, and matrix multiplication is associative. The matrix is an identity element for matrix multiplication.

However, not every element has a multiplicative inverse. From linear algebra, you know that a matrix is invertible if and only if its determinant is nonzero. So, for example, does not have a multiplicative inverse, because its determinant is 0.

The set is *not* a group under matrix multiplication.

As an aside, this is why when people refer to the *group* of
all matrices, they *can't* mean the operation to
be *multiplication*. They probably mean the operation to be
matrix *addition* --- and you can check that this set
*is* a group under matrix addition.

In the same way, when someone refers to "the group of
integers", the operation *can't* be multiplication, and
most likely is addition.

(c) The set of positive integers is closed under multiplication, multiplication of integers is associative, and the positive integer 1 is an identity element for multiplication.

However, most positive integers do not have multiplicative inverses. For example, there is no positive integer x such that .

The set is *not* a group under multiplication.

(d) If x and y are integers, so is . The set is closed under the operation.

Let . Then

These are not equal in general. In particular, note that

Thus, . The operation is not associative.

I'll work backwards to guess an identity for the operation. If e is an identity for , then in particular . This means that

But this equation has no solutions in . Hence, the operation can't have an identity element.

Since there is no identity element, I can't consider the existence of inverses.

is not a group under .

(e) Division is not a binary operation on the set of rational
numbers, because it isn't defined for *all* pairs of
rationals. For example, you can't divide 42 by 0. Therefore, this
does not give a group structure on .

(f) If you add two elements of G, you get another element of G:

Therefore, matrix addition is a binary operation on G.

I'll take for granted that matrix addition is associative.

The identity for matrix addition is , and this is an element of G.

Finally, if , its additive inverse is also in G:

Therefore, G is a group under matrix addition.

(g) If a, b, c, and d are nonzero real numbers, then so are and . Therefore, the definition gives a binary operation on the set.

I have

Therefore, the operation is associative.

I also have

Therefore, is the identity element for the operation.

If is in the set, then . Hence, and are defined. I have

Hence, .

Therefore, the set is a group under the operation.

5. Describe the symmetries of each of the following figures.

Figure (a) has four symmetries: The identity, rotations through , and reflections across lines bisecting the figure vertically and horizontally.

Figure (b) has two symmetries: The identity and reflection across the line which bisects the figure vertically.

Figure (c) has only the identity symmetry.

6. Let G be a group and let . Simplify the following expressions as much as possible:

(a)

(b) .

(c) .

(d) .

(a)

(b)

(c)

(d)

7. Let G be a group and let . Solve the following equation for x:

8. Let G be a group and let . Solve the following equation for x:

9. Let a and b be elements of a group G, with . Suppose that the integers m and n are relatively prime. Prove that either or .

Suppose on the contrary that , but both and . Since , there are integers s and t such that

Then

Likewise,

So

This contradicts .

Hence,either or .

10. (a) Give an example of a finite nonabelian group.

(b) Give an example of an infinite group which is not countable.

(a) , the group of symmetries of an equilateral triangle, is a nonabelian group of order 6.

(b) , the group of real numbers under addition, is an infinite group of uncountable cardinality.

11. Let G be a group, let , and suppose that . Prove that for all ,

I'll use induction on n. For , the result says , which is true by assumption.

Suppose that , and suppose that the result is true for :

I need to prove the result for n. I have

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

12. (a) Find the inverse of in the group .

(b) Explain why is *not* a group under
addition.

(a)

(b) is not closed under addition. For example,

13. In each case, a group and a subset of the group are given. Check each axiom for a subgroup as applied to the subset. If the axiom holds, prove it. If the axiom does not hold, give a specific counterexample.

(a) The subset of the group of real numbers under addition.

(b) The following subset of :

(c) The subset J of the group under vector addition consisting of vectors which satisfy .

(d) The subset in an abelian group G.

(e) The subset . ( is a group under component-wise addition [i.e. vector addition].)

(f) The subset , where is a fixed matrix and 0 denotes the zero matrix.

(a) Elements of the subset have the form , where n is an integer.

If m and n are integers, then

Therefore, H is closed under the group operation.

, so the identity element of is contained in H.

Finally, if , its additive inverse is also in H.

Hence, H is a subgroup of .

(b) Suppose , so and . Their product is

Hence, the product is in K. Therefore, K is closed under the operation.

The identity matrix of is in K, since .

If , its inverse is

Now , so . Hence, the inverse is in K.

Therefore, K is a subgroup of .

(c) J is not closed under vector addition. is in the set, since , and is in the set, since . But since ,

The identity vector is in J, since .

The vector is in the set, since . However, its additive inverse is not in the set, since .

J is not a subgroup of .

(d) An element is in H if it squares to the identity.

Suppose . This means that and . I want to show that . I'll square it and see if I get 1:

(The second equality used the fact that G is abelian.) This proves that , so H is closed under the operation.

, so .

Finally, suppose , so . I want to show that . I'll square it and see if I get 1:

Therefore, , and H is closed under taking inverses.

Hence, H is a subgroup of G.

(e) Let . I have to show that

Since , I have

So

Therefore, .

Since , it follows that .

Finally, suppose . I have to show that

Since , I have . So

Therefore, .

Hence, P is a subgroup of .

(f) Let . I want to show that . Since , I have

Hence,

Therefore, .

The identity for matrix addition is the zero matrix 0. Since , it follows that .

Finally, let . I need to show that . Since , I have . Therefore,

(In the first equality, I'm multiplying both sides of by the * numbers* -1 and -1.)
Thus, .

Hence, K is a subgroup of .

14. Suppose that G is a group, H is a subgroup of G, and . Let

Prove that is a subgroup of G.

consists of all elements of the form .

Let , where . Then

Since --- H is a subgroup, so it's closed under products --- it follows that . Therefore, is closed under products.

Since , . But , so . Thus, contains the identity.

Suppose , where . The inverse is

, since H is a subgroup (and therefore closed under taking inverses). Therefore, , and is closed under taking inverses.

Therefore, is a subgroup of G.

15. Suppose H and K are subgroups of a group G, and suppose that

Define

Prove that is a subgroup of G.

Let and . and are two typical elements of ; I must show that their product is in . But by assumption, anything in H commutes with anything in K. So , and

Since and , .

Let and . Since and commute, I have

Therefore, is a subgroup of G.

16. Suppose G is a group with operation and H is a group with operation . What equation must be true for a function to be a group map?

17. Consider the following function :

Is f a group homomorphism?

f is not a homomorphism! For instance,

Beware of assuming that a simple-looking function must be a group map!

18. In each case, determine whether the function is a homomorphism.

(a) is the group of polynomials with real coefficients under polynomial addition and is defined by

(b) is defined by

(c) is defined by

(Here is a group under component-wise addition [i.e. "vector addition"], so .)

(d) is the determinant function, is the group of invertible real matrices under matrix multiplication, and is the group of nonzero real numbers under multiplication.

(e) is defined by

(a) If and are polynomials, then

Therefore, , so g is a homomorphism.

Note that I could have used any number in place of 1.

(b) It's often useful to check whether the function takes the
identity to the identity; if it *doesn't*, then the function
is not a homomorphism.

In this case, , so h takes the identity to the identity. However, this doesn't prove that h is a homomorphism.

In fact,

Therefore, , so h is *not* a
homomorphism.

(c) Let . Then

Therefore, is a group map.

(d) Let . From linear algebra, the determinant of a product is the product of the determinants, so

Hence, is a group map.

(e) I have

Since , it follows that f is not a group map.

19. The function defined by is a group map.

(a) Find .

(b) Find .

(c) Find .

(a) if and only if . But is equivalent to , or . Thus,

(b)

(c) is equivalent to , or . This is equivalent to , or . Since the elements divisible by 4 are the elements of , the last equation says that the elements of are obtained by adding 2 to the elements of . Thus,

20. Define by

( is the group of nonzero reals under multiplication.)

(a) Prove that f is a group map.

(b) Find and .

(a) Let . Then (since is abelian)

Therefore, f is a group map.

(b) The identity of is 1. So

If , then . Thus, is always a positive real number, and .

Conversely, if y is a positive real number, then

Therefore, . Hence, .

21. Define by . Is f a group map?

I have

Since , it follows that f is not a group map.

22. Let G and H be groups, and let be a group map. Let . Prove that if g has finite order, then the order of divides the order of g.

Suppose that g has order n. Then , so

Hence, the order of must divide n.

23. is a group under the operation

Define by

Show that f is an isomorphism.

Let . Then

Hence, , and so f is a group map.

Define by

Then

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

24. Prove that if is an invertible group map, then is a group map. (Thus, if f is an isomorphism, then its inverse is as well.)

Let . Since f and are inverses, for all . In particular,

Using the fact that f is a group map and the inverse property again, I have

Therefore,

But f is invertible, so it's injective. This means that implies . So the last equation above gives

Thus, is a group map.

25. Suppose n and x are integers, ,

Prove that or .

The idea is to make a linear combination of and where the x's cancel:

Since n is a positive integer dividing 7, it follows that or .

Using and , you can see that both cases could occur.

26. Suppose that n and x are integers, n is odd,

Prove that .

n divides and , so

But n is odd, so .

27. Find the greatest common divisor of 3462 and 118 and write it as a linear combination of 3462 and 118 with integer coefficients.

The GCD of 3462 and 118 is 2, and

28. Use the Extended Euclidean Algorithm to find in .

Hence, in .

29. Prove that if m is an integer, then or 2. Give specific values of m which show that both cases can occur.

Note that

Now and , so

But the only positive integers which divide 2 are 1 and 2, so or 2.

If , , , and .

If , , , and .

Therefore, both cases can occur.

30. Prove that if , then .

Since and , I can write

I want to show that . There are integers such that

Then

Hence, .

31. If two integers differ by 1000, can they both be divisible by 7?

Suppose m and n are both divisible by 7, and . Since and , I have . This is a contradiction, since . Therefore, two integers that differ by 1000 cannot both be divisible by 7.

32. Find the greatest common divisor and the least common multiple of and , where p, q, and r are distinct primes.

To find the greatest common divisor, take the *smallest* power
of each prime that occurs in *both numbers*:

To find the least common multiple, take the *largest* power of
each prime that occurs in *either number*:

33. If p, q, and r are distinct prime numbers, how many positive divisors does have?

A positive divisor of must have the primes p, q, and r as factors. For each such divisor, either it has p as a factor or it doesn't. This gives two choices. The same is true for q and r. Hence, there are a total of choices, and 8 positive divisors.

34. (a) For what integers n is prime?

(b) Calvin Butterball says: "Since doesn't factor, is always prime." Is Calvin correct?

(a) Suppose , where p is prime. Then , and there are four cases.

* Case 1:* and .

gives , so . This is a contradiction, since 0 isn't prime.

* Case 2:* and .

gives , so , and . This works, since 2 is prime.

* Case 3:* and .

gives , so . This works, since 2 is prime.

* Case 4:* and .

gives , so , and . This is a contradiction, since 0 isn't prime.

Thus, is prime for and .

(b) Calvin is wrong. For example, if , , which is not prime.

35. Suppose and . Prove that .

There are integers w, x, y, and z such that

Then

Since and , it follows that .

36. Suppose x and n are positive integers. Prove that

First, I have

So

Consider the polynomial . Plugging in gives

Thus, is a root of , so by the Root Theorem, must be a factor. So for some polynomial , I have

Thus,

Hence, .

37. Prove that if , then

For , I have

The result is true for .

Assume that the result is true for n:

I want to prove the result for :

Start with the left side of this equation. Using the induction hypothesis, I have

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

38. Prove that there is no integer x such that .

Suppose that . Note that and . Multiply by 7:

This contradiction proves that there is no such x.

39. Solve the equation .

Subtracting 63 from both sides gives . Note that ; I'll find the multiplicative inverse of 34 mod 225.

The table gives

Multiply by -86:

40. Compute .

If , then , so . So

However, , , , and all contain 2 and 4 as
* separate* factors, so they're each divisible by
8, and hence they're each congruent to 0 mod 8. So now

41. Recall that

Suppose p is an odd prime. Compute

Consider

For , there is a factor of p in the numerator, but no factor of p in the denominator. Moreover, since p is prime, I can't have two factors a and b in the denominator whose product is p. Hence,

It follows that

42. Prove that if , then is not divisible by 7.

Every integer n is congruent mod 7 to one of 0, 1, 2, 3, 4, 5, or 6. So I just need to consider these 7 cases:

For all n, I have . Hence, if , then is not divisible by 7.

43. Prove that there are no integers m and n such that .

Suppose there is a solution , so . Reduce the equation mod 4 to obtain

Construct a table of squares mod 4:

The table shows that 3 is not a square mod 4. This contradiction shows that the original equation has no solutions.

44. Solve the following modular equation and simplify your answer to a number in the range .

Use the Extended Euclidean algorithm to find .

Thus,

Hence, . Multiplying by -3 and simplifying, I obtain

45. (a) Prove that the following equation has no solutions:

(b) Bonzo McTavish says that the following equation has no solutions:

Bonzo says: "In the last problem, 6 and 12 weren't relatively prime, so you couldn't find and that's why the equation had no solutions. In this problem, 2 and 10 aren't relatively prime, so this equation has no solutions, either."

Show that Bonzo is incorrect.

(a) Suppose x satisfies . Then

This contradiction shows that the original equation has no solutions.

(b) An easy way to check for solutions is to make a table:

As the table shows, and are solutions, so Bonzo is incorrect.

He's right that is undefined, so you can't
multiply both sides by . However, that only shows that you can't
solve the equation * in that particular way*.

*No person is a friend who demands your silence, or denies your
right to grow.* - *Alice Walker*

Copyright 2020 by Bruce Ikenaga