Review Sheet for Test 1

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 $\integer$ by

$$a \ast b = a^2 + b^2.$$

(a) Prove or disprove: $\ast$ is associative.

(b) Prove or disprove: $\ast$ is commutative.

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

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

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

3. Let p be a prime number.

(a) How many elements of $\integer_p$ have multiplicative inverses?

(b) How many elements of $\integer_{p^2}$ 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 $\{1, 3, 7, 9\}$ under multiplication mod 10.

(b) The set of $2 \times 2$ matrices with real entries under matrix multiplication.

(c) The set of positive integers under multiplication.

(d) The set of integers under the operation $x \ast y = x y + 1$ .

(e) The set of rational numbers under division.

(f) The following set of $2\times 2$ matrices under matrix addition:

$$G = \left\{\left[\matrix{x & x \cr y & y \cr}\right] \Bigm| x, y \in \integer\right\}.$$

(g) The set of all pairs of real numbers $(a, b)$ , where $a, b \ne 0$ , under the operation

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

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

$$\matrix{ \hbox{\epsfxsize=1in \epsffile{rev1-1.eps}} & \hbox{\hskip0.5in} & \hbox{\epsfxsize=1in \epsffile{rev1-2.eps}} & \hbox{\hskip0.5in} & \hbox{\epsfysize=1in \epsffile{rev1-3.eps}} \cr \noalign{\vskip8pt} \hbox{(a)} & \hbox{\hskip0.5in} & \hbox{(b)} & \hbox{\hskip0.5in} & \hbox{(c)} \cr}$$

6. Let G be a group and let $a, b, c \in G$ . Simplify the following expressions as much as possible:

(a) $a^{-1} (a b^3)^2 b^{-4}$

(b) $b (a^{-1} b)^{-2} a^{-1}$ .

(c) $(a b^2)^{-1} (b a^2)^{-1}$ .

(d) $(a b c)^2 c^{-1} b^{-1} a^{-5}$ .

7. Let G be a group and let $a, b, x \in G$ . Solve the following equation for x:

$$(a b^{-2})^{-1} x a^{-1} b = b^2 a^{-2} b^2.$$

8. Let G be a group and let $a, b, x \in G$ . Solve the following equation for x:

$$a^2 b^{-1} x (a b)^2 = a^3 b^{-3} a b a^2 b.$$

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

Hint: Use proof by contradiction. Suppose that $a \ne b$ and m and n are relatively prime. Assume the negation of the conclusion (what is the negation of "$P \lor Q$ "?) and derive a contradiction. To do this, use $(m, n) = 1$ 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 $a, b \in G$ , and suppose that $a b = b a$ . Prove that for all $n \ge 1$ ,

$$a b^n = b^n a.$$

12. (a) Find the inverse of $\left[\matrix{2 & 6 \cr 1 & 5 \cr}\right]$ in the group $GL(2, \integer_7)$ .

(b) Explain why $GL(2, \integer_7)$ 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 $H = \{\ldots, -3 \sqrt{2}, -2 \sqrt{2}, -\sqrt{2}, 0, \sqrt{2}, 2 \sqrt{2}, 3 \sqrt{2}, \ldots\}$ of the group $\real$ of real numbers under addition.

(b) The following subset of $GL(2, \real)$ :

$$K = \left\{\left[\matrix{a & 0 \cr 0 & d \cr}\right] \Bigm| a d = 1\right\}.$$

(c) The subset J of the group $\real^2$ under vector addition consisting of vectors $(a, b)$ which satisfy $a = b^2$ .

(d) The subset $H = \{x \in G \mid x^2 = 1\}$ in an abelian group G.

(e) The subset $P = \{(x, y, z) \in \integer^3 \mid 3 x + 4 y = 5 z\}$ . ($\integer^3$ is a group under component-wise addition [i.e. vector addition].)

(f) The subset $K = \{A \in M(2, \real) \mid A B A = 0\}$ , where $B \in M(2, \real)$ is a fixed matrix and 0 denotes the $2 \times 2$ zero matrix.

14. Suppose that G is a group, H is a subgroup of G, and $g \in G$ . Let

$$g H g^{-1} = \{g h g^{-1} \mid h \in H\}.$$

Prove that $g H g^{-1}$ is a subgroup of G.

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

$$h k = k h \quad\hbox{for all}\quad h \in H \quad\hbox{and}\quad k \in K.$$

Define

$$H K = \{h k \mid h \in H \quad\hbox{and}\quad k \in K\}.$$

Prove that $H K$ is a subgroup of G.

16. Suppose G is a group with operation $\ast$ and H is a group with operation $\odot$ . What equation must be true for a function $f: G \to H$ to be a group map?

17. Consider the following function $f: \integer_3 \to \integer_4$ :

$$f(0) = 0, \quad f(1) = 1, \quad f(2) = 2.$$

Is f a group homomorphism?

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

(a) $\real[x]$ is the group of polynomials with real coefficients under polynomial addition and $g: \real[x] \to (\real, +)$ is defined by

$$g\left(\phi(x)\right) = \phi(1).$$

(So, for example, if $\phi(x) = x^2 - 4 x + 7$ , then $g\left(\phi(x)\right) = 1^2 - 4 \cdot 1 + 7 = 4$ .)

(b) $h: (\integer, +) \to (\integer, +)$ is defined by

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

(c) $\phi: \integer \times \integer \to (\integer, +)$ is defined by

$$\phi(x, y) = 2 x + 3 y.$$

(Here $\integer \times \integer$ is a group under component-wise addition [i.e. "vector addition"], so $(a, b) + (c, d) = (a + c, b + d)$ .)

(d) $\det: GL(n, \real) \to (\real^*, \cdot)$ is the determinant function, $GL(n, \real)$ is the group of invertible $n \times n$ real matrices under matrix multiplication, and $\real^*$ is the group of nonzero real numbers under multiplication.

(e) $f: (\real^*, \cdot) \to (\real, +)$ is defined by

$$f(x) = x^2 - 1.$$

19. The function $f: \integer_{12} \to \integer_{12}$ defined by $f(x) = 3 x \mod{12}$ is a group map.

(a) Find $\ker f$ .

(b) Find $\im f$ .

(c) Find $f^{-1}(\{6\})$ .

Note: Remember that $f^{-1}(\{6\})$ 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 $f: \real^* \to \real^*$ by

$$f(x) = x^2.$$

($\real^*$ is the group of nonzero reals under multiplication.)

(a) Prove that f is a group map.

(b) Find $\ker f$ and $\im f$ .

21. Define $f: \integer_3 \to \integer_8$ by $f(x) = 5 x \mod{8}$ . Is f a group map?

22. Let G and H be groups, and let $\phi: G \to H$ be a group map. Let $g \in G$ . Prove that if g has finite order, then the order of $\phi(g)$ divides the order of g.

23. $\real$ is a group under the operation

$$a \ast b = a + b - 2.$$

Define $f: (\real, +) \to (\real, \ast)$ by

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

Show that f is an isomorphism.

