appendix-2.ipynb

Kernel:

%%html
<link href="http://mathbook.pugetsound.edu/beta/mathbook-content.css" rel="stylesheet" type="text/css" />
<link href="https://aimath.org/mathbook/mathbook-add-on.css" rel="stylesheet" type="text/css" />
<style>.subtitle {font-size:medium; display:block}</style>
<link href="https://fonts.googleapis.com/css?family=Open+Sans:400,400italic,600,600italic" rel="stylesheet" type="text/css" />
<link href="https://fonts.googleapis.com/css?family=Inconsolata:400,700&subset=latin,latin-ext" rel="stylesheet" type="text/css" /><!-- Hide this cell. -->
<script>
var cell = $(".container .cell").eq(0), ia = cell.find(".input_area")
if (cell.find(".toggle-button").length == 0) {
ia.after(
    $('<button class="toggle-button">Toggle hidden code</button>').click(
        function (){ ia.toggle() }
        )
    )
ia.hide()
}
</script>

Important: to view this notebook properly you will need to execute the cell above, which assumes you have an Internet connection. It should already be selected, or place your cursor anywhere above to select. Then press the "Run" button in the menu bar above (the right-pointing arrowhead), or press Shift-Enter on your keyboard.

ParseError: KaTeX parse error: \newcommand{\lt} attempting to redefine \lt; use \renewcommand

AppendixBHints and Solutions to Selected Exercises

Exercises1.3Exercises

Exercise1

Suppose that

$$\begin{align*} A & = \{ x : x \in \mathbb N \text{ and } x \text{ is even} \},\\ B & = \{x : x \in \mathbb N \text{ and } x \text{ is prime}\},\\ C & = \{ x : x \in \mathbb N \text{ and } x \text{ is a multiple of 5}\}. \end{align*}$$

Describe each of the following sets.

1. $A \cap B$

2. $B \cap C$

3. $A \cup B$

4. $A \cap (B \cup C)$

Hint

(a) $A \cap B = \{ 2 \}\text{;}$ (b) $B \cap C = \{ 5 \}\text{.}$

Exercise2

If $A = \{ a, b, c \}\text{,}$ $B = \{ 1, 2, 3 \}\text{,}$ $C = \{ x \}\text{,}$ and $D = \emptyset\text{,}$ list all of the elements in each of the following sets.

1. $A \times B$

2. $B \times A$

3. $A \times B \times C$

4. $A \times D$

Hint

(a) $A \times B = \{ (a,1), (a,2), (a,3), (b,1), (b,2), (b,3), (c,1), (c,2), (c,3) \}\text{;}$ (d) $A \times D = \emptyset\text{.}$

Exercise6

Prove $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\text{.}$

Hint

If $x \in A \cup (B \cap C)\text{,}$ then either $x \in A$ or $x \in B \cap C\text{.}$ Thus, $x \in A \cup B$ and $A \cup C\text{.}$ Hence, $x \in (A \cup B) \cap (A \cup C)\text{.}$ Therefore, $A \cup (B \cap C) \subset (A \cup B) \cap (A \cup C)\text{.}$ Conversely, if $x \in (A \cup B) \cap (A \cup C)\text{,}$ then $x \in A \cup B$ and $A \cup C\text{.}$ Thus, $x \in A$ or $x$ is in both $B$ and $C\text{.}$ So $x \in A \cup (B \cap C)$ and therefore $(A \cup B) \cap (A \cup C) \subset A \cup (B \cap C)\text{.}$ Hence, $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\text{.}$

Exercise10

Prove $A \cup B = (A \cap B) \cup (A \setminus B) \cup (B \setminus A)\text{.}$

Hint

