Exercise1

Suppose that

Describe each of the following sets.

1. $A \cap B$

2. $B \cap C$

3. $A \cup B$

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

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$

Exercise6

Prove $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{.}$

Exercise14

Prove $A \setminus (B \cup 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}$

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$

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.

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.

Exercise23

Define a function on the real numbers by

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{.}$

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{.}$

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}$

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{.}$”

Exercise1

Prove that

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

Exercise3

Prove that $n! \gt 2^n$ for $n \geq 4\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

Exercise11

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

Exercise17Fibonacci Numbers

The Fibonacci numbers are

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.

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.

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{.}$

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{.}$

Exercise29

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

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}$

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*}

Exercise6

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

Exercise8

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

Exercise15

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

Exercise16

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

Exercise17

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

Exercise18

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

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{.}$

Exercise31

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

Exercise35

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

Exercise41

Prove that

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

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{.}$

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{.}$

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.

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}$

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$

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}$

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$

Exercise11

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

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)}$

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$

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}$

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}$

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}$

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{?}$

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{.}$

Exercise37

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

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*}

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}$

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)$

Exercise4

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

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{?}$

Exercise8

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

Exercise11

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

Exercise17

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

Exercise25

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

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{.}$

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{?}$

Exercise2

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

Exercise3

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

Exercise4

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

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$

Exercise7

Verify Euler's Theorem for $n = 15$ and $a = 4\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{.}$

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{.}$

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

Exercise1

Encode IXLOVEXMATH using the cryptosystem in Example 1.

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?

Exercise4

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

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$

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$

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)$

Exercise2

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

Exercise3

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

1. $(011010), (011100)$

2. $(11110101), (01010100)$

3. $(00110), (01111)$

4. $(1001), (0111)$

Exercise4

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

1. $(011010)$

2. $(11110101)$

3. $(01111)$

4. $(1011)$

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)$

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*}

Exercise9

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

Decode the message

if possible.

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*}

Exercise12

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

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*}

Exercise19

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

Exercise23

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

Exercise1

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

Exercise2

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

Exercise3

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

Exercise6

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

Exercise8

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

Exercise11

Find five non-isomorphic groups of order 8.

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}$

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.

Exercise20

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

Exercise25

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

Exercise27

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

Exercise38

Find $\aut( {\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.

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}$

Exercise8

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

Exercise11

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

Exercise12

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

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{.}$

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{.}$

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{.}$

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{.}$

Exercise5

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

Exercise9

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

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{.}$

Exercise1

Prove the identity

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*}

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{.}$

Exercise7

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

Exercise10

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

Exercise13

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

Exercise17

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

Exercise1

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

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}$

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.

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.

Exercise16

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

Exercise21

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

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

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) \}$

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{.}$

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$

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?

Exercise11

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

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?

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{?}$

Exercise22

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

Exercise1

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

Exercise2

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

Exercise5

Prove that no group of order 96 is simple.

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.

Exercise10

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

Exercise17

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

Exercise23

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

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.

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} \}$

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$

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}$

Exercise7

Prove that ${\mathbb R}$ is not isomorphic to ${\mathbb C}\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{.}$

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*}

Exercise16

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

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.

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.

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.

Exercise34

Let $p$ be prime. Prove that

is a ring. The ring ${\mathbb Z}_{(p)}$ is called the $p\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.

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}$

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]$

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$

Exercise7

Find a unit $p(x)$ in ${\mathbb Z}_4[x]$ such that $\deg p(x) \gt 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$

Exercise10

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

Exercise13

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

Exercise14

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

Exercise16

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

Exercise20Cyclotomic Polynomials

The polynomial

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.

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{.}$

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

Exercise4

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

Exercise9

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

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{.}$

Exercise16

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

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{.}$

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.

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.

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.

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{.}$

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{.}$

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{.}$

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{.}$

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 \}$

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{.}$

Exercise12

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

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

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.

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*}

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 }$

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. ${\mathbb Q}( \sqrt{2}, \root 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}\, )$

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}$

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.

Exercise8

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

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

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{.}$

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{.}$

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{.}$

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)]$

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{.}$

Exercise5

Construct a finite field of order 27.

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$

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{.}$

Exercise11

Construct all BCH codes of

1. length 7.

2. length 15.

Exercise12

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

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{.}$

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.

Exercise24Wilson's Theorem

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

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})$

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$

Exercise3

Give the order and describe a generator of the Galois group of $\gf(729)$ over $\gf(9)\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$

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$

Exercise7

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

Exercise9

Let $G$ be the Galois group of a polynomial of degree $n\text{.}$ Prove that $|G|$ divides $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.

Exercise20

We know that the cyclotomic polynomial

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{.}$