24. Prove that if $f: G \to H$ is an invertible group map, then $f^{-1}$ is a group map. (Thus, if f is an isomorphism, then its inverse is as well.)

25. Suppose n and x are integers, $n > 0$ ,

$$n \mid 2 x + 5 \quad\hbox{and}\quad n \mid 3 x + 4.$$

Prove that $n = 1$ or $n = 7$ .

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

$$n \mid 2 x + 1 \quad\hbox{and}\quad n \mid 2 x + 3.$$

Prove that $n = 1$ .

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 $49^{-1}$ in $\integer_{61}$ .

29. Prove that if m is an integer, then $(6 m + 4, 5 m + 3) = 1$ or 2. Give specific values of m which show that both cases can occur.

30. Prove that if $a, b \in \integer$ , then $\left(\dfrac{a}{(a, b)}, \dfrac{b}{(a, b)}\right) = 1$ .

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 $p^3 q^{10} r^2$ and $p^5 q^7$ , where p, q, and r are distinct primes.

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

34. (a) For what integers n is $n^2 - 3 n + 2$ prime?

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

35. Suppose $a, b, c \in \integer$ and $c \mid a b$ . Prove that $c \mid (a, c)(b, c)$ .

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

$$(x - 1)^2 \mid x^n - n x(x - 1) - 1.$$

37. Prove that if $n \ge 1$ , then

$$1^3 + 2^3 + \cdots + n^3 = \dfrac{1}{4} n^2 (n + 1)^2.$$

38. Prove that there is no integer x such that $78 x = 61 \mod{91}$ .

39. Solve the equation $34 x + 63 = 191 \mod{225}$ .

40. Compute $\displaystyle \sum_{n=1}^{100} n! \mod{8}$ .

41. Recall that

$${n \choose k} = \dfrac{n!}{k!\, (n - k)!}.$$

Suppose p is an odd prime. Compute

$${p \choose 0} + {p \choose 1} + \cdots + {p \choose {p - 1}} + {p \choose p} \mod{p}.$$

42. Prove that if $n \in \integer$ , then $n^3 + 3 n + 5$ is not divisible by 7.

43. Prove that there are no integers m and n such that $11 m^2 - 4 n^2 = 33$ .

44. Solve the following modular equation and simplify your answer to a number in the range $\{0, 1, \ldots, 60\}$ .

$$8 x + 55 = 14(2 x + 3) \mod{61}.$$

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

$$6 x = 7 \mod{12}.$$

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

$$2 x = 6 \mod{10}.$$

Bonzo says: "In the last problem, 6 and 12 weren't relatively prime, so you couldn't find $6^{-1} \mod{12}$ 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.

Solutions to the Review Sheet for Test 1

1. A binary operation is defined on $\integer$ by

$$a \ast b = a^2 + b^2.$$

(a) Prove or disprove: $\ast$ is associative.

(b) Prove or disprove: $\ast$ is commutative.

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

(a)

$$(1 \ast 2) \ast 3 = (1 + 4) \ast 3 = 5 \ast 3 = 25 + 9 = 34,$$

$$1 \ast (2 \ast 3) = 1 \ast (4 + 9) = 1 \ast 13 = 1 + 169 = 170.$$

Since $(1 \ast 2) \ast 3 \ne 1 \ast (2 \ast 3)$ , it follows that $\ast$ is not associative.

(b) Let $a, b \in \integer$ . Then

$$a \ast b = a^2 + b^2 = b^2 + a^2 = b \ast a.$$

Hence, $\ast$ is commutative.

(c) Suppose e is an identity for $\ast$ . Then in particular, $e \ast (-1) = -1$ . But

$$e \ast (-1) = e^2 + (-1)^2 = e^2 + 1 > 0.$$

Hence, $e \ast (-1) \ne -1$ . This contradiction shows that there is no identity element for $\ast$ .

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

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

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