$(A \cap B) \cup (A \setminus B) \cup (B \setminus A) = (A \cap B) \cup (A \cap B') \cup (B \cap A') = [A \cap (B \cup B')] \cup (B \cap A') = A \cup (B \cap A') = (A \cup B) \cap (A \cup A') = A \cup B\text{.}$

Exercise14

Prove $A \setminus (B \cup C) = (A \setminus B) \cap (A \setminus C)\text{.}$

Hint

$A \setminus (B \cup C) = A \cap (B \cup C)' = (A \cap A) \cap (B' \cap C') = (A \cap B') \cap (A \cap C') = (A \setminus B) \cap (A \setminus C)\text{.}$

Exercise17

Which of the following relations $f: {\mathbb Q} \rightarrow {\mathbb Q}$ define a mapping? In each case, supply a reason why $f$ is or is not a mapping.

1. $\displaystyle f(p/q) = \frac{p+ 1}{p - 2}$

2. $\displaystyle f(p/q) = \frac{3p}{3q}$

3. $\displaystyle f(p/q) = \frac{p+q}{q^2}$

4. $\displaystyle f(p/q) = \frac{3 p^2}{7 q^2} - \frac{p}{q}$

Hint

(a) Not a map since $f(2/3)$ is undefined; (b) this is a map; (c) not a map, since $f(1/2) = 3/4$ but $f(2/4)=3/8\text{;}$ (d) this is a map.

Exercise18

Determine which of the following functions are one-to-one and which are onto. If the function is not onto, determine its range.

1. $f: {\mathbb R} \rightarrow {\mathbb R}$ defined by $f(x) = e^x$

2. $f: {\mathbb Z} \rightarrow {\mathbb Z}$ defined by $f(n) = n^2 + 3$

3. $f: {\mathbb R} \rightarrow {\mathbb R}$ defined by $f(x) = \sin x$

4. $f: {\mathbb Z} \rightarrow {\mathbb Z}$ defined by $f(x) = x^2$

Hint

(a) $f$ is one-to-one but not onto. $f({\mathbb R} ) = \{ x \in {\mathbb R} : x \gt 0 \}\text{.}$ (c) $f$ is neither one-to-one nor onto. $f(\mathbb R) = \{ x : -1 \leq x \leq 1 \}\text{.}$

Exercise20

1. Define a function $f: {\mathbb N} \rightarrow {\mathbb N}$ that is one-to-one but not onto.

2. Define a function $f: {\mathbb N} \rightarrow {\mathbb N}$ that is onto but not one-to-one.

Hint

(a) $f(n) = n + 1\text{.}$

Exercise22

Let $f : A \rightarrow B$ and $g : B \rightarrow C$ be maps.

1. If $f$ and $g$ are both one-to-one functions, show that $g \circ f$ is one-to-one.

2. If $g \circ f$ is onto, show that $g$ is onto.

3. If $g \circ f$ is one-to-one, show that $f$ is one-to-one.

4. If $g \circ f$ is one-to-one and $f$ is onto, show that $g$ is one-to-one.

5. If $g \circ f$ is onto and $g$ is one-to-one, show that $f$ is onto.

Hint

(a) Let $x, y \in A\text{.}$ Then $g(f(x)) = (g \circ f)(x) = (g \circ f)(y) = g(f(y))\text{.}$ Thus, $f(x) = f(y)$ and $x = y\text{,}$ so $g \circ f$ is one-to-one. (b) Let $c \in C\text{,}$ then $c = (g \circ f)(x) = g(f(x))$ for some $x \in A\text{.}$ Since $f(x) \in B\text{,}$ $g$ is onto.

Exercise23

Define a function on the real numbers by

$$\begin{equation*} f(x) = \frac{x + 1}{x - 1}. \end{equation*}$$

What are the domain and range of $f\text{?}$ What is the inverse of $f\text{?}$ Compute $f \circ f^{-1}$ and $f^{-1} \circ f\text{.}$

Hint

$f^{-1}(x) = (x+1)/(x-1)\text{.}$

Exercise24

Let $f: X \rightarrow Y$ be a map with $A_1, A_2 \subset X$ and $B_1, B_2 \subset Y\text{.}$

1. Prove $f( A_1 \cup A_2 ) = f( A_1) \cup f( A_2 )\text{.}$

2. Prove $f( A_1 \cap A_2 ) \subset f( A_1) \cap f( A_2 )\text{.}$ Give an example in which equality fails.

3. Prove $f^{-1}( B_1 \cup B_2 ) = f^{-1}( B_1) \cup f^{-1}(B_2 )\text{,}$ where

   $$\begin{equation*} f^{-1}(B) = \{ x \in X : f(x) \in B \}. \end{equation*}$$

4. Prove $f^{-1}( B_1 \cap B_2 ) = f^{-1}( B_1) \cap f^{-1}( B_2 )\text{.}$

5. Prove $f^{-1}( Y \setminus B_1 ) = X \setminus f^{-1}( B_1)\text{.}$

Hint

(a) Let $y \in f(A_1 \cup A_2)\text{.}$ Then there exists an $x \in A_1 \cup A_2$ such that $f(x) = y\text{.}$ Hence, $y \in f(A_1)$ or $f(A_2) \text{.}$ Therefore, $y \in f(A_1) \cup f(A_2)\text{.}$ Consequently, $f(A_1 \cup A_2) \subset f(A_1) \cup f(A_2)\text{.}$ Conversely, if $y \in f(A_1) \cup f(A_2)\text{,}$ then $y \in f(A_1)$ or $f(A_2)\text{.}$ Hence, there exists an $x$ in $A_1$ or $A_2$ such that $f(x) = y\text{.}$ Thus, there exists an $x \in A_1 \cup A_2$ such that $f(x) = y\text{.}$ Therefore, $f(A_1) \cup f(A_2) \subset f(A_1 \cup A_2)\text{,}$ and $f(A_1 \cup A_2) = f(A_1) \cup f(A_2)\text{.}$

Exercise25

Determine whether or not the following relations are equivalence relations on the given set. If the relation is an equivalence relation, describe the partition given by it. If the relation is not an equivalence relation, state why it fails to be one.

1. $x \sim y$ in ${\mathbb R}$ if $x \geq y$

2. $m \sim n$ in ${\mathbb Z}$ if $mn > 0$

3. $x \sim y$ in ${\mathbb R}$ if $|x - y| \leq 4$

4. $m \sim n$ in ${\mathbb Z}$ if $m \equiv n \pmod{6}$

Hint

(a) The relation fails to be symmetric. (b) The relation is not reflexive, since 0 is not equivalent to itself. (c) The relation is not transitive.

Exercise28

Find the error in the following argument by providing a counterexample. “The reflexive property is redundant in the axioms for an equivalence relation. If $x \sim y\text{,}$ then $y \sim x$ by the symmetric property. Using the transitive property, we can deduce that $x \sim x\text{.}$”

Hint

Let $X = {\mathbb N} \cup \{ \sqrt{2}\, \}$ and define $x \sim y$ if $x + y \in {\mathbb N}\text{.}$

Exercises2.3Exercises

Exercise1

Prove that

$$\begin{equation*} 1^2 + 2^2 + \cdots + n^2 = \frac{n(n + 1)(2n + 1)}{6} \end{equation*}$$

for $n \in {\mathbb N}\text{.}$

Hint

The base case, $S(1): [1(1 + 1)(2(1) + 1)]/6 = 1 = 1^2$ is true. Assume that $S(k): 1^2 + 2^2 + \cdots + k^2 = [k(k + 1)(2k + 1)]/6$ is true. Then

$$\begin{align*} 1^2 + 2^2 + \cdots + k^2 + (k + 1)^2 & = [k(k + 1)(2k + 1)]/6 + (k + 1)^2\\ & = [(k + 1)((k + 1) + 1)(2(k + 1) + 1)]/6, \end{align*}$$

and so $S(k + 1)$ is true. Thus, $S(n)$ is true for all positive integers $n\text{.}$

Exercise3

Prove that $n! \gt 2^n$ for $n \geq 4\text{.}$

Hint

The base case, $S(4): 4! = 24 \gt 16 =2^4$ is true. Assume $S(k): k! \gt 2^k$ is true. Then $(k + 1)! = k! (k + 1) \gt 2^k \cdot 2 = 2^{k + 1}\text{,}$ so $S(k + 1)$ is true. Thus, $S(n)$ is true for all positive integers $n\text{.}$

Exercise8

Prove the Leibniz rule for $f^{(n)} (x)\text{,}$ where $f^{(n)}$ is the $n$th derivative of $f\text{;}$ that is, show that

$$\begin{equation*} (fg)^{(n)}(x) = \sum_{k = 0}^{n} \binom{n}{k} f^{(k)}(x) g^{(n - k)}(x). \end{equation*}$$

Hint

Follow the proof in Example 2.4.

Exercise11

If $x$ is a nonnegative real number, then show that $(1 + x)^n - 1 \geq nx$ for $n = 0, 1, 2, \ldots\text{.}$

Hint

The base case, $S(0): (1 + x)^0 - 1 = 0 \geq 0 = 0 \cdot x$ is true. Assume $S(k): (1 + x)^k -1 \geq kx$ is true. Then

$$\begin{align*} (1 + x)^{k + 1} - 1 & = (1 + x)(1 + x)^k -1\\ & = (1 + x)^k + x(1 + x)^k - 1\\ & \geq kx + x(1 + x)^k\\ & \geq kx + x\\ & = (k + 1)x, \end{align*}$$

so $S(k + 1)$ is true. Therefore, $S(n)$ is true for all positive integers $n\text{.}$

Exercise17Fibonacci Numbers

The Fibonacci numbers are

$$\begin{equation*} 1, 1, 2, 3, 5, 8, 13, 21, \ldots. \end{equation*}$$

We can define them inductively by $f_1 = 1\text{,}$ $f_2 = 1\text{,}$ and $f_{n + 2} = f_{n + 1} + f_n$ for $n \in {\mathbb N}\text{.}$

1. Prove that $f_n \lt 2^n\text{.}$

2. Prove that $f_{n + 1} f_{n - 1} = f^2_n + (-1)^n\text{,}$ $n \geq 2\text{.}$

3. Prove that $f_n = [(1 + \sqrt{5}\, )^n - (1 - \sqrt{5}\, )^n]/ 2^n \sqrt{5}\text{.}$

4. Show that $\lim_{n \rightarrow \infty} f_n / f_{n + 1} = (\sqrt{5} - 1)/2\text{.}$

5. Prove that $f_n$ and $f_{n + 1}$ are relatively prime.

Hint

For (a) and (b) use mathematical induction. (c) Show that $f_1 = 1\text{,}$ $f_2 = 1\text{,}$ and $f_{n + 2} = f_{n + 1} + f_n\text{.}$ (d) Use part (c). (e) Use part (b) and Exercise 2.3.16.

Exercise19

Let $x, y \in {\mathbb N}$ be relatively prime. If $xy$ is a perfect square, prove that $x$ and $y$ must both be perfect squares.

Hint

Use the Fundamental Theorem of Arithmetic.

Exercise23

Define the of two nonzero integers $a$ and $b\text{,}$ denoted by $\lcm(a,b)\text{,}$ to be the nonnegative integer $m$ such that both $a$ and $b$ divide $m\text{,}$ and if $a$ and $b$ divide any other integer $n\text{,}$ then $m$ also divides $n\text{.}$ Prove there exists a unique least common multiple for any two integers $a$ and $b\text{.}$

Hint

Use the Principle of Well-Ordering and the division algorithm.

Exercise27

Let $a, b, c \in {\mathbb Z}\text{.}$ Prove that if $\gcd(a,b) = 1$ and $a \mid bc\text{,}$ then $a \mid c\text{.}$

Hint

Since $\gcd(a,b) = 1\text{,}$ there exist integers $r$ and $s$ such that $ar + bs = 1\text{.}$ Thus, $acr + bcs = c\text{.}$

Exercise29

Prove that there are an infinite number of primes of the form $6n + 5\text{.}$

Hint

Every prime must be of the form 2, 3, $6n + 1\text{,}$ or $6n + 5\text{.}$ Suppose there are only finitely many primes of the form $6k + 5\text{.}$

Exercises3.4Exercises

Exercise1

Find all $x \in {\mathbb Z}$ satisfying each of the following equations.

1. $3x \equiv 2 \pmod{7}$

2. $5x + 1 \equiv 13 \pmod{23}$

3. $5x + 1 \equiv 13 \pmod{26}$

4. $9x \equiv 3 \pmod{5}$

5. $5x \equiv 1 \pmod{6}$

6. $3x \equiv 1 \pmod{6}$

Hint

(a) $3 + 7 \mathbb Z = \{ \ldots, -4, 3, 10, \ldots \}\text{;}$ (c) $18 + 26 \mathbb Z\text{;}$ (e) $5 + 6 \mathbb Z\text{.}$

Exercise2

Which of the following multiplication tables defined on the set $G = \{ a, b, c, d \}$ form a group? Support your answer in each case.

1. $$\begin{equation*} \begin{array}{c|cccc} \circ & a & b & c & d \\ \hline a & a & c & d & a \\ b & b & b & c & d \\ c & c & d & a & b \\ d & d & a & b & c \end{array} \end{equation*}$$
2. $$\begin{equation*} \begin{array}{c|cccc} \circ & a & b & c & d \\ \hline a & a & b & c & d \\ b & b & a & d & c \\ c & c & d & a & b \\ d & d & c & b & a \end{array} \end{equation*}$$
3. $$\begin{equation*} \begin{array}{c|cccc} \circ & a & b & c & d \\ \hline a & a & b & c & d \\ b & b & c & d & a \\ c & c & d & a & b \\ d & d & a & b & c \end{array} \end{equation*}$$
4. $$\begin{equation*} \begin{array}{c|cccc} \circ & a & b & c & d \\ \hline a & a & b & c & d \\ b & b & a & c & d \\ c & c & b & a & d \\ d & d & d & b & c \end{array} \end{equation*}$$

Hint

(a) Not a group; (c) a group.

Exercise6

Give a multiplication table for the group $U(12)\text{.}$

Hint

$$\begin{equation*} \begin{array}{c|cccc} \cdot & 1 & 5 & 7 & 11 \\ \hline 1 & 1 & 5 & 7 & 11 \\ 5 & 5 & 1 & 11 & 7 \\ 7 & 7 & 11 & 1 & 5 \\ 11 & 11 & 7 & 5 & 1 \end{array} \end{equation*}$$

Exercise8

Give an example of two elements $A$ and $B$ in $GL_2({\mathbb R})$ with $AB \neq BA\text{.}$

Hint

Pick two matrices. Almost any pair will work.

Exercise15

Prove or disprove that every group containing six elements is abelian.

Hint

There is a nonabelian group containing six elements.

Exercise16

Give a specific example of some group $G$ and elements $g, h \in G$ where $(gh)^n \neq g^nh^n\text{.}$

Hint

Look at the symmetry group of an equilateral triangle or a square.

Exercise17

Give an example of three different groups with eight elements. Why are the groups different?

Hint

The are five different groups of order 8.

Exercise18

Show that there are $n!$ permutations of a set containing $n$ items.

Hint

Let

$$\begin{equation*} \sigma = \begin{pmatrix} 1 & 2 & \cdots & n \\ a_1 & a_2 & \cdots & a_n \end{pmatrix} \end{equation*}$$

be in $S_n\text{.}$ All of the $a_i$s must be distinct. There are $n$ ways to choose $a_1\text{,}$ $n-1$ ways to choose $a_2\text{,}$ $\ldots\text{,}$ 2 ways to choose $a_{n - 1}\text{,}$ and only one way to choose $a_n\text{.}$ Therefore, we can form $\sigma$ in $n(n - 1) \cdots 2 \cdot 1 = n!$ ways.

Exercise25

Let $a$ and $b$ be elements in a group $G\text{.}$ Prove that $ab^na^{-1} = (aba^{-1})^n$ for $n \in \mathbb Z\text{.}$

Hint

$$\begin{align*} (aba^{-1})^n & = (aba^{-1})(aba^{-1}) \cdots (aba^{-1})\\ & = ab(aa^{-1})b(aa^{-1})b \cdots b(aa^{-1})ba^{-1}\\ & = ab^na^{-1}. \end{align*}$$

Exercise31

Show that if $a^2 = e$ for all elements $a$ in a group $G\text{,}$ then $G$ must be abelian.

Hint

Since $abab = (ab)^2 = e = a^2 b^2 = aabb\text{,}$ we know that $ba = ab\text{.}$

Exercise35

Find all the subgroups of the symmetry group of an equilateral triangle.

Hint

$H_1 = \{ \identity \}\text{,}$ $H_2 = \{ \identity, \rho_1, \rho_2 \}\text{,}$ $H_3 = \{ \identity, \mu_1 \}\text{,}$ $H_4 = \{ \identity, \mu_2 \}\text{,}$ $H_5 = \{ \identity, \mu_3 \}\text{,}$ $S_3\text{.}$

Exercise41

Prove that

$$\begin{equation*} G = \{ a + b \sqrt{2} : a, b \in {\mathbb Q} \text{ and } a \text{ and } b \text{ are not both zero} \} \end{equation*}$$

is a subgroup of ${\mathbb R}^{\ast}$ under the group operation of multiplication.

Hint

The identity of $G$ is $1 = 1 + 0 \sqrt{2}\text{.}$ Since $(a + b \sqrt{2}\, )(c + d \sqrt{2}\, ) = (ac + 2bd) + (ad + bc)\sqrt{2}\text{,}$ $G$ is closed under multiplication. Finally, $(a + b \sqrt{2}\, )^{-1} = a/(a^2 - 2b^2) - b\sqrt{2}/(a^2 - 2 b^2)\text{.}$

Exercise46

Prove or disprove: If $H$ and $K$ are subgroups of a group $G\text{,}$ then $H \cup K$ is a subgroup of $G\text{.}$

Hint

Look at $S_3\text{.}$

Exercise49

Let $a$ and $b$ be elements of a group $G\text{.}$ If $a^4 b = ba$ and $a^3 = e\text{,}$ prove that $ab = ba\text{.}$

Hint

$b a = a^4 b = a^3 a b = ab$

Exercises4.4Exercises

Exercise1

Prove or disprove each of the following statements.

1. All of the generators of ${\mathbb Z}_{60}$ are prime.

2. $U(8)$ is cyclic.

3. ${\mathbb Q}$ is cyclic.

4. If every proper subgroup of a group $G$ is cyclic, then $G$ is a cyclic group.

5. A group with a finite number of subgroups is finite.

Hint

(a) False; (c) false; (e) true.

Exercise2

Find the order of each of the following elements.

1. $5 \in {\mathbb Z}_{12}$

2. $\sqrt{3} \in {\mathbb R}$

3. $\sqrt{3} \in {\mathbb R}^\ast$

4. $-i \in {\mathbb C}^\ast$

5. 72 in ${\mathbb Z}_{240}$

6. 312 in ${\mathbb Z}_{471}$

Hint

(a) 12; (c) infinite; (e) 10.

Exercise3

List all of the elements in each of the following subgroups.

1. The subgroup of ${\mathbb Z}$ generated by 7

2. The subgroup of ${\mathbb Z}_{24}$ generated by 15

3. All subgroups of ${\mathbb Z}_{12}$

4. All subgroups of ${\mathbb Z}_{60}$

5. All subgroups of ${\mathbb Z}_{13}$

6. All subgroups of ${\mathbb Z}_{48}$

7. The subgroup generated by 3 in $U(20)$

8. The subgroup generated by 5 in $U(18)$

9. The subgroup of ${\mathbb R}^\ast$ generated by 7

10. The subgroup of ${\mathbb C}^\ast$ generated by $i$ where $i^2 = -1$

11. The subgroup of ${\mathbb C}^\ast$ generated by $2i$

12. The subgroup of ${\mathbb C}^\ast$ generated by $(1 + i) / \sqrt{2}$

13. The subgroup of ${\mathbb C}^\ast$ generated by $(1 + \sqrt{3}\, i) / 2$

Hint

(a) $7 {\mathbb Z} = \{ \ldots, -7, 0, 7, 14, \ldots \}\text{;}$ (b) $\{ 0, 3, 6, 9, 12, 15, 18, 21 \}\text{;}$ (c) $\{ 0 \}\text{,}$ $\{ 0, 6 \}\text{,}$ $\{ 0, 4, 8 \}\text{,}$ $\{ 0, 3, 6, 9 \}\text{,}$ $\{ 0, 2, 4, 6, 8, 10 \}\text{;}$ (g) $\{ 1, 3, 7, 9 \}\text{;}$ (j) $\{ 1, -1, i, -i \}\text{.}$

Exercise4

Find the subgroups of $GL_2( {\mathbb R })$ generated by each of the following matrices.

1. $\displaystyle \begin{pmatrix} 0 & 1 \\ -1 & 0 \end{pmatrix}$

2. $\displaystyle \begin{pmatrix} 0 & 1/3 \\ 3 & 0 \end{pmatrix}$

3. $\displaystyle \begin{pmatrix} 1 & -1 \\ 1 & 0 \end{pmatrix}$

4. $\displaystyle \begin{pmatrix} 1 & -1 \\ 0 & 1 \end{pmatrix}$

5. $\displaystyle \begin{pmatrix} 1 & -1 \\ -1 & 0 \end{pmatrix}$

6. $\displaystyle \begin{pmatrix} \sqrt{3}/ 2 & 1/2 \\ -1/2 & \sqrt{3}/2 \end{pmatrix}$

Hint

(a)

$$\begin{equation*} \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}, \begin{pmatrix} -1 & 0 \\ 0 & -1 \end{pmatrix}, \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}, \begin{pmatrix} 0 & 1 \\ -1 & 0 \end{pmatrix}. \end{equation*}$$

(c)

$$\begin{equation*} \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}, \begin{pmatrix} 1 & -1 \\ 1 & 0 \end{pmatrix}, \begin{pmatrix} -1 & 1 \\ -1 & 0 \end{pmatrix}, \\ \begin{pmatrix} 0 & 1 \\ -1 & 1 \end{pmatrix}, \begin{pmatrix} 0 & -1 \\ 1 & -1 \end{pmatrix}, \begin{pmatrix} -1 & 0 \\ 0 & -1 \end{pmatrix}. \end{equation*}$$

Exercise10

Find all elements of finite order in each of the following groups. Here the “$\ast$” indicates the set with zero removed.

1. ${\mathbb Z}$

2. ${\mathbb Q}^\ast$

3. ${\mathbb R}^\ast$

Hint

(a) $0\text{;}$ (b) $1, -1\text{.}$

Exercise11

If $a^{24} =e$ in a group $G\text{,}$ what are the possible orders of $a\text{?}$

Hint

1, 2, 3, 4, 6, 8, 12, 24.

Exercise15

Evaluate each of the following.

1. $(3-2i)+ (5i-6)$

2. $(4-5i)-\overline{(4i -4)}$

3. $(5-4i)(7+2i)$

4. $(9-i) \overline{(9-i)}$

5. $i^{45}$

6. $(1+i)+\overline{(1+i)}$

Hint

(a) $-3 + 3i\text{;}$ (c) $43- 18i\text{;}$ (e) $i$

Exercise16

Convert the following complex numbers to the form $a + bi\text{.}$

1. $2 \cis(\pi / 6 )$

2. $5 \cis(9\pi/4)$

3. $3 \cis(\pi)$

4. $\cis(7\pi/4) /2$

Hint

(a) $\sqrt{3} + i\text{;}$ (c) $-3\text{.}$

Exercise17

Change the following complex numbers to polar representation.

1. $1-i$

2. $-5$

3. $2+2i$

4. $\sqrt{3} + i$

5. $-3i$

6. $2i + 2 \sqrt{3}$

Hint

(a) $\sqrt{2} \cis( 7 \pi /4)\text{;}$ (c) $2 \sqrt{2} \cis( \pi /4)\text{;}$ (e) $3 \cis(3 \pi/2)\text{.}$

Exercise18

Calculate each of the following expressions.

1. $(1+i)^{-1}$

