# 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
##### 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
##### Exercise6

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

Hint
##### Exercise10

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

Hint
##### Exercise14

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

Hint
##### 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
##### 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
##### 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
##### 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
##### 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
##### 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
##### 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
##### 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

# 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
##### Exercise3

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

Hint
##### 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
##### 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
##### 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
##### 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
##### Exercise23

Define the least common multiple 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 that any two integers $a$ and $b$ have a unique least common multiple.

Hint
##### 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
##### Exercise29

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

Hint

# 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
##### 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
##### Exercise6

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

Hint
##### Exercise8

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

Hint
##### Exercise15

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

Hint
##### Exercise16

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

Hint
##### Exercise17

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

Hint
##### Exercise18

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

Hint
##### 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
##### Exercise31

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

Hint
##### Exercise35

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

Hint
##### 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
##### 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
##### Exercise49

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

Hint

# Exercises4.5Exercises

##### 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
##### 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
##### 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
##### 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
##### 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
##### Exercise11

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

Hint
##### 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
##### 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
##### 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
##### 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
##### 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
##### 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
##### Exercise31

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

Hint
##### Exercise37

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

Hint