(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 $\integer_p$ have multiplicative inverses?

(b) How many elements of $\integer_{p^2}$ have multiplicative inverses?

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

(b) The elements in $\integer_{p^2}$ which have multiplicative inverses are the elements which are relatively prime to $p^2$ . I'll count the number of elements which are not relatively prime to $p^2$ and subtract this from $p^2$ , the number of elements in $\integer_{p^2}$ .

If $n \in \integer_{p^2}$ is not relatively prime to $p^2$ , then it must have a common factor with $p^2$ other than 1. The only factors of $p^2$ other than 1 are p and $p^2$ , and both of these are divisible by the prime p. Thus, $n \in \integer_{p^2}$ is not relatively prime to $p^2$ if and only if it's divisible by p.

What elements of $\integer_{p^2}$ are divisible by p? Here are the multiples of p:

$$0, \quad p, \quad 2p, \quad 3p, \ldots, (p - 1)p.$$

There are p of them; that is, there are p elements of $\integer_{p^2}$ which are not relatively prime to $p^2$ . Hence, there are $p^2 - p$ elements which are relatively prime to $p^2$ --- and therefore, $p^2 - p$ elements which have multiplicative inverses.

Here's a specific example. Suppose $p = 3$ . In $\integer_9$ , the elements which are relatively prime to 3 are

$$1, \quad 2, \quad 4, \quad 5, \quad 7, \quad 8.$$

There are 6 of them, and $6 = 3^2 - 3$ .

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

(a) The set $\{1, 3, 7, 9\}$ under multiplication mod 10.

(b) The set of $2 \times 2$ matrices with real entries under matrix multiplication.

(c) The set of positive integers under multiplication.

(d) The set of integers under the operation $x \ast y = x y + 1$ .

(e) The set of rational numbers under division.

(f) The following set of $2\times 2$ matrices under matrix addition:

$$G = \left\{\left[\matrix{x & x \cr y & y \cr}\right] \Bigm| x, y \in \integer\right\}.$$

(g) The set of all pairs of real numbers $(a, b)$ , where $a, b \ne 0$ , under the operation

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

(a) Here's the multiplication table:

$$\vbox{\offinterlineskip \halign{& \vrule # & \strut \hfil \quad # \quad \hfil \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & & \omit & \cr & $\cdot$ & & 1 & & 3 & & 7 & & 9 & \cr height2pt & \omit & & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & & \omit & \cr & 1 & & 1 & & 3 & & 7 & & 9 & \cr height2pt & \omit & & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & & \omit & \cr & 3 & & 3 & & 9 & & 1 & & 7 & \cr height2pt & \omit & & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & & \omit & \cr & 7 & & 7 & & 1 & & 9 & & 3 & \cr height2pt & \omit & & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & & \omit & \cr & 9 & & 9 & & 7 & & 3 & & 1 & \cr height2pt & \omit & & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} }} $$

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: $1^{-1} = 1$ , $3^{-1} = 7$ , $7^{-1} = 3$ , and $9^{-1} = 9$ .

Therefore, the set is a group under the operation.

(b) The set is closed under the operation, and matrix multiplication is associative. The matrix $\displaystyle \left[\matrix{1 & 0 \cr 0 & 1 \cr}\right]$ 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, $\displaystyle \left[\matrix{0 & 0 \cr 0 & 0 \cr}\right]$ 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 $2 \times 2$ 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 $2 \cdot x = 1$ .

The set is not a group under multiplication.

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

Let $x, y, z \in \integer$ . Then

$$(x \ast y) \ast z = (x y + 1) \ast z = (x y + 1)z + 1 = x y z + z + 1,$$

$$x \ast (y \ast z) = x \ast (y z + 1) = x(y z + 1) + 1 = x y z + x + 1.$$

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

$$(2 \ast 3) \ast 4 = 24 + 4 + 1 = 29 \quad\hbox{while}\quad 2 \ast (3 \ast 4) = 24 + 2 + 1 = 27.$$

Thus, $(2 \ast 3) \ast 4 \ne 2 \ast (3 \ast 4)$ . The operation is not associative.

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

$$e \cdot 3 + 1 = 3, \quad\hbox{or}\quad 3 e = 2.$$

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

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

$\integer$ is not a group under $\ast$ .

(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 $\rational$ .

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

$$\left[\matrix{x_1 & x_1 \cr y_1 & y_1 \cr}\right] + \left[\matrix{x_2 & x_2 \cr y_2 & y_2 \cr}\right] = \left[\matrix{x_1 + x_2 & x_1 + x_2 \cr y_1 + y_2 & y_1 + y_2 \cr}\right].$$

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 $\displaystyle \left[\matrix{0 & 0 \cr 0 & 0 \cr}\right]$ , and this is an element of G.

Finally, if $\displaystyle \left[\matrix{x & x \cr y & y \cr}\right] \in G$ , its additive inverse is also in G:

$$-\left[\matrix{x & x \cr y & y \cr}\right] = \left[\matrix{-x & -x \cr -y & -y \cr}\right] \in G.$$

Therefore, G is a group under matrix addition.

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

I have

$$[(a, b) \cdot (c, d)] \cdot (e, f) = (a c, b d) \cdot (e, f) = (a c e, b d f),$$

$$(a, b) \cdot [(c, d) \cdot (e, f)] = (a, b) \cdot (c e, d f) = (a c e, b d f).$$

Therefore, the operation is associative.

I also have

$$(1, 1) \cdot (a, b) = (a, b) \quad\hbox{and}\quad (a, b) \cdot (1, 1) = (a, b).$$

Therefore, $(1, 1)$ is the identity element for the operation.

If $(a, b)$ is in the set, then $a, b \ne 0$ . Hence, $\dfrac{1}{a}$ and $\dfrac{1}{b}$ are defined. I have

$$(a, b)\cdot \left(\dfrac{1}{a},\dfrac{1}{b}\right) = (1,1) \quad\hbox{and}\quad \left(\dfrac{1}{a},\dfrac{1}{b}\right)\cdot (a, b) = (1,1).$$

Hence, $(a, b)^{-1} = \left(\dfrac{1}{a},\dfrac{1}{b}\right)$ .

Therefore, the set is a group under the operation.

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

$$\matrix{ \hbox{\epsfxsize=1in \epsffile{rev1-1.eps}} & \hbox{\hskip0.5in} & \hbox{\epsfxsize=1in \epsffile{rev1-2.eps}} & \hbox{\hskip0.5in} & \hbox{\epsfysize=1in \epsffile{rev1-3.eps}} \cr \noalign{\vskip8pt} \hbox{(a)} & \hbox{\hskip0.5in} & \hbox{(b)} & \hbox{\hskip0.5in} & \hbox{(c)} \cr}$$

Figure (a) has four symmetries: The identity, rotations through $180^\circ$ , 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 $a, b, c \in G$ . Simplify the following expressions as much as possible:

(a) $a^{-1} (a b^3)^2 b^{-4}$

(b) $b (a^{-1} b)^{-2} a^{-1}$ .

(c) $(a b^2)^{-1} (b a^2)^{-1}$ .

(d) $(a b c)^2 c^{-1} b^{-1} a^{-5}$ .

(a)

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

(b)

$$b (a^{-1} b)^{-2} a^{-1} = b [(a^{-1} b)^{-1}]^2 a^{-1} = b (b^{-1} a)^2 a^{-1} = b b^{-1} a b^{-1} a a^{-1} = a b^{-1}.\quad\halmos$$

(c)

$$(a b^2)^{-1} (b a^2)^{-1} = b^{-2} a^{-1} a^{-2} b^{-1} = b^{-2} a^{-3} b^{-1}.\quad\halmos$$

(d)

$$(a b c)^2 c^{-1} b^{-1} a^{-5} = (a b c) (a b c) c^{-1} b^{-1} a^{-5} = a b c a b b^{-1} a^{-5} = a b c a a^{-5} = a b c a^{-4}.\quad\halmos$$

7. Let G be a group and let $a, b, x \in G$ . Solve the following equation for x:

$$(a b^{-2})^{-1} x a^{-1} b = b^2 a^{-2} b^2.$$

$$\eqalign{ (a b^{-2})^{-1} x a^{-1} b & = b^2 a^{-2} b^2 \cr b^2 a^{-1} x a^{-1} b & = b^2 a^{-2} b^2 \cr a b^{-2} b^2 a^{-1} x a^{-1} b b^{-1} a & = a b^{-2} b^2 a^{-2} b^2 b^{-1} a \cr x & = a^{-1} b a \cr} \quad\halmos$$

8. Let G be a group and let $a, b, x \in G$ . Solve the following equation for x:

$$a^2 b^{-1} x (a b)^2 = a^3 b^{-3} a b a^2 b.$$

$$\eqalign{ a^2 b^{-1} x (a b)^2 & = a^3 b^{-3} a b a^2 b \cr b a^{-2} a^2 b^{-1} x (a b)^2 & = b a^{-2} a^3 b^{-3} a b a^2 b \cr x (a b)^2 & = b a b^{-3} a b a^2 b \cr x a b a b & = b a b^{-3} a b a^2 b \cr x a b a b b^{-1} a^{-1} b^{-1} a^{-1} & = b a b^{-3} a b a^2 b b^{-1} a^{-1} b^{-1} a^{-1} \cr x & = b a b^{-3} a b a b^{-1} a^{-1} \quad\halmos \cr}$$

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

Suppose on the contrary that $a \ne b$ , but both $a^m = b^m$ and $a^n = b^n$ . Since $(m, n) = 1$ , there are integers s and t such that

$$s m + t n = 1.$$

Then

$$\eqalign{ (a^m)^s & = (b^m)^s \cr a^{s m} & = b^{s m} \cr}$$

Likewise,

$$\eqalign{ (a^n)^t & = (b^n)^t \cr a^{t n} & = b^{t n} \cr}$$

So

$$\eqalign{ a^{s m} \cdot a^{t n} & = b^{s m} \cdot b^{t n} \cr a^{m s + n t} & = b^{m s + n t} \cr a & = b \cr}$$

This contradicts $a \ne b$ .

Hence,either $a^m \ne b^m$ or $a^n \ne b^n$ .

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

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

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

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

11. Let G be a group, let $a, b \in G$ , and suppose that $a b = b a$ . Prove that for all $n \ge 1$ ,

$$a b^n = b^n a.$$

I'll use induction on n. For $n = 1$ , the result says $a b = b a$ , which is true by assumption.

Suppose that $n > 1$ , and suppose that the result is true for $n - 1$ :

$$a b^{n-1} = b^{n-1} a.$$

I need to prove the result for n. I have

$$\matrix{ a b^n & = & a b^{n-1}\cdot b & \hbox{(Since $b^n = b^{n-1} b$)} \cr & = & b^{n-1} a b & \hbox{(By induction)} \cr & = & b^{n-1} b a & \hbox{(Since $a b = b a$)} \cr & = & b^n a & \hbox{(Since $b^n = b^{n-1} b$)} \cr}$$

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

12. (a) Find the inverse of $\left[\matrix{2 & 6 \cr 1 & 5 \cr}\right]$ in the group $GL(2, \integer_7)$ .

(b) Explain why $GL(2, \integer_7)$ is not a group under addition.

(a)

$$\left[\matrix{2 & 6 \cr 1 & 5 \cr}\right]^{-1} = (2 \cdot 5 - 6 \cdot 1)^{-1} \left[\matrix{5 & 1 \cr 6 & 2 \cr}\right] = 4^{-1} \left[\matrix{5 & 1 \cr 6 & 2 \cr}\right] = 2 \cdot \left[\matrix{5 & 1 \cr 6 & 2 \cr}\right] = \left[\matrix{3 & 2 \cr 5 & 4 \cr}\right].\quad\halmos$$

(b) $GL(2, \integer_7)$ is not closed under addition. For example,

$$\left[\matrix{1 & 0 \cr 0 & 1 \cr}\right], \left[\matrix{6 & 0 \cr 0 & 6 \cr}\right] \in GL(2, \integer_7), \quad\hbox{but}\quad \left[\matrix{1 & 0 \cr 0 & 1 \cr}\right] + \left[\matrix{6 & 0 \cr 0 & 6 \cr}\right] = \left[\matrix{0 & 0 \cr 0 & 0 \cr}\right] \notin GL(2, \integer_7). \quad\halmos$$

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 $H = \{\ldots, -3 \sqrt{2}, -2 \sqrt{2}, -\sqrt{2}, 0, \sqrt{2}, 2 \sqrt{2}, 3 \sqrt{2}, \ldots\}$ of the group $\real$ of real numbers under addition.

(b) The following subset of $GL(2, \real)$ :

$$K = \left\{\left[\matrix{a & 0 \cr 0 & d \cr}\right] \Bigm| a d = 1\right\}.$$

(c) The subset J of the group $\real^2$ under vector addition consisting of vectors $(a, b)$ which satisfy $a = b^2$ .

(d) The subset $H = \{x \in G \mid x^2 = 1\}$ in an abelian group G.

(e) The subset $P = \{(x, y, z) \in \integer^3 \mid 3 x + 4 y = 5 z\}$ . ($\integer^3$ is a group under component-wise addition [i.e. vector addition].)

(f) The subset $K = \{A \in M(2, \real) \mid A B A = 0\}$ , where $B \in M(2, \real)$ is a fixed matrix and 0 denotes the $2 \times 2$ zero matrix.

(a) Elements of the subset have the form $n \sqrt{2}$ , where n is an integer.

If m and n are integers, then

$$m \sqrt{2} + n \sqrt{2} = (m + n)\sqrt{2} \in H.$$

Therefore, H is closed under the group operation.

$0 = 0 \sqrt{2} \in H$ , so the identity element of $\real$ is contained in H.

Finally, if $n \sqrt{2} \in H$ , its additive inverse $-n \sqrt{2}$ is also in H.

Hence, H is a subgroup of $\real$ .

(b) Suppose $\displaystyle \left[\matrix{a & 0 \cr 0 & d \cr}\right], \left[\matrix{a' & 0 \cr 0 & d' \cr}\right] \in K$ , so $a d = 1$ and $a'd' = 1$ . Their product is

$$\left[\matrix{a & 0 \cr 0 & d \cr}\right] \left[\matrix{a' & 0 \cr 0 & d' \cr}\right] = \left[\matrix{a a' & 0 \cr 0 & d d' \cr}\right].$$

$$(a a')(d d') = (a d)(a' d') = 1 \cdot 1 = 1.$$

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

The identity matrix $\displaystyle \left[\matrix{1 & 0 \cr 0 & 1 \cr}\right]$ of $GL(2, \real)$ is in K, since $1 \cdot 1 = 1$ .

If $\displaystyle \left[\matrix{a & 0 \cr 0 & d \cr}\right] \in K$ , its inverse is

$$\left[\matrix{a & 0 \cr 0 & d \cr}\right]^{-1} = \left[\matrix{\dfrac{1}{a} & 0 \cr 0 & \dfrac{1}{d} \cr}\right].$$

Now $a d = 1$ , so $\left(\dfrac{1}{a}\right)\left(\dfrac{1}{d}\right) = \dfrac{1}{a d} = 1$ . Hence, the inverse is in K.

Therefore, K is a subgroup of $GL(2, \real)$ .

(c) J is not closed under vector addition. $(1, 1)$ is in the set, since $1 = 1^2$ , and $(4, 2)$ is in the set, since $4 = 2^2$ . But since $5 \ne 3^2$ ,

$$(1, 1) + (4, 2) = (5, 3) \notin J.$$

The identity vector $(0, 0)$ is in J, since $0 = 0^2$ .

The vector $( 1, 1)$ is in the set, since $1 = 1^2$ . However, its additive inverse $-(1, 1) = (-1, -1)$ is not in the set, since $-1 \ne (-1)^2$ .

J is not a subgroup of $\real^2$ .

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

Suppose $x, y \in H$ . This means that $x^2 = 1$ and $y^2 = 1$ . I want to show that $x y \in H$ . I'll square it and see if I get 1:

$$(x y)^2 = x y x y = x x y y = x^2 y^2 = 1 \cdot 1 = 1.$$

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

$1^2 = 1$ , so $1 \in H$ .

Finally, suppose $x \in H$ , so $x^2 = 1$ . I want to show that $x^{-1} \in H$ . I'll square it and see if I get 1:

$$(x^{-1})^2 = x^{-2} = (x^2)^{-1} = 1^{-1} = 1.$$

Therefore, $x^{-1} \in H$ , and H is closed under taking inverses.

Hence, H is a subgroup of G.

(e) Let $(x, y, z), (x', y', z') \in P$ . I have to show that

$$(x, y, z) + (x', y', z') = (x + x', y + y', z + z') \in P.$$

Since $(x, y, z), (x', y', z') \in P$ , I have

$$3 x + 4 y = 5 z \quad\hbox{and}\quad 3 x' + 4 y' = 5 z'.$$

So

$$(3 x + 4 y) + (3 x' + 4 y') = 5 z + 5 z', \quad\hbox{and}\quad 3(x + x') + 4(y + y') = 5(z + z').$$

Therefore, $(x + x', y + y', z + z') \in P$ .

Since $3 \cdot 0 + 4 \cdot 0 = 5 \cdot 0$ , it follows that $(0, 0, 0) \in P$ .

Finally, suppose $(x, y, z) \in P$ . I have to show that

$$-(x, y, z) = (-x, -y, -z) \in P.$$

Since $(x, y, z) \in P$ , I have $3 x + 4 y = 5 z$ . So

$$-(3 x + 4 y) = -5 z, \quad\hbox{and}\quad 3(-x) + 4(-y) = 5(-z).$$

Therefore, $(-x, -y, -z) \in P$ .

Hence, P is a subgroup of $\integer^3$ .

(f) Let $A, A' \in K$ . I want to show that $A + A' \in K$ . Since $A, A' \in K$ , I have

$$A B A = 0 \quad\hbox{and}\quad A' B A' = 0.$$

Hence,

$$\eqalign{ A B A + A' B A' & = 0 \cr (A + A') B (A + A') & = 0 \cr}$$

Therefore, $A + A' \in K$ .

The identity for matrix addition is the zero matrix 0. Since $0 \cdot B \cdot 0 = 0$ , it follows that $0 \in K$ .

Finally, let $A \in K$ . I need to show that $-A \in K$ . Since $A \in K$ , I have $A B A = 0$ . Therefore,

$$(-1) A B A (-1) = (-1)\, 0\, (-1), \quad\hbox{so}\quad (-A) B (-A) = 0.$$

(In the first equality, I'm multiplying both sides of $A B A = 0$ by the numbers -1 and -1.) Thus, $-A \in K$ .

Hence, K is a subgroup of $M(2, \real)$ .

14. Suppose that G is a group, H is a subgroup of G, and $g \in G$ . Let

$$g H g^{-1} = \{g h g^{-1} \mid h \in H\}.$$

Prove that $g H g^{-1}$ is a subgroup of G.

$g H g^{-1}$ consists of all elements of the form $g(\hbox{something in H})g^{-1}$ .

Let $g h_1 g^{-1}, g h_2 g^{-1} \in g H g^{-1}$ , where $h_1, h_2 \in H$ . Then

$$(g h_1 g^{-1})(g h_2 g^{-1}) = g(h_1 h_2)g^{-1}.$$

Since $h_1 h_2 \in H$ --- H is a subgroup, so it's closed under products --- it follows that $g(h_1 h_2)g^{-1} \in g H g^{-1}$ . Therefore, $g H g^{-1}$ is closed under products.

Since $1 \in H$ , $g(1)g^{-1} \in g H g^{-1}$ . But $g(1)g^{-1} = 1$ , so $1 \in g H g^{-1}$ . Thus, $g H g^{-1}$ contains the identity.

Suppose $g h g^{-1} \in g H g^{-1}$ , where $h \in H$ . The inverse is

$$(g h g^{-1})^{-1} = g h^{-1} g^{-1}.$$

$h^{-1} \in H$ , since H is a subgroup (and therefore closed under taking inverses). Therefore, $g h^{-1} g^{-1} \in g H g^{-1}$ , and $g H g^{-1}$ is closed under taking inverses.

Therefore, $g H g^{-1}$ is a subgroup of G.

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

$$h k = k h \quad\hbox{for all}\quad h \in H \quad\hbox{and}\quad k \in K.$$

Define

$$H K = \{h k \mid h \in H \quad\hbox{and}\quad k \in K\}.$$

Prove that $H K$ is a subgroup of G.

Let $h_1, h_2 \in H$ and $k_1, k_2 \in K$ . $h_1 k_1$ and $h_2 k_2$ are two typical elements of $H K$ ; I must show that their product is in $H K$ . But by assumption, anything in H commutes with anything in K. So $k_1 h_2 = h_2 k_1$ , and

$$(h_1 k_1)(h_2 k_2) = (h_1 h_2)(k_1 k_2) \in H K.$$

Since $1 \in H$ and $1 \in K$ , $1 = 1 \cdot 1 \in H K$ .

Let $h \in H$ and $k \in K$ . Since $h^{-1}$ and $k^{-1}$ commute, I have

$$(h k)^{-1} = k^{-1} h^{-1} = h^{-1} k^{-1} \in H K.$$

Therefore, $H K$ is a subgroup of G.

16. Suppose G is a group with operation $\ast$ and H is a group with operation $\odot$ . What equation must be true for a function $f: G \to H$ to be a group map?

$$f(x \ast y) = f(x) \odot f(y) \quad\hbox{for all}\quad x, y \in G.\quad\halmos$$

17. Consider the following function $f: \integer_3 \to \integer_4$ :

$$f(0) = 0, \quad f(1) = 1, \quad f(2) = 2.$$

Is f a group homomorphism?

f is not a homomorphism! For instance,

$$f(1) + f(2) = 1 + 2 = 3, \quad\hbox{while}\quad f(1 + 2) = f(0) = 0.$$

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) $\real[x]$ is the group of polynomials with real coefficients under polynomial addition and $g: \real[x] \to (\real, +)$ is defined by

$$g\left(\phi(x)\right) = \phi(1).$$

(b) $h: (\integer, +) \to (\integer, +)$ is defined by

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

(c) $\phi: \integer \times \integer \to (\integer, +)$ is defined by

$$\phi(x, y) = 2 x + 3 y.$$

(Here $\integer \times \integer$ is a group under component-wise addition [i.e. "vector addition"], so $(a, b) + (c, d) = (a + c, b + d)$ .)

(d) $\det: GL(n, \real) \to (\real^*, \cdot)$ is the determinant function, $GL(n, \real)$ is the group of invertible $n \times n$ real matrices under matrix multiplication, and $\real^*$ is the group of nonzero real numbers under multiplication.

(e) $f: (\real^*, \cdot) \to (\real, +)$ is defined by

$$f(x) = x^2 - 1.$$

(a) If $\phi(x)$ and $\psi(x)$ are polynomials, then

$$g\left(\phi(x) + \psi(x)\right) = \phi(1) + \psi(1),$$

$$g\left(\phi(x)\right) + g\left(\psi(x)\right) = \phi(1) + \psi(1).$$

Therefore, $g\left(\phi(x) + \psi(x)\right) = g\left(\phi(x)\right) + g\left(\psi(x)\right)$ , 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, $h(0) = 0 \cdot 1 = 0$ , so h takes the identity to the identity. However, this doesn't prove that h is a homomorphism.

In fact,

$$h(2 + 3) = h(5) = 5 \cdot 6 = 30, \quad\hbox{but}\quad h(2) + h(3) = 2 \cdot 3 + 3 \cdot 4 = 18.$$

Therefore, $h(2 + 3) \ne h(2) + h(3)$ , so h is not a homomorphism.

(c) Let $(a, b), (c, d) \in \integer \times \integer$ . Then

$$\phi\left((a, b) + (c, d)\right) = \phi(a + c, b + d) = 2(a + c) + 3(b + d) = (2 a + 3 b) + (2 c + 3 d) = \phi(a, b) + \phi(c, d).$$

Therefore, $\phi$ is a group map.

(d) Let $A, B \in GL(n, \real)$ . From linear algebra, the determinant of a product is the product of the determinants, so

$$\det (A B) = (\det A)(\det B).$$

Hence, $\det$ is a group map.

(e) I have

$$f(2 \cdot 3) = f(6) = 6^2 - 1 = 35, \quad\hbox{but}\quad f(2) + f(3) = (2^2 - 1) + (3^2 - 1) = 3 + 8 = 11.$$

Since $f(2 \cdot 3) \ne f(2) + f(3)$ , it follows that f is not a group map.

19. The function $f: \integer_{12} \to \integer_{12}$ defined by $f(x) = 3 x \mod{12}$ is a group map.

(a) Find $\ker f$ .

(b) Find $\im f$ .

(c) Find $f^{-1}(\{6\})$ .

(a) $x \in \ker f$ if and only if $3 x = 0 \mod{12}$ . But $3 x = 0 \mod{12}$ is equivalent to $12 \mid 3 x$ , or $4 \mid x$ . Thus,

$$\ker f = \{0, 4, 8\}.\quad\halmos$$

(b)

$$\im f = \{0, 3, 6, 9\}.\quad\halmos$$

(c) $x \in f^{-1}(\{6\})$ is equivalent to $f(x) = 6$ , or $3 x = 6 \mod{12}$ . This is equivalent to $12 \mid 3 x - 6$ , or $4 \mid x - 2$ . Since the elements divisible by 4 are the elements of $\ker f$ , the last equation says that the elements of $f^{-1}(\{6\})$ are obtained by adding 2 to the elements of $\ker f$ . Thus,

$$f^{-1}(\{6\}) = \{2, 6, 10\}.\quad\halmos$$

20. Define $f: \real^* \to \real^*$ by

$$f(x) = x^2.$$

($\real^*$ is the group of nonzero reals under multiplication.)

(a) Prove that f is a group map.

(b) Find $\ker f$ and $\im f$ .

(a) Let $x, y \in \real^*$ . Then (since $\real^*$ is abelian)

$$f(x y) = (x y)^2 = x y x y = x^2 y^2 = f(x) f(y).$$

Therefore, f is a group map.

(b) The identity of $\real^*$ is 1. So

$$\ker f = \{x \in \real^* \mid f(x) = 1\} = \{x \in \real^* \mid x^2 = 1\} = \{1, -1\}.$$

If $x \in \real^*$ , then $f(x) = x^2 > 0$ . Thus, $f(x)$ is always a positive real number, and $\im f \subset \real^+$ .

Conversely, if y is a positive real number, then

$$f(\sqrt{y}) = (\sqrt{y})^2 = y.$$

Therefore, $\real^+ \subset \im f$ . Hence, $\im f = \real^+$ .

21. Define $f: \integer_3 \to \integer_8$ by $f(x) = 5 x \mod{8}$ . Is f a group map?

I have

$$f(2 + 2) = f(1) = 5, \quad\hbox{but}\quad f(2) + f(2) = 2 + 2 = 4.$$

Since $f(2 + 2) \ne f(2) + f(2)$ , it follows that f is not a group map.

22. Let G and H be groups, and let $\phi: G \to H$ be a group map. Let $g \in G$ . Prove that if g has finite order, then the order of $\phi(g)$ divides the order of g.

Suppose that g has order n. Then $g^n = 1$ , so

$$[\phi(g)]^n = \phi(g^n) = \phi(1) = 1.$$

Hence, the order of $\phi(g)$ must divide n.

23. $\real$ is a group under the operation

$$a \ast b = a + b - 2.$$

Define $f: (\real, +) \to (\real, \ast)$ by

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

Show that f is an isomorphism.

Let $x, y \in \real$ . Then

$$f(x + y) = x + y + 2 \quad\hbox{and}\quad f(x) \ast f(y) = (x + 2) \ast (y + 2) = (x + 2) + (y + 2) - 2 = x + y + 2.$$

Hence, $f(x + y) = f(x) \ast f(y)$ , and so f is a group map.

Define $g: (\real, \ast) \to (\real, +)$ by

$$g(x) = x - 2.$$

Then

$$f(g(x)) = f(x - 2) = (x - 2) + 2 = x,$$

$$g(f(x)) = g(x + 2) = (x + 2) - 2 = x.$$

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

24. Prove that if $f: G \to H$ is an invertible group map, then $f^{-1}$ is a group map. (Thus, if f is an isomorphism, then its inverse is as well.)

Let $x, y \in H$ . Since f and $f^{-1}$ are inverses, $f(f^{-1}(x)) = x$ for all $x \in H$ . In particular,

$$f\left(f^{-1}(x \cdot y)\right) = x \cdot y.$$

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

$$f\left(f^{-1}(x) \cdot f^{-1}(y)\right) = f\left(f^{-1}(x)\right) \cdot f\left(f^{-1}(y)\right) = x \cdot y.$$

Therefore,

$$f\left(f^{-1}(x \cdot y)\right) = f\left(f^{-1}(x) \cdot f^{-1}(y)\right).$$

But f is invertible, so it's injective. This means that $f(x) = f(y)$ implies $x = y$ . So the last equation above gives

$$f^{-1}(x \cdot y) = f^{-1}(x) \cdot f^{-1}(y).$$

Thus, $f^{-1}$ is a group map.

25. Suppose n and x are integers, $n > 0$ ,

$$n \mid 2 x + 5 \quad\hbox{and}\quad n \mid 3 x + 4.$$

Prove that $n = 1$ or $n = 7$ .

The idea is to make a linear combination of $2 x + 5$ and $3 x + 4$ where the x's cancel:

$$n \mid 3(2 x + 5) - 2(3 x + 4) = 7.$$

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

Using $x = 0$ and $x = 1$ , you can see that both cases could occur.

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

$$n \mid 2 x + 1 \quad\hbox{and}\quad n \mid 2 x + 3.$$

Prove that $n = 1$ .

n divides $2x + 1$ and $2 x + 3$ , so

$$n \mid (2 x + 3) - (2 x + 1) = 2.$$

But n is odd, so $n = \pm 1$ .

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

$$\vbox{\offinterlineskip \halign{& \vrule # & \strut \hfil \quad # \quad \hfil \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & 3462 & & - & & 88 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & 118 & & 29 & & 3 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & 40 & & 2 & & 1 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & 38 & & 1 & & 1 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & 2 & & 19 & & 0 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} }} $$

The GCD of 3462 and 118 is 2, and

$$(3)(3462) + (-88)(118) = 2.\quad\halmos$$

28. Use the Extended Euclidean Algorithm to find $49^{-1}$ in $\integer_{61}$ .

$$\vbox{\offinterlineskip \halign{& \vrule # & \strut \hfil \quad # \quad \hfil \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & 61 & & - & & 5 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & 49 & & 1 & & 4 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & 12 & & 4 & & 1 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & 1 & & 12 & & 0 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} }} $$

$$\eqalign{ 5 \cdot 49 - 4 \cdot 61 & = 1 \cr 5 \cdot 49 & = 1 \mod{61} \cr}$$

Hence, $49^{-1} = 5$ in $\integer_{61}$ .

29. Prove that if m is an integer, then $(6 m + 4, 5 m + 3) = 1$ or 2. Give specific values of m which show that both cases can occur.

Note that

$$5 \cdot (6 m + 4) - 6 \cdot (5 m + 3) = 2.$$

Now $(6 m + 4, 5 m + 3) \mid (6 m + 4)$ and $(6 m + 4, 5 m + 3) \mid (5 m + 3)$ , so

$$(6 m + 4, 5 m + 3) \mid 5 \cdot (6 m + 4) - 6 \cdot (5 m + 3) = 2.$$

But the only positive integers which divide 2 are 1 and 2, so $(6 m + 4, 5 m + 3) = 1$ or 2.

If $m = 1$ , $6 m + 4 = 10$ , $5 m + 3 = 8$ , and $(10,8) = 2$ .

If $m = 2$ , $6 m + 4 = 16$ , $5 m + 3 = 13$ , and $(16,13) = 1$ .

Therefore, both cases can occur.

30. Prove that if $a, b \in \integer$ , then $\left(\dfrac{a}{(a, b)}, \dfrac{b}{(a, b)}\right) = 1$ .

Since $(a, b) \mid a$ and $(a, b) \mid b$ , I can write

$$a = m(a, b) \quad\hbox{and}\quad b = n(a, b) \quad\hbox{for}\quad m, n \in \integer.$$

I want to show that $(m, n) = 1$ . There are integers $j, k \in \integer$ such that

$$(a, b) = j a + k b.$$

Then

$$(a, b) = j m (a, b) + k n (a, b), \quad\hbox{so}\quad 1 = j m + k n.$$

Hence, $(m, n) = 1$ .

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

Suppose m and n are both divisible by 7, and $m - n = 1000$ . Since $7 \mid m$ and $7 \mid n$ , I have $7 \mid m - n = 1000$ . This is a contradiction, since $7 \notdiv 1000$ . 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 $p^3 q^{10} r^2$ and $p^5 q^7$ , 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:

$$(p^3 q^{10} r^2, p^5 q^7) = p^3 q^7.$$

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

$$[p^3 q^{10} r^2, p^5 q^7] = p^5 q^{10} r^2.\quad\halmos$$

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

A positive divisor of $p q r$ 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 $2^3 = 8$ choices, and 8 positive divisors.

34. (a) For what integers n is $n^2 - 3 n + 2$ prime?

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

(a) Suppose $n^2 - 3 n + 2 = p$ , where p is prime. Then $(n - 1)(n - 2) = p$ , and there are four cases.

Case 1: $n - 1 = 1$ and $n - 2 = p$ .

$n - 1 = 1$ gives $n = 2$ , so $p = n - 2 = 0$ . This is a contradiction, since 0 isn't prime.

Case 2: $n - 1 = -1$ and $n - 2 = -p$ .

$n - 1 = -1$ gives $n = 0$ , so $-p = n - 2 = -2$ , and $p = 2$ . This works, since 2 is prime.

Case 3: $n - 1 = p$ and $n - 2 = 1$ .

$n - 2 = 1$ gives $n = 3$ , so $p = n - 1 = 2$ . This works, since 2 is prime.

Case 4: $n - 1 = -p$ and $n - 2 = -1$ .

$n - 2 = -1$ gives $n = 1$ , so $-p = n - 1 = 0$ , and $p = 0$ . This is a contradiction, since 0 isn't prime.

Thus, $n^2 - 3 n + 2$ is prime for $n = 0$ and $n = 3$ .

(b) Calvin is wrong. For example, if $n = 2$ , $n^2 + 2 n + 2 = 10$ , which is not prime.

35. Suppose $a, b, c \in \integer$ and $c \mid a b$ . Prove that $c \mid (a, c) (b, c)$ .

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

$$(a, c) = w a + x c \quad\hbox{and}\quad (b, c) = y b + z c.$$

Then

$$(a, c) (b, c) = (w a + x c)(y b + z c) = w y (a b) + (w z a + x y b + x z c)c.$$

Since $c \mid a b \mid w y (a b)$ and $c \mid (w z a + x y b + x z c)c$ , it follows that $c \mid (a, c) (b, c)$ .

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

$$(x - 1)^2 \mid x^n - n x(x - 1) - 1.$$

First, I have

$$x^n - 1 = (x - 1)(x^{n-1} + x^{n-2} + \cdots + x + 1).$$

So

$$\eqalign{ x^n - n x(x - 1) - 1 & = (x - 1)(x^{n-1} + x^{n-2} + \cdots + x + 1) - n x(x - 1) \cr & = (x - 1)[(x^{n-1} + x^{n-2} + \cdots + x + 1) - n x] \cr}$$

Consider the polynomial $(x^{n-1} + x^{n-2} + \cdots + x + 1) - n x$ . Plugging in $x = 1$ gives

$$\overbrace{(1 + 1 + \cdot + 1)}^{n\,\rm times} - n = 0.$$

Thus, $x = 1$ is a root of $(x^{n-1} + x^{n-2} + \cdots + x + 1) - n x$ , so by the Root Theorem, $x - 1$ must be a factor. So for some polynomial $p(x)$ , I have

$$(x^{n-1} + x^{n-2} + \cdots + x + 1) - n x = (x - 1) p(x).$$

Thus,

$$x^n - n x(x - 1) - 1 = (x - 1) \cdot (x - 1) p(x).$$

Hence, $(x - 1)^2 \mid x^n - n x(x - 1) - 1$ .

37. Prove that if $n \ge 1$ , then

$$1^3 + 2^3 + \cdots + n^3 = \dfrac{1}{4} n^2 (n + 1)^2.$$

For $n = 1$ , I have

$$1^3 = 1 \quad\hbox{and}\quad \dfrac{1}{4}\cdot 1^2 \cdot (1 + 1)^2 = 1.$$

The result is true for $n = 1$ .

Assume that the result is true for n:

$$1^3 + 2^3 + \cdots + n^3 = \dfrac{1}{4} n^2 (n + 1)^2.$$

I want to prove the result for $n + 1$ :

$$1^3 + 2^3 + \cdots + n^3 + (n + 1)^3 = \dfrac{1}{4} (n + 1)^2(n + 2)^2.$$

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

$$\eqalign{ 1^3 + 2^3 + \cdots + n^3 + (n + 1)^3 & = \dfrac{1}{4} n^2 (n + 1)^2 + (n + 1)^3 \cr \noalign{\vskip2pt} & = (n + 1)^2 \left(\dfrac{1}{4} n^2 + (n + 1)\right) \cr \noalign{\vskip2pt} & = \dfrac{1}{4} (n + 1)^2 \left(n^2 + 4(n + 1)\right) \cr \noalign{\vskip2pt} & = \dfrac{1}{4} (n + 1)^2 \left(n^2 + 4 n + 4\right) \cr \noalign{\vskip2pt} & = \dfrac{1}{4} (n + 1)^2 (n + 2)^2 \cr}$$

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

38. Prove that there is no integer x such that $78 x = 61 \mod{91}$ .

Suppose that $78 x = 61 \mod{91}$ . Note that $91 = 7 \cdot 13$ and $78 = 6 \cdot 13$ . Multiply by 7:

$$\eqalign{ 78 x & = 61 \mod{91} \cr 7 \cdot 78 x & = 7 \cdot 61 \mod{91} \cr 546 x & = 427 \mod{91} \cr 0 \cdot x & = 63 \mod{91} \cr 0 & = 63 \mod{91} \cr}$$

This contradiction proves that there is no such x.

39. Solve the equation $34 x + 63 = 191 \mod{225}$ .

Subtracting 63 from both sides gives $34 x = 128 \mod{225}$ . Note that $(34,225) = 1$ ; I'll find the multiplicative inverse of 34 mod 225.

$$\vbox{\offinterlineskip \halign{& \vrule # & \strut \hfil \quad # \quad \hfil \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & 225 & & - & & 86 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & 34 & & 6 & & 13 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & 21 & & 1 & & 8 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & 13 & & 1 & & 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} }} $$

The table gives

$$(13)(225) + (-86)(34) = 1, \quad\hbox{so}\quad (-86)(34) = 1 \mod{225}.$$

Multiply $34 x = 128 \mod{225}$ by -86:

$$\eqalign{ (-86) \cdot 34 x 7 = (-86)\cdot 128 \mod{225} \cr x & = -11008 = 17 \mod{225} \quad\halmos \cr}$$

40. Compute $\displaystyle \sum_{n=1}^{100} n! \mod{8}$ .

If $n \ge 8$ , then $8 \mid n!$ , so $n! = 0 \mod{8}$ . So

$$\sum_{n=1}^{100} n! = \sum_{n=1}^7 n! \mod{8}.$$

However, $4!$ , $5!$ , $6!$ , and $7!$ 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

$$\sum_{n=1}^{100} n! = \sum_{n=1}^3 n! = 1! + 2! + 3! = 1 + 2 + 6 = 1 \mod{8}.\quad\halmos$$

41. Recall that

$${n \choose k} = \dfrac{n!}{k!\, (n - k)!}.$$

Suppose p is an odd prime. Compute

$${p \choose 0} + {p \choose 1} + \cdots + {p \choose {p - 1}} + {p \choose p} \mod{p}.$$

Consider

$${p \choose k} = \dfrac{p!}{k!\, (p - k)!}.$$

For $1 \le k \le p - 1$ , 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,

$${p \choose k} = 0 \mod{p} \quad\hbox{for}\quad 1 \le k \le p - 1.$$

It follows that

$${p \choose 0} + {p \choose 1} + \cdots + {p \choose p} = 1 + 0 + \cdots + 0 + 1 = 2 \mod{p}.\quad\halmos$$

42. Prove that if $n \in \integer$ , then $n^3 + 3 n + 5$ 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:

$$\vbox{\offinterlineskip \halign{& \vrule # & \strut \hfil \quad # \quad \hfil \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr & $n \mod{7}$ & & 0 & & 1 & & 2 & & 3 & & 4 & & 5 & & 6 & \cr height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr & $n^3 + 3 n + 5 \mod{7}$ & & 5 & & 2 & & 5 & & 6 & & 4 & & 5 & & 1 & \cr height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} }} $$

For all n, I have $n^3 + 3 n + 5 \ne 0 \mod{7}$ . Hence, if $n \in \integer$ , then $n^3 + 3 n + 5$ is not divisible by 7.

43. Prove that there are no integers m and n such that $11 m^2 - 4 n^2 = 33$ .

Suppose there is a solution $(m, n)$ , so $11 m^2 - 4 n^2 = 33$ . Reduce the equation mod 4 to obtain

$$\eqalign{ 3 m^2 & = 1 \mod{4} \cr 3 \cdot 3 m^2 & = 3 \cdot 1 \mod{4} \cr m^2 & = 3 \mod{4} \cr}$$

Construct a table of squares mod 4:

$$\vbox{\offinterlineskip \halign{& \vrule # & \strut \hfil \quad # \quad \hfil \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & & \omit & \cr & $x \mod{4}$ & & 0 & & 1 & & 2 & & 3 & \cr height2pt & \omit & & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & & \omit & \cr & $x^2 \mod{4}$ & & 0 & & 1 & & 0 & & 1 & \cr height2pt & \omit & & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} }} $$

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 $\{0, 1, \ldots, 60\}$ .

$$8 x + 55 = 14(2 x + 3) \mod{61}.$$

$$\eqalign{ 8 x + 55 & = 14(2 x + 3) \mod{61} \cr 8 x + 55 & = 28 x + 42 \mod{61} \cr 13 & = 20 x \cr}$$

Use the Extended Euclidean algorithm to find $20^{-1} \mod{61}$ .

$$\vbox{\offinterlineskip \halign{& \vrule # & \strut \hfil \quad # \quad \hfil \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & 61 & & - & & 3 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & 20 & & 3 & & 1 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & 1 & & 20 & & 0 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} }} $$

Thus,

$$\eqalign{ 1 & = 1 \cdot 61 + (-3) \cdot 20 \cr 1 & = (-3) \cdot 20 \mod{61} \cr}$$

Hence, $20^{-1} = -3 \mod{61}$ . Multiplying $20 x = 13 \mod{61}$ by -3 and simplifying, I obtain

$$\eqalign{ (-3) \cdot 20 x & = (-3) \cdot 13 \mod{61} \cr x & = - 39 \mod{61} \cr x & = 22 \mod{61} \quad\halmos \cr}$$

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

$$6 x = 7 \mod{12}.$$

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

$$2 x = 6 \mod{10}.$$

Bonzo says: "In the last problem, 6 and 12 weren't relatively prime, so you couldn't find $6^{-1} \mod{12}$ 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 $6 x = 7 \mod{12}$ . Then

$$\eqalign{ 2 \cdot 6 x & = 2 \cdot 7 \mod{12} \cr 0 & = 2 \mod{12} \cr}$$

This contradiction shows that the original equation has no solutions.

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

$$\vbox{\offinterlineskip \halign{& \vrule # & \strut \hfil \quad # \quad \hfil \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr & x & & 0 & & 1 & & 2 & & 3 & & 4 & & 5 & & 6 & & 7 & & 8 & & 9 & \cr height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr & $2 x \mod{10}$ & & 0 & & 2 & & 4 & & 6 & & 8 & & 0 & & 2 & & 4 & & 6 & & 8 & \cr height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} }} $$

As the table shows, $x = 3$ and $x = 8$ are solutions, so Bonzo is incorrect.

He's right that $2^{-1} \mod{10}$ is undefined, so you can't multiply both sides by $2^{-1}$ . 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

Contact information

Bruce Ikenaga's Home Page

Copyright 2020 by Bruce Ikenaga