2. $(1 - i)^{6}$

3. $(\sqrt{3} + i)^{5}$

4. $(-i)^{10}$

5. $((1-i)/2)^{4}$

6. $(-\sqrt{2} - \sqrt{2}\, i)^{12}$

7. $(-2 + 2i)^{-5}$

Hint

(a) $(1 - i)/2\text{;}$ (c) $16(i - \sqrt{3}\, )\text{;}$ (e) $-1/4\text{.}$

Exercise22

Calculate each of the following.

1. $292^{3171} \pmod{ 582}$

2. $2557^{ 341} \pmod{ 5681}$

3. $2071^{ 9521} \pmod{ 4724}$

4. $971^{ 321} \pmod{ 765}$

Hint

(a) 292; (c) 1523.

Exercise27

If $g$ and $h$ have orders 15 and 16 respectively in a group $G\text{,}$ what is the order of $\langle g \rangle \cap \langle h \rangle \text{?}$

Hint

$|\langle g \rangle \cap \langle h \rangle| = 1\text{.}$

Exercise31

Let $G$ be an abelian group. Show that the elements of finite order in $G$ form a subgroup. This subgroup is called the of $G\text{.}$

Hint

The identity element in any group has finite order. Let $g, h \in G$ have orders $m$ and $n\text{,}$ respectively. Since $(g^{-1})^m = e$ and $(gh)^{mn} = e\text{,}$ the elements of finite order in $G$ form a subgroup of $G\text{.}$

Exercise37

Prove that if $G$ has no proper nontrivial subgroups, then $G$ is a cyclic group.

Hint

If $g$ is an element distinct from the identity in $G\text{,}$ $g$ must generate $G\text{;}$ otherwise, $\langle g \rangle$ is a nontrivial proper subgroup of $G\text{.}$

Exercises5.3Exercises

Exercise1

Write the following permutations in cycle notation.

1. $$\begin{equation*} \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 4 & 1 & 5 & 3 \end{pmatrix} \end{equation*}$$
2. $$\begin{equation*} \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 2 & 5 & 1 & 3 \end{pmatrix} \end{equation*}$$
3. $$\begin{equation*} \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 5 & 1 & 4 & 2 \end{pmatrix} \end{equation*}$$
4. $$\begin{equation*} \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 4 & 3 & 2 & 5 \end{pmatrix} \end{equation*}$$

Hint

(a) $(12453)\text{;}$ (c) $(13)(25)\text{.}$

Exercise2

Compute each of the following.

1. $(1345)(234)$

2. $(12)(1253)$

3. $(143)(23)(24)$

4. $(1423)(34)(56)(1324)$

5. $(1254)(13)(25)$

6. $(1254) (13)(25)^2$

7. $(1254)^{-1} (123)(45) (1254)$

8. $(1254)^2 (123)(45)$

9. $(123)(45) (1254)^{-2}$

10. $(1254)^{100}$

11. $|(1254)|$

12. $|(1254)^2|$

13. $(12)^{-1}$

14. $(12537)^{-1}$

15. $[(12)(34)(12)(47)]^{-1}$

16. $[(1235)(467)]^{-1}$

Hint

(a) $(135)(24)\text{;}$ (c) $(14)(23)\text{;}$ (e) $(1324)\text{;}$ (g) $(134)(25)\text{;}$ (n) $(17352)\text{.}$

Exercise3

Express the following permutations as products of transpositions and identify them as even or odd.

1. $(14356)$

2. $(156)(234)$

3. $(1426)(142)$

4. $(17254)(1423)(154632)$

5. $(142637)$

Hint

(a) $(16)(15)(13)(14)\text{;}$ (c) $(16)(14)(12)\text{.}$

Exercise4

Find $(a_1, a_2, \ldots, a_n)^{-1}\text{.}$

Hint

$(a_1, a_2, \ldots, a_n)^{-1} = (a_1, a_{n}, a_{n-1}, \ldots, a_2)$

Exercise5

List all of the subgroups of $S_4\text{.}$ Find each of the following sets.

1. $\{ \sigma \in S_4 : \sigma(1) = 3 \}$

2. $\{ \sigma \in S_4 : \sigma(2) = 2 \}$

3. $\{ \sigma \in S_4 : \sigma(1) = 3$ and $\sigma(2) = 2 \}$

Are any of these sets subgroups of $S_4\text{?}$

Hint

(a) $\{ (13), (13)(24), (132), (134), (1324), (1342) \}$ is not a subgroup.

Exercise8

Show that $A_{10}$ contains an element of order 15.

Hint

$(12345)(678)\text{.}$

Exercise11

What are the possible cycle structures of elements of $A_5\text{?}$ What about $A_6\text{?}$

Hint

Permutations of the form

$$\begin{equation*} (1), (a_1, a_2)(a_3, a_4), (a_1, a_2, a_3), (a_1, a_2, a_3, a_4, a_5) \end{equation*}$$

are possible for $A_5\text{.}$

Exercise17

Prove that $S_n$ is nonabelian for $n \geq 3\text{.}$

Hint

Calculate $(123)(12)$ and $(12)(123)\text{.}$

Exercise25

Prove that in $A_n$ with $n \geq 3\text{,}$ any permutation is a product of cycles of length 3.

Hint

Consider the cases $(ab)(bc)$ and $(ab)(cd)\text{.}$

Exercise30

Let $\tau = (a_1, a_2, \ldots, a_k)$ be a cycle of length $k\text{.}$

1. Prove that if $\sigma$ is any permutation, then

   $$\begin{equation*} \sigma \tau \sigma^{-1 } = ( \sigma(a_1), \sigma(a_2), \ldots, \sigma(a_k)) \end{equation*}$$

   is a cycle of length $k\text{.}$

2. Let $\mu$ be a cycle of length $k\text{.}$ Prove that there is a permutation $\sigma$ such that $\sigma \tau \sigma^{-1 } = \mu\text{.}$

Hint

For (a), show that $\sigma \tau \sigma^{-1 }(\sigma(a_i)) = \sigma(a_{i + 1})\text{.}$

Exercises6.4Exercises

Exercise1

Suppose that $G$ is a finite group with an element $g$ of order 5 and an element $h$ of order 7. Why must $|G| \geq 35\text{?}$

Hint

The order of $g$ and the order $h$ must both divide the order of $G\text{.}$

Exercise2

Suppose that $G$ is a finite group with 60 elements. What are the orders of possible subgroups of $G\text{?}$

Hint

The possible orders must divide 60.

Exercise3

Prove or disprove: Every subgroup of the integers has finite index.

Hint

This is true for every proper nontrivial subgroup.

Exercise4

Prove or disprove: Every subgroup of the integers has finite order.

Hint

False.

Exercise5

List the left and right cosets of the subgroups in each of the following.

1. $\langle 8 \rangle$ in ${\mathbb Z}_{24}$

2. $\langle 3 \rangle$ in $U(8)$

3. $3 {\mathbb Z}$ in ${\mathbb Z}$

4. $A_4$ in $S_4$

5. $A_n$ in $S_n$

6. $D_4$ in $S_4$

7. ${\mathbb T}$ in ${\mathbb C}^\ast$

8. $H = \{ (1), (123), (132) \}$ in $S_4$

Hint

(a) $\langle 8 \rangle\text{,}$ $1 + \langle 8 \rangle\text{,}$ $2 + \langle 8 \rangle\text{,}$ $3 + \langle 8 \rangle\text{,}$ $4 + \langle 8 \rangle\text{,}$ $5 + \langle 8 \rangle\text{,}$ $6 + \langle 8 \rangle\text{,}$ and $7 + \langle 8 \rangle\text{;}$ (c) $3 {\mathbb Z}\text{,}$ $1 + 3 {\mathbb Z}\text{,}$ and $2 + 3 {\mathbb Z}\text{.}$

Exercise7

Verify Euler's Theorem for $n = 15$ and $a = 4\text{.}$

Hint

$4^{\phi(15)} \equiv 4^8 \equiv 1 \pmod{15}\text{.}$

Exercise12

If $ghg^{-1} \in H$ for all $g \in G$ and $h \in H\text{,}$ show that right cosets are identical to left cosets. That is, show that $gH = Hg$ for all $g \in G\text{.}$

Hint

Let $g_1 \in gH\text{.}$ Show that $g_1 \in Hg$ and thus $gH \subset Hg\text{.}$

Exercise19

Let $H$ and $K$ be subgroups of a group $G\text{.}$ Prove that $gH \cap gK$ is a coset of $H \cap K$ in $G\text{.}$

Hint

Show that $g(H \cap K) = gH \cap gK\text{.}$

Exercise22

Let $n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}\text{,}$ where $p_1, p_2, \ldots, p_k$ are distinct primes. Prove that

$$\begin{equation*} \phi(n) = n \left( 1 - \frac{1}{p_1} \right) \left( 1 - \frac{1}{p_2} \right)\cdots \left( 1 - \frac{1}{p_k} \right). \end{equation*}$$

Hint

If $\gcd(m,n) = 1\text{,}$ then $\phi(mn) = \phi(m)\phi(n)$ (Exercise 2.3.26 in Chapter 2).

Exercises7.3Exercises

Exercise1

Encode IXLOVEXMATH using the cryptosystem in Example 1.

Hint

LAORYHAPDWK

Exercise3

Assuming that monoalphabetic code was used to encode the following secret message, what was the original message?

APHUO EGEHP PEXOV FKEUH CKVUE CHKVE APHUO
EGEHU EXOVL EXDKT VGEFT EHFKE UHCKF TZEXO
VEZDT TVKUE XOVKV ENOHK ZFTEH TEHKQ LEROF
PVEHP PEXOV ERYKP GERYT GVKEG XDRTE RGAGA

What is the significance of this message in the history of cryptography?

Hint

Hint: V = E, E = X (also used for spaces and punctuation), K = R.

Exercise4

What is the total number of possible monoalphabetic cryptosystems? How secure are such cryptosystems?

Hint

$26! - 1$

Exercise7

Encrypt each of the following RSA messages $x$ so that $x$ is divided into blocks of integers of length 2; that is, if $x = 142528\text{,}$ encode 14, 25, and 28 separately.

1. $n = 3551, E = 629, x = 31$

2. $n = 2257, E = 47, x = 23$

3. $n = 120979, E = 13251, x = 142371$

4. $n = 45629, E = 781, x = 231561$

Hint

(a) 2791; (c) 112135 25032 442.

Exercise9

Decrypt each of the following RSA messages $y\text{.}$

1. $n = 3551, D = 1997, y = 2791$

2. $n = 5893, D = 81, y = 34$

3. $n = 120979, D = 27331, y = 112135$

4. $n = 79403, D = 671, y = 129381$

Hint

(a) 31; (c) 14.

Exercise10

For each of the following encryption keys $(n, E)$ in the RSA cryptosystem, compute $D\text{.}$

1. $(n, E) = (451, 231)$

2. $(n, E) = (3053, 1921)$

3. $(n, E) = (37986733, 12371)$

4. $(n, E) = (16394854313, 34578451)$

Hint

(a) $n = 11 \cdot 41\text{;}$ (c) $n = 8779 \cdot 4327\text{.}$

Exercises8.5Exercises

Exercise2

Without doing any addition, explain why the following set of 4-tuples in ${\mathbb Z}_2^4$ cannot be a group code.

$$\begin{equation*} (0110) \quad (1001) \quad (1010) \quad (1100) \end{equation*}$$

Hint

This cannot be a group code since $(0000) \notin C\text{.}$

Exercise3

Compute the Hamming distances between the following pairs of $n$-tuples.

1. $(011010), (011100)$

2. $(11110101), (01010100)$

3. $(00110), (01111)$

4. $(1001), (0111)$

Hint

(a) 2; (c) 2.

Exercise4

Compute the weights of the following $n$-tuples.

1. $(011010)$

2. $(11110101)$

3. $(01111)$

4. $(1011)$

Hint

(a) 3; (c) 4.

Exercise6

In each of the following codes, what is the minimum distance for the code? What is the best situation we might hope for in connection with error detection and error correction?

1. $(011010) \; (011100) \; (110111) \; (110000)$

2. $(011100) \; (011011) \; (111011) \; (100011)$ \; $(000000) \; (010101) \; (110100) \; (110011)$

3. $(000000) \; (011100) \; (110101) \; (110001)$

4. $(0110110) \; (0111100) \; (1110000) \; (1111111)$ \; $(1001001) \; (1000011) \; (0001111) \; (0000000)$

Hint

(a) $d_{\min} = 2\text{;}$ (c) $d_{\min} = 1\text{.}$

Exercise7

Compute the null space of each of the following matrices. What type of $(n,k)$-block codes are the null spaces? Can you find a matrix (not necessarily a standard generator matrix) that generates each code? Are your generator matrices unique?

1. $$\begin{equation*} \begin{pmatrix} 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 \end{pmatrix} \end{equation*}$$
2. $$\begin{equation*} \begin{pmatrix} 1 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 1 \end{pmatrix} \end{equation*}$$
3. $$\begin{equation*} \begin{pmatrix} 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 \end{pmatrix} \end{equation*}$$
4. $$\begin{equation*} \begin{pmatrix} 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \end{pmatrix} \end{equation*}$$

Hint

1. $(00000), (00101), (10011), (10110)$

   $$\begin{equation*} G = \begin{pmatrix} 0 & 1 \\ 0 & 0 \\ 1 & 0 \\ 0 & 1 \\ 1 & 1 \end{pmatrix} \end{equation*}$$

2. $(000000), (010111), (101101), (111010)$

   $$\begin{equation*} G = \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ 1 & 0 \\ 1 & 1 \\ 0 & 1 \\ 1 & 1 \end{pmatrix} \end{equation*}$$

Exercise9

Let $C$ be the code obtained from the null space of the matrix

$$\begin{equation*} H = \begin{pmatrix} 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 1 \end{pmatrix}. \end{equation*}$$

Decode the message

$$\begin{equation*} 01111 \quad 10101 \quad 01110 \quad 00011 \end{equation*}$$

if possible.

Hint

Multiple errors occur in one of the received words.

Exercise11

Which matrices are canonical parity-check matrices? For those matrices that are canonical parity-check matrices, what are the corresponding standard generator matrices? What are the error-detection and error-correction capabilities of the code generated by each of these matrices?

1. $$\begin{equation*} \begin{pmatrix} 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 \end{pmatrix} \end{equation*}$$
2. $$\begin{equation*} \begin{pmatrix} 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 1 \end{pmatrix} \end{equation*}$$
3. $$\begin{equation*} \begin{pmatrix} 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \end{pmatrix} \end{equation*}$$
4. $$\begin{equation*} \begin{pmatrix} 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 & 1 \end{pmatrix} \end{equation*}$$

Hint

(a) A canonical parity-check matrix with standard generator matrix

$$\begin{equation*} G = \begin{pmatrix} 1 \\ 1 \\ 0 \\ 0 \\ 1 \end{pmatrix}. \end{equation*}$$

(c) A canonical parity-check matrix with standard generator matrix

$$\begin{equation*} G = \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ 1 & 1 \\ 1 & 0 \end{pmatrix}. \end{equation*}$$

Exercise12

List all possible syndromes for the codes generated by each of the matrices in Exercise 8.5.11.

Hint

(a) All possible syndromes occur.

Exercise15

For each of the following matrices, find the cosets of the corresponding code $C\text{.}$ Give a decoding table for each code if possible.

1. $$\begin{equation*} \begin{pmatrix} 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 \end{pmatrix} \end{equation*}$$
2. $$\begin{equation*} \begin{pmatrix} 0 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 \end{pmatrix} \end{equation*}$$
3. $$\begin{equation*} \begin{pmatrix} 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 \end{pmatrix} \end{equation*}$$
4. $$\begin{equation*} \begin{pmatrix} 1 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 1 & 0 \end{pmatrix} \end{equation*}$$

Hint

(a) $C\text{,}$ $(10000) + C\text{,}$ $(01000) + C\text{,}$ $(00100) + C\text{,}$ $(00010) + C\text{,}$ $(11000) + C\text{,}$ $(01100) + C\text{,}$ $(01010) + C\text{.}$ A decoding table does not exist for $C$ since this is only a single error-detecting code.

Exercise19

Let $C$ be a linear code. Show that either every codeword has even weight or exactly half of the codewords have even weight.

Hint

Let ${\mathbf x} \in C$ have odd weight and define a map from the set of odd codewords to the set of even codewords by ${\mathbf y} \mapsto {\mathbf x} + {\mathbf y}\text{.}$ Show that this map is a bijection.

Exercise23

How many check positions are needed for a single error-correcting code with 20 information positions? With 32 information positions?

Hint

For 20 information positions, at least 6 check bits are needed to ensure an error-correcting code.

Exercises9.3Exercises

Exercise1

Prove that $\mathbb Z \cong n \mathbb Z$ for $n \neq 0\text{.}$

Hint

Every infinite cyclic group is isomorphic to ${\mathbb Z}$ by Theorem 9.7.

Exercise2

Prove that ${\mathbb C}^\ast$ is isomorphic to the subgroup of $GL_2( {\mathbb R} )$ consisting of matrices of the form

$$\begin{equation*} \begin{pmatrix} a & b \\ -b & a \end{pmatrix}. \end{equation*}$$

Hint

Define $\phi: {\mathbb C}^* \rightarrow GL_2( {\mathbb R})$ by

$$\begin{equation*} \phi(a + bi) = \begin{pmatrix} a & b \\ -b & a \end{pmatrix}. \end{equation*}$$

Exercise3

Prove or disprove: $U(8) \cong {\mathbb Z}_4\text{.}$

Hint

False.

Exercise6

Show that the $n$th roots of unity are isomorphic to ${\mathbb Z}_n\text{.}$

Hint

Define a map from ${\mathbb Z}_n$ into the $n$th roots of unity by $k \mapsto \cis(2k\pi / n)\text{.}$

Exercise8

Prove that ${\mathbb Q}$ is not isomorphic to ${\mathbb Z}\text{.}$

Hint

Assume that ${\mathbb Q}$ is cyclic and try to find a generator.

Exercise11

Find five non-isomorphic groups of order 8.

Hint

There are two nonabelian and three abelian groups that are not isomorphic.

Exercise16

Find the order of each of the following elements.

1. $(3, 4)$ in ${\mathbb Z}_4 \times {\mathbb Z}_6$

2. $(6, 15, 4)$ in ${\mathbb Z}_{30} \times {\mathbb Z}_{45} \times {\mathbb Z}_{24}$

3. $(5, 10, 15)$ in ${\mathbb Z}_{25} \times {\mathbb Z}_{25} \times {\mathbb Z}_{25}$

4. $(8, 8, 8)$ in ${\mathbb Z}_{10} \times {\mathbb Z}_{24} \times {\mathbb Z}_{80}$

Hint

(a) 12; (c) 5.

Exercise19

Prove that $S_3 \times {\mathbb Z}_2$ is isomorphic to $D_6\text{.}$ Can you make a conjecture about $D_{2n}\text{?}$ Prove your conjecture.

Hint

Draw the picture.

Exercise20

Prove or disprove: Every abelian group of order divisible by 3 contains a subgroup of order 3.

Hint

True.

Exercise25

Prove or disprove: There is a noncyclic abelian group of order 52.

Hint

True.

Exercise27

Let $G \cong H\text{.}$ Show that if $G$ is cyclic, then so is $H\text{.}$

Hint

Let $a$ be a generator for $G\text{.}$ If $\phi :G \rightarrow H$ is an isomorphism, show that $\phi(a)$ is a generator for $H\text{.}$

Exercise38

Find $\aut( {\mathbb Z}_6)\text{.}$

Hint

Any automorphism of ${\mathbb Z}_6$ must send 1 to another generator of ${\mathbb Z}_6\text{.}$

Exercise45

Let $G$ be the internal direct product of subgroups $H$ and $K\text{.}$ Show that the map $\phi : G \rightarrow H \times K$ defined by $\phi(g) = (h,k)$ for $g =hk\text{,}$ where $h \in H$ and $k \in K\text{,}$ is one-to-one and onto.

Hint

To show that $\phi$ is one-to-one, let $g_1 = h_1 k_1$ and $g_2 = h_2 k_2$ and consider $\phi(g_1) = \phi(g_2)\text{.}$

Exercises10.3Exercises

Exercise1

For each of the following groups $G\text{,}$ determine whether $H$ is a normal subgroup of $G\text{.}$ If $H$ is a normal subgroup, write out a Cayley table for the factor group $G/H\text{.}$

1. $G = S_4$ and $H = A_4$

2. $G = A_5$ and $H = \{ (1), (123), (132) \}$

3. $G = S_4$ and $H = D_4$

4. $G = Q_8$ and $H = \{ 1, -1, I, -I \}$

5. $G = {\mathbb Z}$ and $H = 5 {\mathbb Z}$

Hint

(a)

$$\begin{equation*} \begin{array}{c|cc} & A_4 & (12)A_4 \\ \hline A_4 & A_4 & (12) A_4 \\ (12) A_4 & (12) A_4 & A_4 \end{array} \end{equation*}$$

(c) $D_4$ is not normal in $S_4\text{.}$

Exercise8

If $G$ is cyclic, prove that $G/H$ must also be cyclic.

Hint

If $a \in G$ is a generator for $G\text{,}$ then $aH$ is a generator for $G/H\text{.}$

Exercise11

If a group $G$ has exactly one subgroup $H$ of order $k\text{,}$ prove that $H$ is normal in $G\text{.}$

Hint

For any $g \in G\text{,}$ show that the map $i_g : G \to G$ defined by $i_g : x \mapsto gxg^{-1}$ is an isomorphism of $G$ with itself. Then consider $i_g(H)\text{.}$

Exercise12

Define the of an element $g$ in a group $G$ to be the set

$$\begin{equation*} C(g) = \{ x \in G : xg = gx \}. \end{equation*}$$

Show that $C(g)$ is a subgroup of $G\text{.}$ If $g$ generates a normal subgroup of $G\text{,}$ prove that $C(g)$ is normal in $G\text{.}$

Hint

Suppose that $\langle g \rangle$ is normal in $G$ and let $y$ be an arbitrary element of $G\text{.}$ If $x \in C(g)\text{,}$ we must show that $y x y^{-1}$ is also in $C(g)\text{.}$ Show that $(y x y^{-1}) g = g (y x y^{-1})\text{.}$

Exercise14

Let $G$ be a group and let $G' = \langle aba^{- 1} b^{-1} \rangle\text{;}$ that is, $G'$ is the subgroup of all finite products of elements in $G$ of the form $aba^{-1}b^{-1}\text{.}$ The subgroup $G'$ is called the of $G\text{.}$

1. Show that $G'$ is a normal subgroup of $G\text{.}$

2. Let $N$ be a normal subgroup of $G\text{.}$ Prove that $G/N$ is abelian if and only if $N$ contains the commutator subgroup of $G\text{.}$

Hint

(a) Let $g \in G$ and $h \in G'\text{.}$ If $h = aba^{-1}b^{-1}\text{,}$ then

$$\begin{align*} ghg^{-1} & = gaba^{-1}b^{-1}g^{-1}\\ & = (gag^{-1})(gbg^{-1})(ga^{-1}g^{-1})(gb^{-1}g^{-1})\\ & = (gag^{-1})(gbg^{-1})(gag^{-1})^{-1}(gbg^{-1})^{-1}. \end{align*}$$

We also need to show that if $h = h_1 \cdots h_n$ with $h_i = a_i b_i a_i^{-1} b_i^{-1}\text{,}$ then $ghg^{-1}$ is a product of elements of the same type. However, $ghg^{-1} = g h_1 \cdots h_n g^{-1} = (gh_1g^{-1})(gh_2g^{-1}) \cdots (gh_ng^{-1})\text{.}$

Exercises11.3Exercises

Exercise2

Which of the following maps are homomorphisms? If the map is a homomorphism, what is the kernel?

1. $\phi : {\mathbb R}^\ast \rightarrow GL_2 ( {\mathbb R})$ defined by

   $$\begin{equation*} \phi( a ) = \begin{pmatrix} 1 & 0 \\ 0 & a \end{pmatrix} \end{equation*}$$

2. $\phi : {\mathbb R} \rightarrow GL_2 ( {\mathbb R})$ defined by

   $$\begin{equation*} \phi( a ) = \begin{pmatrix} 1 & 0 \\ a & 1 \end{pmatrix} \end{equation*}$$

3. $\phi : GL_2 ({\mathbb R}) \rightarrow {\mathbb R}$ defined by

   $$\begin{equation*} \phi \left( \begin{pmatrix} a & b \\ c & d \end{pmatrix} \right) = a + d \end{equation*}$$

4. $\phi : GL_2 ( {\mathbb R}) \rightarrow {\mathbb R}^\ast$ defined by

   $$\begin{equation*} \phi \left( \begin{pmatrix} a & b \\ c & d \end{pmatrix} \right) = ad - bc \end{equation*}$$

5. $\phi : {\mathbb M}_2( {\mathbb R}) \rightarrow {\mathbb R}$ defined by

   $$\begin{equation*} \phi \left( \begin{pmatrix} a & b \\ c & d \end{pmatrix} \right) = b, \end{equation*}$$

   where ${\mathbb M}_2( {\mathbb R})$ is the additive group of $2 \times 2$ matrices with entries in ${\mathbb R}\text{.}$

Hint

(a) is a homomorphism with kernel $\{ 1 \}\text{;}$ (c) is not a homomorphism.

Exercise4

Let $\phi : {\mathbb Z} \rightarrow {\mathbb Z}$ be given by $\phi(n) = 7n\text{.}$ Prove that $\phi$ is a group homomorphism. Find the kernel and the image of $\phi\text{.}$

Hint

Since $\phi(m + n) = 7(m+n) = 7m + 7n = \phi(m) + \phi(n)\text{,}$ $\phi$ is a homomorphism.

Exercise5

Describe all of the homomorphisms from ${\mathbb Z}_{24}$ to ${\mathbb Z}_{18}\text{.}$

Hint

For any homomorphism $\phi : {\mathbb Z}_{24} \rightarrow {\mathbb Z}_{18}\text{,}$ the kernel of $\phi$ must be a subgroup of ${\mathbb Z}_{24}$ and the image of $\phi$ must be a subgroup of ${\mathbb Z}_{18}\text{.}$ Now use the fact that a generator must map to a generator.

Exercise9

If $\phi : G \rightarrow H$ is a group homomorphism and $G$ is abelian, prove that $\phi(G)$ is also abelian.

Hint

Let $a, b \in G\text{.}$ Then $\phi(a) \phi(b) = \phi(ab) = \phi(ba) = \phi(b)\phi(a)\text{.}$

Exercise17

Let $\phi : G_1 \rightarrow G_2$ be a surjective group homomorphism. Let $H_1$ be a normal subgroup of $G_1$ and suppose that $\phi(H_1) = H_2\text{.}$ Prove or disprove that $G_1/H_1 \cong G_2/H_2\text{.}$

Hint

Find a counterexample.

Exercises12.3Exercises

Exercise1

Prove the identity

$$\begin{equation*} \langle {\mathbf x}, {\mathbf y} \rangle = \frac{1}{2} \left[ \|{\mathbf x} + {\mathbf y}\|^2 - \|{\mathbf x}\|^2 - \| {\mathbf y}\|^2 \right]. \end{equation*}$$

Hint

$$\begin{align*} \frac{1}{2} \left[ \|{\mathbf x} + {\mathbf y}\|^2 + \|{\mathbf x}\|^2 - \| {\mathbf y}\|^2 \right] & = \frac{1}{2} \left[ \langle x + y, x + y \rangle - \|{\mathbf x}\|^2 - \| {\mathbf y}\|^2 \right]\\ & = \frac{1}{2} \left[ \| {\mathbf x}\|^2 + 2 \langle x, y \rangle + \| {\mathbf y}\|^2 - \|{\mathbf x}\|^2 - \| {\mathbf y}\|^2 \right]\\ & = \langle {\mathbf x}, {\mathbf y} \rangle. \end{align*}$$

Exercise3

Prove that the following matrices are orthogonal. Are any of these matrices in $SO(n)\text{?}$

1. $$\begin{equation*} \begin{pmatrix} 1/\sqrt{2} & -1/\sqrt{2} \\ 1/\sqrt{2} & 1/\sqrt{2} \end{pmatrix} \end{equation*}$$
2. $$\begin{equation*} \begin{pmatrix} 1 / \sqrt{5} & 2 / \sqrt{5} \\ - 2 /\sqrt{5} & 1/ \sqrt{5} \end{pmatrix} \end{equation*}$$
3. $$\begin{equation*} \begin{pmatrix} 4/ \sqrt{5} & 0 & 3 / \sqrt{5} \\ -3 / \sqrt{5} & 0 & 4 / \sqrt{5} \\ 0 & -1 & 0 \end{pmatrix} \end{equation*}$$
4. $$\begin{equation*} \begin{pmatrix} 1/3 & 2/3 & - 2/3 \\ - 2/3 & 2/3 & 1/3 \\ -2/3 & 1/3 & 2/3 \end{pmatrix} \end{equation*}$$

Hint

(a) is in $SO(2)\text{;}$ (c) is not in $O(3)\text{.}$

Exercise5

Let ${\mathbf x}\text{,}$ ${\mathbf y}\text{,}$ and ${\mathbf w}$ be vectors in ${\mathbb R}^n$ and $\alpha \in {\mathbb R}\text{.}$ Prove each of the following properties of inner products.

1. $\langle {\mathbf x}, {\mathbf y} \rangle = \langle {\mathbf y}, {\mathbf x} \rangle\text{.}$

2. $\langle {\mathbf x}, {\mathbf y} + {\mathbf w} \rangle = \langle {\mathbf x}, {\mathbf y} \rangle + \langle {\mathbf x}, {\mathbf w} \rangle\text{.}$

3. $\langle \alpha {\mathbf x}, {\mathbf y} \rangle = \langle {\mathbf x}, \alpha {\mathbf y} \rangle = \alpha \langle {\mathbf x}, {\mathbf y} \rangle\text{.}$

4. $\langle {\mathbf x}, {\mathbf x} \rangle \geq 0$ with equality exactly when ${\mathbf x} = 0\text{.}$

5. If $\langle {\mathbf x}, {\mathbf y} \rangle = 0$ for all ${\mathbf x}$ in ${\mathbb R}^n\text{,}$ then ${\mathbf y} = 0\text{.}$

Hint

(a) $\langle {\mathbf x}, {\mathbf y} \rangle = \langle {\mathbf y}, {\mathbf x} \rangle\text{.}$

Exercise7

Prove that $\{ (2,1), (1,1) \}$ and $\{ ( 12, 5), ( 7, 3) \}$ are bases for the same lattice.

Hint

Use the unimodular matrix

$$\begin{equation*} \begin{pmatrix} 5 & 2 \\ 2 & 1 \end{pmatrix}. \end{equation*}$$

Exercise10

Prove that $SO(n)$ is a normal subgroup of $O(n)\text{.}$

Hint

Show that the kernel of the map $\det : O(n) \rightarrow {\mathbb R}^*$ is $SO(n)\text{.}$

Exercise13

Prove or disprove: There exists an infinite abelian subgroup of $O(n)\text{.}$

Hint

True.

Exercise17

Determine which of the 17 wallpaper groups preserves the symmetry of the pattern in Figure 12.26.

Hint

$p6m$

Exercises13.3Exercises

Exercise1

Find all of the abelian groups of order less than or equal to 40 up to isomorphism.

Hint

There are three possible groups.

Exercise4

Find all of the composition series for each of the following groups.

1. ${\mathbb Z}_{12}$

2. ${\mathbb Z}_{48}$

3. The quaternions, $Q_8$

4. $D_4$

5. $S_3 \times {\mathbb Z}_4$

6. $S_4$

7. $S_n\text{,}$ $n \geq 5$

8. ${\mathbb Q}$

Hint

(a) $\{ 0 \} \subset \langle 6 \rangle \subset \langle 3 \rangle \subset {\mathbb Z}_{12}\text{;}$ (e) $\{ (1) \} \times \{ 0 \} \subset \{ (1), (123), (132) \} \times \{ 0 \} \subset S_3 \times \{ 0 \} \subset S_3 \times \langle 2 \rangle\subset S_3 \times {\mathbb Z}_4\text{.}$

Exercise7

A group $G$ is a if every element of $G$ has finite order. Prove that a finitely generated abelian torsion group must be finite.

Hint

Use the Fundamental Theorem of Finitely Generated Abelian Groups.

Exercise12

Let $N$ be a normal subgroup of $G\text{.}$ If $N$ and $G/N$ are solvable groups, show that $G$ is also a solvable group.

Hint

If $N$ and $G/N$ are solvable, then they have solvable series

$$\begin{gather*} N = N_n \supset N_{n - 1} \supset \cdots \supset N_1 \supset N_0 = \{ e \}\\ G/N = G_n/N \supset G_{n - 1}/N \supset \cdots G_1/N \supset G_0/N = \{ N \}. \end{gather*}$$

Exercise16

Prove that $D_n$ is solvable for all integers $n\text{.}$

Hint

Use the fact that $D_n$ has a cyclic subgroup of index 2.

Exercise21

Suppose that $G$ is a solvable group with order $n \geq 2\text{.}$ Show that $G$ contains a normal nontrivial abelian factor group.

Hint

$G/G'$ is abelian.

Exercises14.4Exercises

Exercise1

Examples 14.1–14.5 in the first section each describe an action of a group $G$ on a set $X\text{,}$ which will give rise to the equivalence relation defined by $G$-equivalence. For each example, compute the equivalence classes of the equivalence relation, the $G$-.

Hint

Example 14.1: $0\text{,}$ ${\mathbb R}^2 \setminus \{ 0 \}\text{.}$ Example 14.2: $X = \{ 1, 2, 3, 4 \}\text{.}$

Exercise2

Compute all $X_g$ and all $G_x$ for each of the following permutation groups.

1. $X= \{1, 2, 3\}\text{,}$ $G=S_3=\{(1), (12), (13), (23), (123), (132) \}$

2. $X = \{1, 2, 3, 4, 5, 6\}\text{,}$ $G = \{(1), (12), (345), (354), (12)(345), (12)(354) \}$

Hint

(a) $X_{(1)} = \{1, 2, 3 \}\text{,}$ $X_{(12)} = \{3 \}\text{,}$ $X_{(13)} = \{ 2 \}\text{,}$ $X_{(23)} = \{1 \}\text{,}$ $X_{(123)} = X_{(132)} = \emptyset\text{.}$ $G_1 = \{ (1), (23) \}\text{,}$ $G_2 = \{(1), (13) \}\text{,}$ $G_3 = \{ (1), (12)\}\text{.}$

Exercise3

Compute the $G$-equivalence classes of $X$ for each of the $G$-sets in Exercise 14.4.2. For each $x \in X$ verify that $|G|=|{\mathcal O}_x| \cdot |G_x|\text{.}$

Hint

(a) ${\mathcal O}_1 = {\mathcal O}_2 = {\mathcal O}_3 = \{ 1, 2, 3\}\text{.}$

Exercise6

Find the conjugacy classes and the class equation for each of the following groups.

1. $S_4$

2. $D_5$

3. ${\mathbb Z}_9$

4. $Q_8$

Hint

The conjugacy classes for $S_4$ are

$$\begin{gather*} {\mathcal O}_{(1)} = \{ (1) \},\\ {\mathcal O}_{(12)} = \{ (12), (13), (14), (23), (24), (34) \},\\ {\mathcal O}_{(12)(34)} = \{ (12)(34), (13)(24), (14)(23) \},\\ {\mathcal O}_{(123)} = \{ (123), (132), (124), (142), (134), (143), (234), (243) \},\\ {\mathcal O}_{(1234)} = \{ (1234), (1243), (1324), (1342), (1423), (1432) \}. \end{gather*}$$

The class equation is $1 + 3 + 6 + 6 + 8 = 24\text{.}$

Exercise8

If a square remains fixed in the plane, how many different ways can the corners of the square be colored if three colors are used?

Hint

$(3^4 + 3^1 + 3^2 + 3^1 + 3^2 + 3^2 + 3^3 + 3^3)/8 = 21\text{.}$

Exercise11

Up to a rotation, how many ways can the faces of a cube be colored with three different colors?

Hint

The group of rigid motions of the cube can be described by the allowable permutations of the six faces and is isomorphic to $S_4\text{.}$ There are the identity cycle, 6 permutations with the structure $(abcd)$ that correspond to the quarter turns, 3 permutations with the structure $(ab)(cd)$ that correspond to the half turns, 6 permutations with the structure $(ab)(cd)(ef)$ that correspond to rotating the cube about the centers of opposite edges, and 8 permutations with the structure $(abc)(def)$ that correspond to rotating the cube about opposite vertices.

Exercise15

Suppose that the vertices of a regular hexagon are to be colored either red or white. How many ways can this be done up to a symmetry of the hexagon?

Hint

$(1 \cdot 2^6 + 3 \cdot 2^4 + 4 \cdot 2^3 + 2 \cdot 2^2 + 2 \cdot 2^1)/12 = 13\text{.}$

Exercise17

How many equivalence classes of switching functions are there if the input variables $x_1\text{,}$ $x_2\text{,}$ and $x_3$ can be permuted by any permutation in $S_3\text{?}$ What if the input variables $x_1\text{,}$ $x_2\text{,}$ $x_3\text{,}$ and $x_4$ can be permuted by any permutation in $S_4\text{?}$

Hint

$(1 \cdot 2^8 + 3 \cdot 2^6 + 2 \cdot 2^4)/6 = 80\text{.}$

Exercise22

Let $a \in G\text{.}$ Show that for any $g \in G\text{,}$ $gC(a) g^{-1} = C(gag^{-1})\text{.}$

Hint

Use the fact that $x \in g C(a) g^{-1}$ if and only if $g^{-1}x g \in C(a)\text{.}$

Exercises15.3Exercises

Exercise1

What are the orders of all Sylow $p$-subgroups where $G$ has order 18, 24, 54, 72, and 80?

Hint

If $|G| = 18 = 2 \cdot 3^2\text{,}$ then the order of a Sylow 2-subgroup is 2, and the order of a Sylow 3-subgroup is 9.

Exercise2

Find all the Sylow 3-subgroups of $S_4$ and show that they are all conjugate.

Hint

The four Sylow 3-subgroups of $S_4$ are $P_1 = \{ (1), (123), (132) \}\text{,}$ $P_2 = \{ (1), (124), (142) \}\text{,}$ $P_3 = \{ (1), (134), (143) \}\text{,}$ $P_4 = \{ (1), (234), (243) \}\text{.}$

Exercise5

Prove that no group of order 96 is simple.

Hint

Since $|G| = 96 = 2^5 \cdot 3\text{,}$ $G$ has either one or three Sylow 2-subgroups by the Third Sylow Theorem. If there is only one subgroup, we are done. If there are three Sylow 2-subgroups, let $H$ and $K$ be two of them. Therefore, $|H \cap K| \geq 16\text{;}$ otherwise, $HK$ would have $(32 \cdot 32)/8 = 128$ elements, which is impossible. Thus, $H \cap K$ is normal in both $H$ and $K$ since it has index 2 in both groups.

Exercise8

Let $G$ be a group of order $p^2 q^2\text{,}$ where $p$ and $q$ are distinct primes such that $q \nmid p^2 - 1$ and $p \nmid q^2 - 1\text{.}$ Prove that $G$ must be abelian. Find a pair of primes for which this is true.

Hint

Show that $G$ has a normal Sylow $p$-subgroup of order $p^2$ and a normal Sylow $q$-subgroup of order $q^2\text{.}$

Exercise10

Let $H$ be a subgroup of a group $G\text{.}$ Prove or disprove that the normalizer of $H$ is normal in $G\text{.}$

Hint

False.

Exercise17

Show that every group of order $255$ is cyclic.

Hint

If $G$ is abelian, then $G$ is cyclic, since $|G| = 3 \cdot 5 \cdot 17\text{.}$ Now look at Example 15.14.

Exercise23

Prove that the number of distinct conjugates of a subgroup $H$ of a finite group $G$ is $[G : N(H) ]\text{.}$

Hint

Define a mapping between the right cosets of $N(H)$ in $G$ and the conjugates of $H$ in $G$ by $N(H) g \mapsto g^{-1} H g\text{.}$ Prove that this map is a bijection.

Exercise26

Let $G$ be a group. Prove that $G' = \langle a b a^{-1} b^{-1} : a, b \in G \rangle$ is a normal subgroup of $G$ and $G/G'$ is abelian. Find an example to show that $\{ a b a^{-1} b^{-1} : a, b \in G \}$ is not necessarily a group.

Hint

Let $a G', b G' \in G/G'\text{.}$ Then $(a G')( b G') = ab G' = ab(b^{-1}a^{-1}ba) G' = (abb^{-1}a^{-1})ba G' = ba G'\text{.}$

Exercises16.6Exercises

Exercise1

Which of the following sets are rings with respect to the usual operations of addition and multiplication? If the set is a ring, is it also a field?

1. $7 {\mathbb Z}$

2. ${\mathbb Z}_{18}$

3. ${\mathbb Q} ( \sqrt{2}\, ) = \{a + b \sqrt{2} : a, b \in {\mathbb Q}\}$

4. ${\mathbb Q} ( \sqrt{2}, \sqrt{3}\, ) = \{a + b \sqrt{2} + c \sqrt{3} + d \sqrt{6} : a, b, c, d \in {\mathbb Q}\}$

5. ${\mathbb Z}[\sqrt{3}\, ] = \{ a + b \sqrt{3} : a, b \in {\mathbb Z} \}$

6. $R = \{a + b \sqrt[3]{3} : a, b \in {\mathbb Q} \}$

7. ${\mathbb Z}[ i ] = \{ a + b i : a, b \in {\mathbb Z} \text{ and } i^2 = -1 \}$

8. ${\mathbb Q}( \sqrt[3]{3}\, ) = \{ a + b \sqrt[3]{3} + c \sqrt[3]{9} : a, b, c \in {\mathbb Q} \}$

Hint

(a) $7 {\mathbb Z}$ is a ring but not a field; (c) ${\mathbb Q}(\sqrt{2}\, )$ is a field; (f) $R$ is not a ring.

Exercise3

List or characterize all of the units in each of the following rings.

1. ${\mathbb Z}_{10}$

2. ${\mathbb Z}_{12}$

3. ${\mathbb Z}_{7}$

4. ${\mathbb M}_2( {\mathbb Z} )\text{,}$ the $2 \times 2$ matrices with entries in ${\mathbb Z}$

5. ${\mathbb M}_2( {\mathbb Z}_2 )\text{,}$ the $2 \times 2$ matrices with entries in ${\mathbb Z}_2$

Hint

(a) $\{1, 3, 7, 9 \}\text{;}$ (c) $\{ 1, 2, 3, 4, 5, 6 \}\text{;}$ (e)

$$\begin{equation*} \left\{ \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}, \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}, \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}, \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}, \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}, \right\}. \end{equation*}$$

Exercise4

Find all of the ideals in each of the following rings. Which of these ideals are maximal and which are prime?

1. ${\mathbb Z}_{18}$

2. ${\mathbb Z}_{25}$

3. ${\mathbb M}_2( {\mathbb R} )\text{,}$ the $2 \times 2$ matrices with entries in ${\mathbb R}$

4. ${\mathbb M}_2( {\mathbb Z} )\text{,}$ the $2 \times 2$ matrices with entries in ${\mathbb Z}$

5. ${\mathbb Q}$

Hint

(a) $\{0 \}\text{,}$ $\{0, 9 \}\text{,}$ $\{0, 6, 12 \}\text{,}$ $\{0, 3, 6, 9, 12, 15 \}\text{,}$ $\{0, 2, 4, 6, 8, 10, 12, 14, 16 \}\text{;}$ (c) there are no nontrivial ideals.

Exercise7

Prove that ${\mathbb R}$ is not isomorphic to ${\mathbb C}\text{.}$

Hint

Assume there is an isomorphism $\phi: {\mathbb C} \rightarrow {\mathbb R}$ with $\phi(i) = a\text{.}$

Exercise8

Prove or disprove: The ring ${\mathbb Q}( \sqrt{2}\, ) = \{ a + b \sqrt{2} : a, b \in {\mathbb Q} \}$ is isomorphic to the ring ${\mathbb Q}( \sqrt{3}\, ) = \{a + b \sqrt{3} : a, b \in {\mathbb Q} \}\text{.}$

Hint

False. Assume there is an isomorphism $\phi: {\mathbb Q}(\sqrt{2}\, ) \rightarrow {\mathbb Q}(\sqrt{3}\, )$ such that $\phi(\sqrt{2}\, ) = a\text{.}$

Exercise13

Solve each of the following systems of congruences.

1. $$\begin{align*} x & \equiv 2 \pmod{5}\\ x & \equiv 6 \pmod{11} \end{align*}$$
2. $$\begin{align*} x & \equiv 3 \pmod{7}\\ x & \equiv 0 \pmod{8}\\ x & \equiv 5 \pmod{15} \end{align*}$$
3. $$\begin{align*} x & \equiv 2 \pmod{4}\\ x & \equiv 4 \pmod{7}\\ x & \equiv 7 \pmod{9}\\ x & \equiv 5 \pmod{11} \end{align*}$$
4. $$\begin{align*} x & \equiv 3 \pmod{5}\\ x & \equiv 0 \pmod{8}\\ x & \equiv 1 \pmod{11}\\ x & \equiv 5 \pmod{13} \end{align*}$$

Hint

(a) $x \equiv 17 \pmod{55}\text{;}$ (c) $x \equiv 214 \pmod{2772}\text{.}$

Exercise16

If $R$ is a field, show that the only two ideals of $R$ are $\{ 0 \}$ and $R$ itself.

Hint

If $I \neq \{ 0 \}\text{,}$ show that $1 \in I\text{.}$

Exercise18

Let $\phi : R \rightarrow S$ be a ring homomorphism. Prove each of the following statements.

1. If $R$ is a commutative ring, then $\phi(R)$ is a commutative ring.

2. $\phi( 0 ) = 0\text{.}$

3. Let $1_R$ and $1_S$ be the identities for $R$ and $S\text{,}$ respectively. If $\phi$ is onto, then $\phi(1_R) = 1_S\text{.}$

4. If $R$ is a field and $\phi(R) \neq 0\text{,}$ then $\phi(R)$ is a field.

Hint

(a) $\phi(a) \phi(b) = \phi(ab) = \phi(ba) = \phi(b) \phi(a)\text{.}$

Exercise26

Let $R$ be an integral domain. Show that if the only ideals in $R$ are $\{ 0 \}$ and $R$ itself, $R$ must be a field.

Hint

Let $a \in R$ with $a \neq 0\text{.}$ Then the principal ideal generated by $a$ is $R\text{.}$ Thus, there exists a $b \in R$ such that $ab =1\text{.}$

Exercise28

A ring $R$ is a if for every $a \in R\text{,}$ $a^2 = a\text{.}$ Show that every Boolean ring is a commutative ring.

Hint

Compute $(a+b)^2$ and $(-ab)^2\text{.}$

Exercise34

Let $p$ be prime. Prove that

$$\begin{equation*} {\mathbb Z}_{(p)} = \{ a / b : a, b \in {\mathbb Z} \text{ and } \gcd( b,p) = 1 \} \end{equation*}$$

is a ring. The ring ${\mathbb Z}_{(p)}$ is called the $p\text{.}$

Hint

Let $a/b, c/d \in {\mathbb Z}_{(p)}\text{.}$ Then $a/b + c/d = (ad + bc)/bd$ and $(a/b) \cdot (c/d) = (ac)/(bd)$ are both in ${\mathbb Z}_{(p)}\text{,}$ since $\gcd(bd,p) = 1\text{.}$

Exercise38

An element $x$ in a ring is called an if $x^2 = x\text{.}$ Prove that the only idempotents in an integral domain are $0$ and $1\text{.}$ Find a ring with a idempotent $x$ not equal to 0 or 1.

Hint

Suppose that $x^2 = x$ and $x \neq 0\text{.}$ Since $R$ is an integral domain, $x = 1\text{.}$ To find a nontrivial idempotent, look in ${\mathbb M}_2({\mathbb R})\text{.}$

Exercises17.4Exercises

Exercise2

Compute each of the following.

1. $(5x^2 + 3x - 4) + (4x^2 - x + 9)$ in ${\mathbb Z}_{12}$

2. $(5x^2 + 3x - 4) (4x^2 - x + 9)$ in ${\mathbb Z}_{12}$

3. $(7x^3 + 3x^2 - x) + (6x^2 - 8x + 4)$ in ${\mathbb Z}_9$

4. $(3x^2 + 2x - 4) + (4x^2 + 2)$ in ${\mathbb Z}_5$

5. $(3x^2 + 2x - 4) (4x^2 + 2)$ in ${\mathbb Z}_5$

6. $(5x^2 + 3x - 2)^2$ in ${\mathbb Z}_{12}$

Hint

(a) $9x^2 + 2x + 5\text{;}$ (b) $8x^4 + 7x^3 + 2x^2 + 7x\text{.}$

Exercise3

Use the division algorithm to find $q(x)$ and $r(x)$ such that $a(x) = q(x) b(x) + r(x)$ with $\deg r(x) \lt \deg b(x)$ for each of the following pairs of polynomials.

1. $a(x) = 5 x^3 + 6x^2 - 3 x + 4$ and $b(x) = x - 2$ in ${\mathbb Z}_7[x]$

2. $a(x) = 6 x^4 - 2 x^3 + x^2 - 3 x + 1$ and $b(x) = x^2 + x - 2$ in ${\mathbb Z}_7[x]$

3. $a(x) = 4 x^5 - x^3 + x^2 + 4$ and $b(x) = x^3 - 2$ in ${\mathbb Z}_5[x]$

4. $a(x) = x^5 + x^3 -x^2 - x$ and $b(x) = x^3 + x$ in ${\mathbb Z}_2[x]$

Hint

(a) $5 x^3 + 6 x^2 - 3 x + 4 = (5 x^2 + 2x + 1)(x -2) + 6\text{;}$ (c) $4x^5 - x^3 + x^2 + 4 = (4x^2 + 4)(x^3 + 3) + 4x^2 + 2\text{.}$

Exercise5

Find all of the zeros for each of the following polynomials.

1. $5x^3 + 4x^2 - x + 9$ in ${\mathbb Z}_{12}$

2. $3x^3 - 4x^2 - x + 4$ in ${\mathbb Z}_{5}$

3. $5x^4 + 2x^2 - 3$ in ${\mathbb Z}_{7}$

4. $x^3 + x + 1$ in ${\mathbb Z}_2$

Hint

(a) No zeros in ${\mathbb Z}_{12}\text{;}$ (c) 3, 4.

Exercise7

Find a unit $p(x)$ in ${\mathbb Z}_4[x]$ such that $\deg p(x) \gt 1\text{.}$

Hint

Look at $(2x + 1)\text{.}$

Exercise8

Which of the following polynomials are irreducible over ${\mathbb Q}[x]\text{?}$

1. $x^4 - 2x^3 + 2x^2 + x + 4$

2. $x^4 - 5x^3 + 3x - 2$

3. $3x^5 - 4x^3 - 6x^2 + 6$

4. $5x^5 - 6x^4 - 3x^2 + 9 x - 15$

Hint

(a) Reducible; (c) irreducible.

Exercise10

Give two different factorizations of $x^2 + x + 8$ in ${\mathbb Z}_{10}[x]\text{.}$

Hint

One factorization is $x^2 + x + 8 = (x + 2)(x + 9)\text{.}$

Exercise13

Show that the division algorithm does not hold for ${\mathbb Z}[x]\text{.}$ Why does it fail?

Hint

The integers $\mathbb Z$ do not form a field.

Exercise14

Prove or disprove: $x^p + a$ is irreducible for any $a \in {\mathbb Z}_p\text{,}$ where $p$ is prime.

Hint

False.

Exercise16

Suppose that $R$ and $S$ are isomorphic rings. Prove that $R[x] \cong S[x]\text{.}$

Hint

Let $\phi : R \rightarrow S$ be an isomorphism. Define $\overline{\phi} : R[x] \rightarrow S[x]$ by $\overline{\phi}(a_0 + a_1 x + \cdots + a_n x^n) = \phi(a_0) + \phi(a_1) x + \cdots + \phi(a_n) x^n\text{.}$

Exercise20Cyclotomic Polynomials

The polynomial

$$\begin{equation*} \Phi_n(x) = \frac{x^n - 1}{x - 1} = x^{n - 1} + x^{n - 2} + \cdots + x + 1 \end{equation*}$$

is called the Show that $\Phi_p(x)$ is irreducible over ${\mathbb Q}$ for any prime $p\text{.}$

Hint

The polynomial

$$\begin{equation*} \Phi_n(x) = \frac{x^n - 1}{x - 1} = x^{n - 1} + x^{n - 2} + \cdots + x + 1 \end{equation*}$$

is called the Show that $\Phi_p(x)$ is irreducible over ${\mathbb Q}$ for any prime $p\text{.}$

Exercise26

Let $F$ be a field. Show that $F[x]$ is never a field.

Hint

Find a nontrivial proper ideal in $F[x]\text{.}$

Exercises18.3Exercises

Exercise1

Let $z = a + b \sqrt{3}\, i$ be in ${\mathbb Z}[ \sqrt{3}\, i]\text{.}$ If $a^2 + 3 b^2 = 1\text{,}$ show that $z$ must be a unit. Show that the only units of ${\mathbb Z}[ \sqrt{3}\, i ]$ are 1 and $-1\text{.}$

Hint

Note that $z^{-1} = 1/(a + b\sqrt{3}\, i) = (a -b \sqrt{3}\, i)/(a^2 + 3b^2)$ is in ${\mathbb Z}[\sqrt{3}\, i]$ if and only if $a^2 + 3 b^2 = 1\text{.}$ The only integer solutions to the equation are $a = \pm 1, b = 0\text{.}$

Exercise2

The Gaussian integers, ${\mathbb Z}[i]\text{,}$ are a UFD. Factor each of the following elements in ${\mathbb Z}[i]$ into a product of irreducibles.

1. 5

2. $1 + 3i$

3. $6 + 8i$

4. 2

Hint

(a) $5 = -i(1 + 2i)(2 + i)\text{;}$ (c) $6 + 8i = -i(1 + i)^2(2 + i)^2\text{.}$

Exercise4

Prove or disprove: Any subring of a field $F$ containing 1 is an integral domain.

Hint

True.

Exercise9

Prove that the field of fractions of the Gaussian integers, ${\mathbb Z}[i]\text{,}$ is

$$\begin{equation*} {\mathbb Q}(i) = \{ p + q i : p, q \in {\mathbb Q} \}. \end{equation*}$$

Hint

Let $z = a + bi$ and $w = c + di \neq 0$ be in ${\mathbb Z}[i]\text{.}$ Prove that $z/w \in {\mathbb Q}(i)\text{.}$

Exercise15

Let $D$ be a Euclidean domain with Euclidean valuation $\nu\text{.}$ If $a$ and $b$ are associates in $D\text{,}$ prove that $\nu(a) = \nu(b)\text{.}$

Hint

Let $a = ub$ with $u$ a unit. Then $\nu(b) \leq \nu(ub) \leq \nu(a)\text{.}$ Similarly, $\nu(a) \leq \nu(b)\text{.}$

Exercise16

Show that ${\mathbb Z}[\sqrt{5}\, i]$ is not a unique factorization domain.

Hint

Show that 21 can be factored in two different ways.

Exercises19.4Exercises

Exercise2

Draw the diagram for the set of positive integers that are divisors of 30. Is this poset a Boolean algebra?

Hint

Exercise5

Prove or disprove: ${\mathbb Z}$ is a poset under the relation $a \preceq b$ if $a \mid b\text{.}$

Hint

False.

Exercise6

Draw the switching circuit for each of the following Boolean expressions.

1. $(a \vee b \vee a') \wedge a$

2. $(a \vee b)' \wedge (a \vee b)$

3. $a \vee (a \wedge b)$

4. $(c \vee a \vee b) \wedge c' \wedge (a \vee b)'$

Hint

(a) $(a \vee b \vee a') \wedge a$

(c) $a \vee (a \wedge b)$

Exercise8

Prove or disprove that the two circuits shown are equivalent.

Hint

Not equivalent.

Exercise10

For each of the following circuits, write a Boolean expression. If the circuit can be replaced by one with fewer switches, give the Boolean expression and draw a diagram for the new circuit.

Hint

(a) $a' \wedge [(a \wedge b') \vee b] = a \wedge (a \vee b) \text{.}$

Exercise14

Let $R$ be a ring and suppose that $X$ is the set of ideals of $R\text{.}$ Show that $X$ is a poset ordered by set-theoretic inclusion, $\subset\text{.}$ Define the meet of two ideals $I$ and $J$ in $X$ by $I \cap J$ and the join of $I$ and $J$ by $I + J\text{.}$ Prove that the set of ideals of $R$ is a lattice under these operations.

Hint

Let $I, J$ be ideals in $R\text{.}$ We need to show that $I + J = \{ r + s : r \in I \text{ and } s \in J \}$ is the smallest ideal in $R$ containing both $I$ and $J\text{.}$ If $r_1, r_2 \in I$ and $s_1, s_2 \in J\text{,}$ then $(r_1 + s_1) + (r_2 + s_2) = (r_1 + r_2) +(s_1 + s_2)$ is in $I + J\text{.}$ For $a \in R\text{,}$ $a(r_1 + s_1) = ar_1 + as_1 \in I + J\text{;}$ hence, $I + J$ is an ideal in $R\text{.}$

Exercise18

Let $X$ be a poset such that for every $a$ and $b$ in $X\text{,}$ either $a \preceq b$ or $b \preceq a\text{.}$ Then $X$ is said to be a .

1. Is $a \mid b$ a total order on ${\mathbb N}\text{?}$

2. Prove that ${\mathbb N}\text{,}$ ${\mathbb Z}\text{,}$ ${\mathbb Q}\text{,}$ and ${\mathbb R}$ are totally ordered sets under the usual ordering $\leq\text{.}$

Hint

(a) No.

Exercise20

Let $B$ be a Boolean algebra. Prove that $a = b$ if and only if $(a \wedge b') \vee ( a' \wedge b) = O$ for $a, b \in B\text{.}$

Hint

$( \Rightarrow)\text{.}$ $a = b \Rightarrow (a \wedge b') \vee (a' \wedge b) = (a \wedge a') \vee (a' \wedge a) = O \vee O = O\text{.}$ $( \Leftarrow)\text{.}$ $( a \wedge b') \vee (a' \wedge b) = O \Rightarrow a \vee b = (a \vee a) \vee b = a \vee (a \vee b) = a \vee [I \wedge (a \vee b)] = a \vee [(a \vee a') \wedge (a \vee b)] = [a \vee (a \wedge b')] \vee [a \vee (a' \wedge b)] = a \vee [(a \wedge b') \vee (a' \wedge b)] = a \vee 0 = a\text{.}$ A symmetric argument shows that $a \vee b = b\text{.}$

Exercises20.4Exercises

Exercise3

Let ${\mathbb Q }( \sqrt{2}, \sqrt{3}\, )$ be the field generated by elements of the form $a + b \sqrt{2} + c \sqrt{3} + d \sqrt{6}\text{,}$ where $a, b, c, d$ are in ${\mathbb Q}\text{.}$ Prove that ${\mathbb Q }( \sqrt{2}, \sqrt{3}\, )$ is a vector space of dimension 4 over ${\mathbb Q}\text{.}$ Find a basis for ${\mathbb Q }( \sqrt{2}, \sqrt{3}\, )\text{.}$

Hint

${\mathbb Q}(\sqrt{2}, \sqrt{3}\, )$ has basis $\{ 1, \sqrt{2}, \sqrt{3}, \sqrt{6}\, \}$ over ${\mathbb Q}\text{.}$

Exercise5

Prove that the set $P_n$ of all polynomials of degree less than $n$ form a subspace of the vector space $F[x]\text{.}$ Find a basis for $P_n$ and compute the dimension of $P_n\text{.}$

Hint

The set $\{ 1, x, x^2, \ldots, x^{n-1} \}$ is a basis for $P_n\text{.}$

Exercise7

Which of the following sets are subspaces of ${\mathbb R}^3\text{?}$ If the set is indeed a subspace, find a basis for the subspace and compute its dimension.

1. $\{ (x_1, x_2, x_3) : 3 x_1 - 2 x_2 + x_3 = 0 \}$

2. $\{ (x_1, x_2, x_3) : 3 x_1 + 4 x_3 = 0, 2 x_1 - x_2 + x_3 = 0 \}$

3. $\{ (x_1, x_2, x_3) : x_1 - 2 x_2 + 2 x_3 = 2 \}$

4. $\{ (x_1, x_2, x_3) : 3 x_1 - 2 x_2^2 = 0 \}$

Hint

(a) Subspace of dimension 2 with basis $\{(1, 0, -3), (0, 1, 2) \}\text{;}$ (d) not a subspace

Exercise10

Let $V$ be a vector space over $F\text{.}$ Prove that $-(\alpha v) = (-\alpha)v = \alpha(-v)$ for all $\alpha \in F$ and all $v \in V\text{.}$

Hint

Since $0 = \alpha 0 = \alpha(-v + v) = \alpha(-v) + \alpha v\text{,}$ it follows that $- \alpha v = \alpha(-v)\text{.}$

Exercise12

Prove that any set of vectors containing ${\mathbf 0}$ is linearly dependent.

Hint

Let $v_0 = 0, v_1, \ldots, v_n \in V$ and $\alpha_0 \neq 0, \alpha_1, \ldots, \alpha_n \in F\text{.}$ Then $\alpha_0 v_0 + \cdots + \alpha_n v_n = 0\text{.}$

Exercise15Linear Transformations

Let $V$ and $W$ be vector spaces over a field $F\text{,}$ of dimensions $m$ and $n\text{,}$ respectively. If $T: V \rightarrow W$ is a map satisfying

$$\begin{align*} T( u+ v ) & = T(u ) + T(v)\\ T( \alpha v ) & = \alpha T(v) \end{align*}$$

for all $\alpha \in F$ and all $u, v \in V\text{,}$ then $T$ is called a from $V$ into $W\text{.}$

1. Prove that the of $T\text{,}$ $\ker(T) = \{ v \in V : T(v) = {\mathbf 0} \}\text{,}$ is a subspace of $V\text{.}$ The kernel of $T$ is sometimes called the of $T\text{.}$

2. Prove that the or of $T\text{,}$ $R(V) = \{ w \in W : T(v) = w \text{ for some } v \in V \}\text{,}$ is a subspace of $W\text{.}$

3. Show that $T : V \rightarrow W$ is injective if and only if $\ker(T) = \{ \mathbf 0 \}\text{.}$

4. Let $\{ v_1, \ldots, v_k \}$ be a basis for the null space of $T\text{.}$ We can extend this basis to be a basis $\{ v_1, \ldots, v_k, v_{k + 1}, \ldots, v_m\}$ of $V\text{.}$ Why? Prove that $\{ T(v_{k + 1}), \ldots, T(v_m) \}$ is a basis for the range of $T\text{.}$ Conclude that the range of $T$ has dimension $m-k\text{.}$

5. Let $\dim V = \dim W\text{.}$ Show that a linear transformation $T : V \rightarrow W$ is injective if and only if it is surjective.

Hint

(a) Let $u, v \in \ker(T)$ and $\alpha \in F\text{.}$ Then

$$\begin{gather*} T(u +v) = T(u) + T(v) = 0\\ T(\alpha v) = \alpha T(v) = \alpha 0 = 0. \end{gather*}$$

Hence, $u + v, \alpha v \in \ker(T)\text{,}$ and $\ker(T)$ is a subspace of $V\text{.}$

(c) The statement that $T(u) = T(v)$ is equivalent to $T(u-v) = T(u) - T(v) = 0\text{,}$ which is true if and only if $u-v = 0$ or $u = v\text{.}$

Exercise17Direct Sums

Let $U$ and $V$ be subspaces of a vector space $W\text{.}$ The sum of $U$ and $V\text{,}$ denoted $U + V\text{,}$ is defined to be the set of all vectors of the form $u + v\text{,}$ where $u \in U$ and $v \in V\text{.}$

1. Prove that $U + V$ and $U \cap V$ are subspaces of $W\text{.}$

2. If $U + V = W$ and $U \cap V = {\mathbf 0}\text{,}$ then $W$ is said to be the In this case, we write $W = U \oplus V\text{.}$ Show that every element $w \in W$ can be written uniquely as $w = u + v\text{,}$ where $u \in U$ and $v \in V\text{.}$

3. Let $U$ be a subspace of dimension $k$ of a vector space $W$ of dimension $n\text{.}$ Prove that there exists a subspace $V$ of dimension $n-k$ such that $W = U \oplus V\text{.}$ Is the subspace $V$ unique?

4. If $U$ and $V$ are arbitrary subspaces of a vector space $W\text{,}$ show that

   $$\begin{equation*} \dim( U + V) = \dim U + \dim V - \dim( U \cap V). \end{equation*}$$

Hint

(a) Let $u, u' \in U$ and $v, v' \in V\text{.}$ Then

$$\begin{align*} (u + v) + (u' + v') & = (u + u') + (v + v') \in U + V\\ \alpha(u + v) & = \alpha u + \alpha v \in U + V. \end{align*}$$

Exercises21.4Exercises

Exercise1

Show that each of the following numbers is algebraic over ${\mathbb Q}$ by finding the minimal polynomial of the number over ${\mathbb Q}\text{.}$

1. $\sqrt{ 1/3 + \sqrt{7} }$

2. $\sqrt{ 3} + \sqrt[3]{5}$

3. $\sqrt{3} + \sqrt{2}\, i$

4. $\cos \theta + i \sin \theta$ for $\theta = 2 \pi /n$ with $n \in {\mathbb N}$

5. $\sqrt{ \sqrt[3]{2} - i }$

Hint

(a) $x^4 - (2/3) x^2 - 62/9\text{;}$ (c) $x^4 - 2 x^2 + 25\text{.}$

Exercise2

Find a basis for each of the following field extensions. What is the degree of each extension?

1. ${\mathbb Q}( \sqrt{3}, \sqrt{6}\, )$ over ${\mathbb Q}$

2. ${\mathbb Q}( \sqrt[3]{2}, \sqrt[3]{3}\, )$ over ${\mathbb Q}$

3. ${\mathbb Q}( \sqrt{2}, i)$ over ${\mathbb Q}$

4. ${\mathbb Q}( \sqrt{3}, \sqrt{5}, \sqrt{7}\, )$ over ${\mathbb Q}$

5. ParseError: KaTeX parse error: Undefined control sequence: \root at position 24: … Q}( \sqrt{2}, \̲r̲o̲o̲t̲ ̲3 \of{2}\, ) over ${\mathbb Q}$

6. ${\mathbb Q}( \sqrt{8}\, )$ over ${\mathbb Q}(\sqrt{2}\, )$

7. ${\mathbb Q}(i, \sqrt{2} +i, \sqrt{3} + i )$ over ${\mathbb Q}$

8. ${\mathbb Q}( \sqrt{2} + \sqrt{5}\, )$ over ${\mathbb Q} ( \sqrt{5}\, )$

9. ${\mathbb Q}( \sqrt{2}, \sqrt{6} + \sqrt{10}\, )$ over ${\mathbb Q} ( \sqrt{3} + \sqrt{5}\, )$

Hint

(a) $\{ 1, \sqrt{2}, \sqrt{3}, \sqrt{6}\, \}\text{;}$ (c) $\{ 1, i, \sqrt{2}, \sqrt{2}\, i \}\text{;}$ (e) $\{1, 2^{1/6}, 2^{1/3}, 2^{1/2}, 2^{2/3}, 2^{5/6} \}\text{.}$

Exercise3

Find the splitting field for each of the following polynomials.

1. $x^4 - 10 x^2 + 21$ over ${\mathbb Q}$

2. $x^4 + 1$ over ${\mathbb Q}$

3. $x^3 + 2x + 2$ over ${\mathbb Z}_3$

4. $x^3 - 3$ over ${\mathbb Q}$

Hint

(a) ${\mathbb Q}(\sqrt{3}, \sqrt{7}\, )\text{.}$

Exercise5

Show that ${\mathbb Z}_2[x] / \langle x^3 + x + 1 \rangle$ is a field with eight elements. Construct a multiplication table for the multiplicative group of the field.

Hint

Use the fact that the elements of ${\mathbb Z}_2[x]/ \langle x^3 + x + 1 \rangle$ are 0, 1, $\alpha\text{,}$ $1 + \alpha\text{,}$ $\alpha^2\text{,}$ $1 + \alpha^2\text{,}$ $\alpha + \alpha^2\text{,}$ $1 + \alpha + \alpha^2$ and the fact that $\alpha^3 + \alpha + 1 = 0\text{.}$

Exercise8

Can a cube be constructed with three times the volume of a given cube?

Hint

False.

Exercise14

Let $K$ be an algebraic extension of $E\text{,}$ and $E$ an algebraic extension of $F\text{.}$ Prove that $K$ is algebraic over $F\text{.}$ [Caution: Do not assume that the extensions are finite.]

Hint

Suppose that $E$ is algebraic over $F$ and $K$ is algebraic over $E\text{.}$ Let $\alpha \in K\text{.}$ It suffices to show that $\alpha$ is algebraic over some finite extension of $F\text{.}$ Since $\alpha$ is algebraic over $E\text{,}$ it must be the zero of some polynomial $p(x) = \beta_0 + \beta_1 x + \cdots + \beta_n x^n$ in $E[x]\text{.}$ Hence $\alpha$ is algebraic over $F(\beta_0, \ldots, \beta_n)\text{.}$

Exercise22

Show that ${\mathbb Q}( \sqrt{3}, \sqrt{7}\, ) = {\mathbb Q}( \sqrt{3} + \sqrt{7}\, )\text{.}$ Extend your proof to show that ${\mathbb Q}( \sqrt{a}, \sqrt{b}\, ) = {\mathbb Q}( \sqrt{a} + \sqrt{b}\, )\text{,}$ where $\gcd(a, b) = 1\text{.}$

Hint

Since $\{ 1, \sqrt{3}, \sqrt{7}, \sqrt{21}\, \}$ is a basis for ${\mathbb Q}( \sqrt{3}, \sqrt{7}\, )$ over ${\mathbb Q}\text{,}$ ${\mathbb Q}( \sqrt{3}, \sqrt{7}\, ) \supset {\mathbb Q}( \sqrt{3} +\sqrt{7}\, )\text{.}$ Since $[{\mathbb Q}( \sqrt{3}, \sqrt{7}\, ) : {\mathbb Q}] = 4\text{,}$ $[{\mathbb Q}( \sqrt{3} + \sqrt{7}\, ) : {\mathbb Q}] = 2$ or 4. Since the degree of the minimal polynomial of $\sqrt{3} +\sqrt{7}$ is 4, ${\mathbb Q}( \sqrt{3}, \sqrt{7}\, ) = {\mathbb Q}( \sqrt{3} +\sqrt{7}\, )\text{.}$

Exercise27

Let $E$ be an extension field of $F$ and $\alpha \in E$ be transcendental over $F\text{.}$ Prove that every element in $F(\alpha)$ that is not in $F$ is also transcendental over $F\text{.}$

Hint

Let $\beta \in F(\alpha)$ not in $F\text{.}$ Then $\beta = p(\alpha)/q(\alpha)\text{,}$ where $p$ and $q$ are polynomials in $\alpha$ with $q(\alpha) \neq 0$ and coefficients in $F\text{.}$ If $\beta$ is algebraic over $F\text{,}$ then there exists a polynomial $f(x) \in F[x]$ such that $f(\beta) = 0\text{.}$ Let $f(x) = a_0 + a_1 x + \cdots + a_n x^n\text{.}$ Then

$$\begin{equation*} 0 = f(\beta) = f\left( \frac{p(\alpha)}{q(\alpha)} \right) = a_0 + a_1 \left( \frac{p(\alpha)}{q(\alpha)} \right) + \cdots + a_n \left( \frac{p(\alpha)}{q(\alpha)} \right)^n. \end{equation*}$$

Now multiply both sides by $q(\alpha)^n$ to show that there is a polynomial in $F[x]$ that has $\alpha$ as a zero.

Exercise28

Let $\alpha$ be a root of an irreducible monic polynomial $p(x) \in F[x]\text{,}$ with $\deg p = n\text{.}$ Prove that $[F(\alpha) : F] = n\text{.}$

Hint

See the comments following Theorem 21.13.

Exercises22.3Exercises

Exercise1

Calculate each of the following.

1. $[\gf(3^6) : \gf(3^3)]$

2. $[\gf(128): \gf(16)]$

3. $[\gf(625) : \gf(25) ]$

4. $[\gf(p^{12}): \gf(p^2)]$

Hint

Make sure that you have a field extension.

Exercise4

Let $\alpha$ be a zero of $x^3 + x^2 + 1$ over ${\mathbb Z}_2\text{.}$ Construct a finite field of order 8. Show that $x^3 + x^2 + 1$ splits in ${\mathbb Z}_2(\alpha)\text{.}$

Hint

There are eight elements in ${\mathbb Z}_2(\alpha)\text{.}$ Exhibit two more zeros of $x^3 + x^2 + 1$ other than $\alpha$ in these eight elements.

Exercise5

Construct a finite field of order 27.

Hint

Find an irreducible polynomial $p(x)$ in ${\mathbb Z}_3[x]$ of degree 3 and show that ${\mathbb Z}_3[x]/ \langle p(x) \rangle$ has 27 elements.

Exercise7

Factor each of the following polynomials in ${\mathbb Z}_2[x]\text{.}$

1. $x^5- 1$

2. $x^6 + x^5 + x^4 + x^3 + x^2 + x + 1$

3. $x^9 - 1$

4. $x^4 +x^3 + x^2 + x + 1$

Hint

(a) $x^5 -1 = (x+1)(x^4+x^3 + x^2 + x+ 1)\text{;}$ (c) $x^9 -1 = (x+1)( x^2 + x+ 1)(x^6+x^3+1)\text{.}$

Exercise8

Prove or disprove: ${\mathbb Z}_2[x] / \langle x^3 + x + 1 \rangle \cong {\mathbb Z}_2[x] / \langle x^3 + x^2 + 1 \rangle\text{.}$

Hint

True.

Exercise11

Construct all BCH codes of

1. length 7.

2. length 15.

Hint

(a) Use the fact that $x^7 -1 = (x+1)( x^3 + x+ 1)(x^3+x^2+1)\text{.}$

Exercise12

Prove or disprove: There exists a finite field that is algebraically closed.

Hint

False.

Exercise17

Let $F \subset E \subset K$ be fields. If $K$ is a separable extension of $F\text{,}$ show that $K$ is also separable extension of $E\text{.}$

Hint

If $p(x) \in F[x]\text{,}$ then $p(x) \in E[x]\text{.}$

Exercise18

Let $E$ be an extension of a finite field $F\text{,}$ where $F$ has $q$ elements. Let $\alpha \in E$ be algebraic over $F$ of degree $n\text{.}$ Prove that $F( \alpha )$ has $q^n$ elements.

Hint

Since $\alpha$ is algebraic over $F$ of degree $n\text{,}$ we can write any element $\beta \in F(\alpha)$ uniquely as $\beta = a_0 + a_1 \alpha + \cdots + a_{n-1} \alpha^{n-1}$ with $a_i \in F\text{.}$ There are $q^n$ possible $n$-tuples $(a_0, a_1, \ldots, a_{n-1})\text{.}$

Exercise24Wilson's Theorem

Let $p$ be prime. Prove that $(p-1)! \equiv -1 \pmod{p}\text{.}$

Hint

Factor $x^{p-1} - 1$ over ${\mathbb Z}_p\text{.}$

Exercises23.4Exercises

Exercise1

Compute each of the following Galois groups. Which of these field extensions are normal field extensions? If the extension is not normal, find a normal extension of ${\mathbb Q}$ in which the extension field is contained.

1. $G({\mathbb Q}(\sqrt{30}\, ) / {\mathbb Q})$

2. $G({\mathbb Q}(\sqrt[4]{5}\, ) / {\mathbb Q})$

3. $G( {\mathbb Q}(\sqrt{2}, \sqrt{3}, \sqrt{5}\, )/ {\mathbb Q} )$

4. $G({\mathbb Q}(\sqrt{2}, \sqrt[3]{2}, i) / {\mathbb Q})$

5. $G({\mathbb Q}(\sqrt{6}, i) / {\mathbb Q})$

Hint

(a) ${\mathbb Z}_2\text{;}$ (c) ${\mathbb Z}_2 \times {\mathbb Z}_2 \times {\mathbb Z}_2\text{.}$

Exercise2

Determine the separability of each of the following polynomials.

1. $x^3 + 2 x^2 - x - 2$ over ${\mathbb Q}$

2. $x^4 + 2 x^2 + 1$ over ${\mathbb Q}$

3. $x^4 + x^2 + 1$ over ${\mathbb Z}_3$

4. $x^3 +x^2 + 1$ over ${\mathbb Z}_2$

Hint

(a) Separable over $\mathbb Q$ since $x^3 + 2 x^2 - x - 2 = (x - 1)(x + 1)(x + 2)\text{;}$ (c) not separable over $\mathbb Z_3$ since $x^4 + x^2 + 1 = (x + 1)^2 (x + 2)^2 \text{.}$

Exercise3

Give the order and describe a generator of the Galois group of $\gf(729)$ over $\gf(9)\text{.}$

Hint

If

$$\begin{equation*} [\gf(729): \gf(9)] = [\gf(729): \gf(3)] /[\gf(9): \gf(3)] = 6/2 = 3, \end{equation*}$$

then $G(\gf(729)/ \gf(9)) \cong {\mathbb Z}_3\text{.}$ A generator for $G(\gf(729)/ \gf(9))$ is $\sigma\text{,}$ where $\sigma_{3^6}( \alpha) = \alpha^{3^6} = \alpha^{729}$ for $\alpha \in \gf(729)\text{.}$

Exercise4

Determine the Galois groups of each of the following polynomials in ${\mathbb Q}[x]\text{;}$ hence, determine the solvability by radicals of each of the polynomials.

1. $x^5 - 12 x^2 + 2$

2. $x^5 - 4 x^4 + 2 x + 2$

3. $x^3 - 5$

4. $x^4 - x^2 - 6$

5. $x^5 + 1$

6. $(x^2 - 2)(x^2 + 2)$

7. $x^8 - 1$

8. $x^8 + 1$

9. $x^4 - 3 x^2 -10$

Hint

(a) $S_5\text{;}$ (c) $S_3\text{;}$ (g) see Example 23.10.

Exercise5

Find a primitive element in the splitting field of each of the following polynomials in ${\mathbb Q}[x]\text{.}$

1. $x^4 - 1$

2. $x^4 - 8 x^2 + 15$

3. $x^4 - 2 x^2 - 15$

4. $x^3 - 2$

Hint

(a) ${\mathbb Q}(i)$

Exercise7

Prove that the Galois group of an irreducible cubic polynomial is isomorphic to $S_3$ or ${\mathbb Z}_3\text{.}$

Hint

Let $E$ be the splitting field of a cubic polynomial in $F[x]\text{.}$ Show that $[E:F]$ is less than or equal to 6 and is divisible by 3. Since $G(E/F)$ is a subgroup of $S_3$ whose order is divisible by 3, conclude that this group must be isomorphic to ${\mathbb Z}_3$ or $S_3\text{.}$

Exercise9

Let $G$ be the Galois group of a polynomial of degree $n\text{.}$ Prove that $|G|$ divides $n!\text{.}$

Hint

$G$ is a subgroup of $S_n\text{.}$

Exercise16

Let $K$ be the splitting field of $x^3 + x^2 + 1 \in {\mathbb Z}_2[x]\text{.}$ Prove or disprove that $K$ is an extension by radicals.

Hint

True.

Exercise20

We know that the cyclotomic polynomial

$$\begin{equation*} \Phi_p(x) = \frac{x^p - 1}{x - 1} = x^{p - 1} + x^{p - 2} + \cdots + x + 1 \end{equation*}$$

is irreducible over ${\mathbb Q}$ for every prime $p\text{.}$ Let $\omega$ be a zero of $\Phi_p(x)\text{,}$ and consider the field ${\mathbb Q}(\omega)\text{.}$

1. Show that $\omega, \omega^2, \ldots, \omega^{p-1}$ are distinct zeros of $\Phi_p(x)\text{,}$ and conclude that they are all the zeros of $\Phi_p(x)\text{.}$

2. Show that $G( {\mathbb Q}( \omega ) / {\mathbb Q} )$ is abelian of order $p - 1\text{.}$

3. Show that the fixed field of $G( {\mathbb Q}( \omega ) / {\mathbb Q} )$ is ${\mathbb Q}\text{.}$

Hint

1. Clearly $\omega, \omega^2, \ldots, \omega^{p - 1}$ are distinct since $\omega \neq 1$ or 0. To show that $\omega^i$ is a zero of $\Phi_p\text{,}$ calculate $\Phi_p( \omega^i)\text{.}$

2. The conjugates of $\omega$ are $\omega, \omega^2, \ldots, \omega^{p - 1}\text{.}$ Define a map $\phi_i: {\mathbb Q}(\omega) \rightarrow {\mathbb Q}(\omega^i)$ by

   $$\begin{equation*} \phi_i(a_0 + a_1 \omega + \cdots + a_{p - 2} \omega^{p - 2}) = a_0 + a_1 \omega^i + \cdots + c_{p - 2} (\omega^i)^{p - 2}, \end{equation*}$$

   where $a_i \in {\mathbb Q}\text{.}$ Prove that $\phi_i$ is an isomorphism of fields. Show that $\phi_2$ generates $G({\mathbb Q}(\omega)/{\mathbb Q})\text{.}$

3. Show that $\{ \omega, \omega^2, \ldots, \omega^{p - 1} \}$ is a basis for ${\mathbb Q}( \omega )$ over ${\mathbb Q}\text{,}$ and consider which linear combinations of $\omega, \omega^2, \ldots, \omega^{p - 1}$ are left fixed by all elements of $G( {\mathbb Q}( \omega ) / {\mathbb Q})\text{.}$