AATA Hints and Answers to Selected Exercises

Appendix B Hints and Answers to Selected Exercises

1 Preliminaries
1.4 Exercises

1.4.1.

Hint.

(a)

A \cap B = {2};

(b)

B \cap C = {5} .

1.4.2.

Hint.

(a)

A \times B = {(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3), (c, 1), (c, 2), (c, 3)};

(d)

A \times D = \emptyset .

1.4.6.

Hint.

Observe that

x \in A \cup B

if and only if

x \in A

x \in B .

Equivalently,

x \in B

x \in A,

which is the same as

x \in B \cup A .

Therefore,

A \cup B = B \cup A .

1.4.10.

Hint.

(A \cap B) \cup (A ∖ B) \cup (B ∖ 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 .

1.4.14.

Hint.

A ∖ (B \cup C) = A \cap (B \cup C)^{'} = (A \cap A) \cap (B^{'} \cap C^{'}) = (A \cap B^{'}) \cap (A \cap C^{'}) = (A ∖ B) \cap (A ∖ C) .

1.4.17.

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;

(d) this is a map.

1.4.18.

Hint.

(a)

f

is one-to-one but not onto.

f (R) = {x \in R : x > 0} .

(c)

f

is neither one-to-one nor onto.

f (R) = {x : - 1 \leq x \leq 1} .

1.4.20.

Hint.

(a)

f (n) = n + 1 .

1.4.22.

Hint.

(a) Let

x, y \in A .

Then

g (f (x)) = (g \circ f) (x) = (g \circ f) (y) = g (f (y)) .

Thus,

f (x) = f (y)

and

x = y,

g \circ f

is one-to-one. (b) Let

c \in C,

then

c = (g \circ f) (x) = g (f (x))

for some

x \in A .

Since

f (x) \in B,

g

is onto.

1.4.23.

Hint.

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

1.4.24.

Hint.

(a) Let

y \in f (A_{1} \cup A_{2}) .

Then there exists an

x \in A_{1} \cup A_{2}

such that

f (x) = y .

Hence,

y \in f (A_{1})

f (A_{2}) .

Therefore,

y \in f (A_{1}) \cup f (A_{2}) .

Consequently,

f (A_{1} \cup A_{2}) \subset f (A_{1}) \cup f (A_{2}) .

Conversely, if

y \in f (A_{1}) \cup f (A_{2}),

then

y \in f (A_{1})

f (A_{2}) .

Hence, there exists an

x

A_{1}

A_{2}

such that

f (x) = y .

Thus, there exists an

x \in A_{1} \cup A_{2}

such that

f (x) = y .

Therefore,

f (A_{1}) \cup f (A_{2}) \subset f (A_{1} \cup A_{2}),

and

f (A_{1} \cup A_{2}) = f (A_{1}) \cup f (A_{2}) .

1.4.25.

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.

1.4.28.

Hint.

Let

X = N \cup {\sqrt{2}}

and define

x \sim y

x + y \in N .

2 The Integers
2.4 Exercises

2.4.1.

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} + \dots + k^{2} = [k (k + 1) (2 k + 1)] / 6

is true. Then

\begin{aligned} 1^{2} + 2^{2} + \dots + k^{2} + (k + 1)^{2} & = [k (k + 1) (2 k + 1)] / 6 + (k + 1)^{2} \\ = [(k + 1) ((k + 1) + 1) (2 (k + 1) + 1)] / 6, \end{aligned}

and so

S (k + 1)

is true. Thus,

S (n)

is true for all positive integers

n .

2.4.3.

Hint.

The base case,

S (4) : 4! = 24 > 16 = 2^{4}

is true. Assume

S (k) : k! > 2^{k}

is true. Then

(k + 1)! = k! (k + 1) > 2^{k} \cdot 2 = 2^{k + 1},

S (k + 1)

is true. Thus,

S (n)

is true for all positive integers

n .

2.4.8.

Hint.

Follow the proof in Example 2.4.

2.4.11.

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 k x

is true. Then

\begin{aligned} (1 + x)^{k + 1} - 1 & = (1 + x) (1 + x)^{k} - 1 \\ = (1 + x)^{k} + x (1 + x)^{k} - 1 \\ \geq k x + x (1 + x)^{k} \\ \geq k x + x \\ = (k + 1) x, \end{aligned}

S (k + 1)

is true. Therefore,

S (n)

is true for all positive integers

n .

2.4.17. Fibonacci Numbers.

Hint.

For (a) and (b) use mathematical induction. (c) Show that

f_{1} = 1,

f_{2} = 1,

and

f_{n + 2} = f_{n + 1} + f_{n} .

(e) Use part (b) and Exercise 2.4.16.

2.4.19.

Hint.

Use the Fundamental Theorem of Arithmetic.

2.4.23.

Hint.

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

2.4.27.

Hint.

Since

gcd (a, b) = 1,

there exist integers

r

and

s

such that

a r + b s = 1 .

Thus,

a c r + b c s = c .

2.4.29.

Hint.

Every prime must be of the form

2,

3,

6 n + 1,

6 n + 5 .

Suppose there are only finitely many primes of the form

6 k + 5 .

3 Groups
3.5 Exercises

3.5.1.

Hint.

(a)

3 + 7 Z = {\dots, - 4, 3, 10, \dots};

(c)

18 + 26 Z;

(e)

5 + 6 Z .

3.5.2.

Hint.

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

3.5.6.

Hint.

\begin{array}{ccccc} \cdot & 1 & 5 & 7 & 11 \\ 1 & 1 & 5 & 7 & 11 \\ 5 & 5 & 1 & 11 & 7 \\ 7 & 7 & 11 & 1 & 5 \\ 11 & 11 & 7 & 5 & 1 \end{array}

3.5.8.

Hint.

Pick two matrices. Almost any pair will work.

3.5.15.

Hint.

There is a nonabelian group containing six elements.

3.5.16.

Hint.

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

3.5.17.

Hint.

The are five different groups of order 8.

3.5.18.

Hint.

Let

σ = (\begin{matrix} 1 & 2 & \dots & n \\ a_{1} & a_{2} & \dots & a_{n} \end{matrix})

be in

S_{n} .

All of the

a_{i}

s must be distinct. There are

n

ways to choose

a_{1},

n - 1

ways to choose

a_{2}, \dots,

2 ways to choose

a_{n - 1},

and only one way to choose

a_{n} .

Therefore, we can form

σ

n (n - 1) \dots 2 \cdot 1 = n!

ways.

3.5.25.

Hint.

\begin{aligned} (a b a^{- 1})^{n} & = (a b a^{- 1}) (a b a^{- 1}) \dots (a b a^{- 1}) \\ = a b (a a^{- 1}) b (a a^{- 1}) b \dots b (a a^{- 1}) b a^{- 1} \\ = a b^{n} a^{- 1} . \end{aligned}

3.5.31.

Hint.

Since

a b a b = (a b)^{2} = e = a^{2} b^{2} = a a b b,

we know that

b a = a b .

3.5.35.

Hint.

H_{1} = {id},

H_{2} = {id, ρ_{1}, ρ_{2}},

H_{3} = {id, μ_{1}},

H_{4} = {id, μ_{2}},

H_{5} = {id, μ_{3}},

S_{3} .

3.5.41.

Hint.

The identity of

G

1 = 1 + 0 \sqrt{2} .

Since

(a + b \sqrt{2}) (c + d \sqrt{2}) = (a c + 2 b d) + (a d + b c) \sqrt{2},

G

is closed under multiplication. Finally,

(a + b \sqrt{2})^{- 1} = a / (a^{2} - 2 b^{2}) - b \sqrt{2} / (a^{2} - 2 b^{2}) .

3.5.46.

Hint.

Look at

S_{3} .

3.5.49.

Hint.

b a = a^{4} b = a^{3} a b = a b

4 Cyclic Groups
4.5 Exercises

4.5.1.

Hint.

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

4.5.2.

Hint.

(a)

12;

10 .

4.5.3.

Hint.

(a)

7 Z = {\dots, - 7, 0, 7, 14, \dots};

(b)

{0, 3, 6, 9, 12, 15, 18, 21};

(c)

{0},

{0, 6},

{0, 4, 8},

{0, 3, 6, 9},

{0, 2, 4, 6, 8, 10};

(g)

{1, 3, 7, 9};

(j)

{1, - 1, i, - i} .

4.5.4.

Hint.

(a)

(\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}), (\begin{matrix} - 1 & 0 \\ 0 & - 1 \end{matrix}), (\begin{matrix} 0 & - 1 \\ 1 & 0 \end{matrix}), (\begin{matrix} 0 & 1 \\ - 1 & 0 \end{matrix}) .

(c)

(\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}), (\begin{matrix} 1 & - 1 \\ 1 & 0 \end{matrix}), (\begin{matrix} - 1 & 1 \\ - 1 & 0 \end{matrix}), (\begin{matrix} 0 & 1 \\ - 1 & 1 \end{matrix}), (\begin{matrix} 0 & - 1 \\ 1 & - 1 \end{matrix}), (\begin{matrix} - 1 & 0 \\ 0 & - 1 \end{matrix}) .

4.5.10.

Hint.

(a)

0;

(b)

1, - 1 .

4.5.11.

Hint.

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

4.5.15.

Hint.

(a)

- 3 + 3 i;

(c)

43 - 18 i;

(e)

i

4.5.16.

Hint.

(a)

\sqrt{3} + i;

(c)

- 3 .

4.5.17.

Hint.

(a)

\sqrt{2} cis (7 π / 4);

(c)

2 \sqrt{2} cis (π / 4);

(e)

3 cis (3 π / 2) .

4.5.18.

Hint.

(a)

(1 - i) / 2;

(c)

16 (i - \sqrt{3});

(e)

- 1 / 4 .

4.5.22.

Hint.

(a)

292;

(c)

1523 .

4.5.27.

Hint.

| ⟨ g ⟩ \cap ⟨ h ⟩ | = 1 .

4.5.31.

Hint.

The identity element in any group has finite order. Let

g, h \in G

have orders

m

and

n,

respectively. Since

(g^{- 1})^{m} = e

and

(g h)^{m n} = e,

the elements of finite order in

G

form a subgroup of

G .

4.5.37.

Hint.

g

is an element distinct from the identity in

G,

g

must generate

G;

otherwise,

⟨ g ⟩

is a nontrivial proper subgroup of

G .

5 Permutation Groups
5.4 Exercises

5.4.1.

Hint.

(a)

(1 2 4 5 3);

(c)

(1 3) (2 5) .

5.4.2.

Hint.

(a)

(1 3 5) (2 4);

(c)

(1 4) (2 3);

(e)

(1 3 2 4);

(g)

(1 3 4) (2 5);

(n)

(1 7 3 5 2) .

5.4.3.

Hint.

(a)

(1 6) (1 5) (1 3) (1 4);

(c)

(1 6) (1 4) (1 2) .

5.4.4.

Hint.

(a_{1}, a_{2}, \dots, a_{n})^{- 1} = (a_{1}, a_{n}, a_{n - 1}, \dots, a_{2})

5.4.5.

Hint.

(a)

{(1 3), (1 3) (2 4), (1 3 2), (1 3 4), (1 3 2 4), (1 3 4 2)}

is not a subgroup.

5.4.8.

Hint.

(1 2 3 4 5) (6 7 8) .

5.4.11.

Hint.

Permutations of the form

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

are possible for

A_{5} .

5.4.17.

Hint.

Calculate

(1 2 3) (1 2)

and

(1 2) (1 2 3) .

5.4.25.

Hint.

Consider the cases

(a, b) (b, c)

and

(a, b) (c, d) .

5.4.29.

Hint.

Show that the center of

D_{n}

consists of the identity if

n

is odd and consists of the identity and a

180^{\circ}

rotation if

n

is even.

5.4.30.

Hint.

For (a), show that

σ τ σ^{- 1} (σ (a_{i})) = σ (a_{i + 1}) .

6 Cosets and Lagrange’s Theorem
6.5 Exercises

6.5.1.

Hint.

The order of

g

and the order

h

must both divide the order of

G .

6.5.2.

Hint.

The possible orders must divide

60 .

6.5.3.

Hint.

This is true for every proper nontrivial subgroup.

6.5.4.

Hint.

False.

6.5.5.

Hint.

(a)

⟨ 8 ⟩,

1 + ⟨ 8 ⟩,

2 + ⟨ 8 ⟩,

3 + ⟨ 8 ⟩,

4 + ⟨ 8 ⟩,

5 + ⟨ 8 ⟩,

6 + ⟨ 8 ⟩,

and

7 + ⟨ 8 ⟩;

(c)

3 Z,

1 + 3 Z,

and

2 + 3 Z .

6.5.7.

Hint.

4^{ϕ (15)} \equiv 4^{8} \equiv 1 (\mod 15) .

6.5.12.

Hint.

Let

g_{1} \in g H .

Show that

g_{1} \in H g

and thus

g H \subset H g .

6.5.19.

Hint.

Show that

g (H \cap K) = g H \cap g K .

6.5.22.

Hint.

gcd (m, n) = 1,

then

ϕ (m n) = ϕ (m) ϕ (n)

(Exercise 2.4.26 in Chapter 2).

7 Introduction to Cryptography
7.4 Exercises

7.4.1.

Hint.

LAORYHAPDWK

7.4.3.

Hint.

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

7.4.4.

Hint.

26! - 1

7.4.7.

Hint.

(a)

2791;

(c)

11213525032442 .

7.4.9.

Hint.

(a)

31

(c)

14 .

7.4.10.

Hint.

(a)

n = 11 \cdot 41;

(c)

n = 8779 \cdot 4327 .

8 Algebraic Coding Theory
8.6 Exercises

8.6.2.

Hint.

This cannot be a group code since

(0000) \notin C .

8.6.3.

Hint.

(a)

2;

(c)

2 .

8.6.4.

Hint.

(a)

3;

(c)

4 .

8.6.6.

Hint.

(a)

d_{min} = 2;

(c)

d_{min} = 1 .

8.6.7.

Hint.

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

$G = (\begin{matrix} 0 & 1 \\ 0 & 0 \\ 1 & 0 \\ 0 & 1 \\ 1 & 1 \end{matrix})$
$(000000), (010111), (101101), (111010)$

$G = (\begin{matrix} 1 & 0 \\ 0 & 1 \\ 1 & 0 \\ 1 & 1 \\ 0 & 1 \\ 1 & 1 \end{matrix})$

8.6.9.

Hint.

Multiple errors occur in one of the received words.

8.6.11.

Hint.

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

G = (\begin{matrix} 1 \\ 1 \\ 0 \\ 0 \\ 1 \end{matrix}) .

G = (\begin{matrix} 1 & 0 \\ 0 & 1 \\ 1 & 1 \\ 1 & 0 \end{matrix}) .

8.6.12.

Hint.

(a) All possible syndromes occur.

8.6.15.

Hint.

(a)

C,

(10000) + C,

(01000) + C,

(00100) + C,

(00010) + C,

(11000) + C,

(01100) + C,

(01010) + C .

A decoding table does not exist for

C

since this is only a single error-detecting code.

8.6.19.

Hint.

Let

x \in C

have odd weight and define a map from the set of odd codewords to the set of even codewords by

y \mapsto x + y .

Show that this map is a bijection.

8.6.23.

Hint.

For

20

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

9 Isomorphisms
9.4 Exercises

9.4.1.

Hint.

Every infinite cyclic group is isomorphic to

Z

by Theorem 9.7.

9.4.2.

Hint.

Define

ϕ : C^{*} \to G L_{2} (R)

ϕ (a + b i) = (\begin{matrix} a & b \\ - b & a \end{matrix}) .

9.4.3.

Hint.

False.

9.4.6.

Hint.

Define a map from

Z_{n}

into the

n

th roots of unity by

k \mapsto cis (2 k π / n) .

9.4.8.

Hint.

Assume that

Q

is cyclic and try to find a generator.

9.4.11.

Hint.

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

9.4.16.

Hint.

(a)

12;

(c)

5 .

9.4.19.

Hint.

Draw the picture.

9.4.20.

Hint.

True.

9.4.25.

Hint.

True.

9.4.27.

Hint.

Let

a

be a generator for

G .

ϕ : G \to H

is an isomorphism, show that

ϕ (a)

is a generator for

H .

9.4.38.

Hint.

Any automorphism of

Z_{6}

must send 1 to another generator of

Z_{6} .

9.4.45.

Hint.

To show that

ϕ

is one-to-one, let

g_{1} = h_{1} k_{1}

and

g_{2} = h_{2} k_{2}

and consider

ϕ (g_{1}) = ϕ (g_{2}) .

10 Normal Subgroups and Factor Groups
10.4 Exercises

10.4.1.

Hint.

(a)

\begin{array}{ccc} A_{4} & (1 2) A_{4} \\ A_{4} & A_{4} & (1 2) A_{4} \\ (1 2) A_{4} & (1 2) A_{4} & A_{4} \end{array}

(c)

D_{4}

is not normal in

S_{4} .

10.4.8.

Hint.

a \in G

is a generator for

G,

then

a H

is a generator for

G / H .

10.4.11.

Hint.

For any

g \in G,

show that the map

i_{g} : G \to G

defined by

i_{g} : x \mapsto g x g^{- 1}

is an isomorphism of

G

with itself. Then consider

i_{g} (H) .

10.4.12.

Hint.

Suppose that

⟨ g ⟩

is normal in

G

and let

y

be an arbitrary element of

G .

x \in C (g),

we must show that

y x y^{- 1}

is also in

C (g) .

Show that

(y x y^{- 1}) g = g (y x y^{- 1}) .

10.4.14.

Hint.

(a) Let

g \in G

and

h \in G^{'} .

h = a b a^{- 1} b^{- 1},

then

\begin{aligned} g h g^{- 1} & = g a b a^{- 1} b^{- 1} g^{- 1} \\ = (g a g^{- 1}) (g b g^{- 1}) (g a^{- 1} g^{- 1}) (g b^{- 1} g^{- 1}) \\ = (g a g^{- 1}) (g b g^{- 1}) (g a g^{- 1})^{- 1} (g b g^{- 1})^{- 1} . \end{aligned}

We also need to show that if

h = h_{1} \dots h_{n}

with

h_{i} = a_{i} b_{i} a_{i}^{- 1} b_{i}^{- 1},

then

g h g^{- 1}

is a product of elements of the same type. However,

g h g^{- 1} = g h_{1} \dots h_{n} g^{- 1} = (g h_{1} g^{- 1}) (g h_{2} g^{- 1}) \dots (g h_{n} g^{- 1}) .

11 Homomorphisms
11.4 Exercises

11.4.2.

Hint.

(a) is a homomorphism with kernel

{1};

11.4.4.

Hint.

Since

ϕ (m + n) = 7 (m + n) = 7 m + 7 n = ϕ (m) + ϕ (n),

ϕ

is a homomorphism.

11.4.5.

Hint.

For any homomorphism

ϕ : Z_{24} \to Z_{18},

the kernel of

ϕ

must be a subgroup of

Z_{24}

and the image of

ϕ

must be a subgroup of

Z_{18} .

Now use the fact that a generator must map to a generator.

11.4.9.

Hint.

Let

a, b \in G .

Then

ϕ (a) ϕ (b) = ϕ (a b) = ϕ (b a) = ϕ (b) ϕ (a) .

11.4.17.

Hint.

Find a counterexample.

12 Matrix Groups and Symmetry
12.4 Exercises

12.4.1.

Hint.

\begin{aligned} \frac{1}{2} [‖ x + y ‖^{2} + ‖ x ‖^{2} - ‖ y ‖^{2}] & = \frac{1}{2} [⟨ x + y, x + y ⟩ - ‖ x ‖^{2} - ‖ y ‖^{2}] \\ = \frac{1}{2} [‖ x ‖^{2} + 2 ⟨ x, y ⟩ + ‖ y ‖^{2} - ‖ x ‖^{2} - ‖ y ‖^{2}] \\ = ⟨ x, y ⟩ . \end{aligned}

12.4.3.

Hint.

(a) is in

S O (2);

O (3) .

12.4.5.

Hint.

(a)

⟨ x, y ⟩ = ⟨ y, x ⟩ .

12.4.7.

Hint.

Use the unimodular matrix

(\begin{matrix} 5 & 2 \\ 2 & 1 \end{matrix}) .

12.4.10.

Hint.

Show that the kernel of the map

det : O (n) \to R^{*}

S O (n) .

12.4.13.

Hint.

True.

12.4.17.

Hint.

p 6 m

13 The Structure of Groups
13.4 Exercises

13.4.1.

Hint.

There are three possible groups.

13.4.4.

Hint.

(a)

{0} \subset ⟨ 6 ⟩ \subset ⟨ 3 ⟩ \subset Z_{12};

(e)

{(1)} \times {0} \subset {(1), (1 2 3), (1 3 2)} \times {0} \subset S_{3} \times {0} \subset S_{3} \times ⟨ 2 ⟩ \subset S_{3} \times Z_{4} .

13.4.7.

Hint.

Use the Fundamental Theorem of Finitely Generated Abelian Groups.

13.4.12.

Hint.

N

and

G / N

are solvable, then they have solvable series

\begin{matrix} N = N_{n} \supset N_{n - 1} \supset \dots \supset N_{1} \supset N_{0} = {e} \\ G / N = G_{n} / N \supset G_{n - 1} / N \supset \dots G_{1} / N \supset G_{0} / N = {N} . \end{matrix}

13.4.16.

Hint.

Use the fact that

D_{n}

has a cyclic subgroup of index

2 .

13.4.21.

Hint.

G / G^{'}

is abelian.

14 Group Actions
14.5 Exercises

14.5.1.

Hint.

Example 14.1:

0,

R^{2} ∖ {0} .

Example 14.2:

X = {1, 2, 3, 4} .

14.5.2.

Hint.

(a)

X_{(1)} = {1, 2, 3},

X_{(1 2)} = {3},

X_{(1 3)} = {2},

X_{(2 3)} = {1},

X_{(1 2 3)} = X_{(1 3 2)} = \emptyset .

G_{1} = {(1), (2 3)},

G_{2} = {(1), (1 3)},

G_{3} = {(1), (1 2)} .

14.5.3.

Hint.

(a)

O_{1} = O_{2} = O_{3} = {1, 2, 3} .

14.5.6.

Hint.

The conjugacy classes for

S_{4}

are

\begin{matrix} O_{(1)} = {(1)}, \\ O_{(12)} = {(1 2), (1 3), (1 4), (2 3), (2 4), (3 4)}, \\ O_{(1 2) (3 4)} = {(1 2) (3 4), (1 3) (2 4), (1 4) (2 3)}, \\ O_{(123)} = {(1 2 3), (1 3 2), (1 2 4), (1 4 2), (1 3 4), (1 4 3), (2 3 4), (2 4 3)}, \\ O_{(1234)} = {(1 2 3 4), (1 2 4 3), (1 3 2 4), (1 3 4 2), (1 4 2 3), (1 4 3 2)} . \end{matrix}

The class equation is

1 + 3 + 6 + 6 + 8 = 24 .

14.5.8.

Hint.

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

14.5.11.

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

There are the identity cycle, 6 permutations with the structure

(a b c d)

that correspond to the quarter turns, 3 permutations with the structure

(a b) (c d)

that correspond to the half turns, 6 permutations with the structure

(a b) (c d) (e f)

that correspond to rotating the cube about the centers of opposite edges, and 8 permutations with the structure

(a b c) (d e f)

that correspond to rotating the cube about opposite vertices.

14.5.15.

Hint.

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

14.5.17.

Hint.

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

14.5.22.

Hint.

Use the fact that

x \in g C (a) g^{- 1}

if and only if

g^{- 1} x g \in C (a) .

15 The Sylow Theorems
15.4 Exercises

15.4.1.

Hint.

| G | = 18 = 2 \cdot 3^{2},

then the order of a Sylow

2

-subgroup is

2,

and the order of a Sylow

3

-subgroup is

9 .

15.4.2.

Hint.

The four Sylow

3

-subgroups of

S_{4}

are

P_{1} = {(1), (1 2 3), (1 3 2)},

P_{2} = {(1), (1 2 4), (1 4 2)},

P_{3} = {(1), (1 3 4), (1 4 3)},

P_{4} = {(1), (2 3 4), (2 4 3)} .

15.4.5.

Hint.

Since

| G | = 96 = 2^{5} \cdot 3,

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;

otherwise,

H K

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.

15.4.8.

Hint.

Show that

G

has a normal Sylow

p

-subgroup of order

p^{2}

and a normal Sylow

q

-subgroup of order

q^{2} .

15.4.10.

Hint.

False.

15.4.17.

Hint.

G

is abelian, then

G

is cyclic, since

| G | = 3 \cdot 5 \cdot 17 .

Now look at Example 15.14.

15.4.23.

Hint.

Define a mapping between the right cosets of

N (H)

G

and the conjugates of

H

G

N (H) g \mapsto g^{- 1} H g .

Prove that this map is a bijection.

15.4.26.

Hint.

Let

a G^{'}, b G^{'} \in G / G^{'} .

Then

(a G^{'}) (b G^{'}) = a b G^{'} = a b (b^{- 1} a^{- 1} b a) G^{'} = (a b b^{- 1} a^{- 1}) b a G^{'} = b a G^{'} .

16 Rings
16.7 Exercises

16.7.1.

Hint.

(a)

7 Z

is a ring but not a field; (c)

Q (\sqrt{2})

is a field; (f)

R

is not a ring.

16.7.3.

Hint.

(a)

{1, 3, 7, 9};

(c)

{1, 2, 3, 4, 5, 6};

(e)

{(\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}), (\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix}), (\begin{matrix} 1 & 0 \\ 1 & 1 \end{matrix}), (\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}), (\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}), (\begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix}),} .

16.7.4.

Hint.

(a)

{0},

{0, 9},

{0, 6, 12},

{0, 3, 6, 9, 12, 15},

{0, 2, 4, 6, 8, 10, 12, 14, 16};

16.7.7.

Hint.

Assume there is an isomorphism

ϕ : C \to R

with

ϕ (i) = a .

16.7.8.

Hint.

False. Assume there is an isomorphism

ϕ : Q (\sqrt{2}) \to Q (\sqrt{3})

such that

ϕ (\sqrt{2}) = a .

16.7.13.

Hint.

(a)

x \equiv 17 (\mod 55);

(c)

x \equiv 214 (\mod 2772) .

16.7.16.

Hint.

I \neq {0},

show that

1 \in I .

16.7.18.

Hint.

(a)

ϕ (a) ϕ (b) = ϕ (a b) = ϕ (b a) = ϕ (b) ϕ (a) .

16.7.26.

Hint.

Let

a \in R

with

a \neq 0 .

Then the principal ideal generated by

a

R .

Thus, there exists a

b \in R

such that

a b = 1 .

16.7.28.

Hint.

Compute

(a + b)^{2}

and

(- a b)^{2} .

16.7.33.

Hint.

Let

a / b, c / d \in Z_{(p)} .

Then

a / b + c / d = (a d + b c) / b d

and

(a / b) \cdot (c / d) = (a c) / (b d)

are both in

Z_{(p)},

since

gcd (b d, p) = 1 .

16.7.37.

Hint.

Suppose that

x^{2} = x

and

x \neq 0 .

Since

R

is an integral domain,

x = 1 .

To find a nontrivial idempotent, look in

M_{2} (R) .

17 Polynomials
17.5 Exercises

17.5.2.

Hint.

(a)

9 x^{2} + 2 x + 5;

(b)

8 x^{4} + 7 x^{3} + 2 x^{2} + 7 x .

17.5.3.

Hint.

(a)

5 x^{3} + 6 x^{2} - 3 x + 4 = (5 x^{2} + 2 x + 1) (x - 2) + 6;

(c)

4 x^{5} - x^{3} + x^{2} + 4 = (4 x^{2} + 4) (x^{3} + 3) + 4 x^{2} + 2 .

17.5.5.

Hint.

(a) No zeros in

Z_{12};

(c)

3,

4 .

17.5.7.

Hint.

Look at

(2 x + 1) .

17.5.8.

Hint.

(a) Reducible; (c) irreducible.

17.5.10.

Hint.

One factorization is

x^{2} + x + 8 = (x + 2) (x + 9) .

17.5.13.

Hint.

The integers

Z

do not form a field.

17.5.14.

Hint.

False.

17.5.16.

Hint.

Let

ϕ : R \to S

be an isomorphism. Define

\overset{―}{ϕ} : R [x] \to S [x]

\overset{―}{ϕ} (a_{0} + a_{1} x + \dots + a_{n} x^{n}) = ϕ (a_{0}) + ϕ (a_{1}) x + \dots + ϕ (a_{n}) x^{n} .

17.5.20. Cyclotomic Polynomials.

Hint.

The polynomial

Φ_{n} (x) = \frac{x^{n} - 1}{x - 1} = x^{n - 1} + x^{n - 2} + \dots + x + 1

is called the cyclotomic polynomial. Show that

Φ_{p} (x)

is irreducible over

Q

for any prime

p .

17.5.26.

Hint.

Find a nontrivial proper ideal in

F [x] .

18 Integral Domains
18.4 Exercises

18.4.1.

Hint.

Note that

z^{- 1} = 1 / (a + b \sqrt{3} i) = (a - b \sqrt{3} i) / (a^{2} + 3 b^{2})

is in

Z [\sqrt{3} i]

if and only if

a^{2} + 3 b^{2} = 1 .

The only integer solutions to the equation are

a = \pm 1, b = 0 .

18.4.2.

Hint.

(a)

5 = - i (1 + 2 i) (2 + i);

(c)

6 + 8 i = - i (1 + i)^{2} (2 + i)^{2} .

18.4.4.

Hint.

True.

18.4.9.

Hint.

Let

z = a + b i

and

w = c + d i \neq 0

be in

Z [i] .

Prove that

z / w \in Q (i) .

18.4.15.

Hint.

Let

a = u b

with

u

a unit. Then

ν (b) \leq ν (u b) \leq ν (a) .

Similarly,

ν (a) \leq ν (b) .

18.4.16.

Hint.

Show that 21 can be factored in two different ways.

19 Lattices and Boolean Algebras
19.5 Exercises

19.5.2.

Hint.

$A graph with 30 at the top level which is connected to 10 and 15 at the second level. The third level has 2, which is connected to 30 and 10, and 5, which is connected to 10 and 15, and 3 which is connected to 15. The bottom level is 1 which is connected to 2, 3, and 5.$

19.5.4.

Hint.

What are the atoms of

B ?

19.5.5.

Hint.

False.

19.5.6.

Hint.

(a)

(a \lor b \lor a^{'}) \land a

$A graph from left to right which splits into three paths, a b, and b’ and then rejoins into a single path and goes through a.$

(c)

a \lor (a \land b)

$A graph from left to right which splits into two paths and then rejoins. The top path is a then b. The bottom path is a.$

19.5.8.

Hint.

Not equivalent.

19.5.10.

Hint.

(a)

a^{'} \land [(a \land b^{'}) \lor b] = a \land (a \lor b) .

19.5.14.

Hint.

Let

I, J

be ideals in

R .

We need to show that

I + J = {r + s : r \in I and s \in J}

is the smallest ideal in

R

containing both

I

and

J .

r_{1}, r_{2} \in I

and

s_{1}, s_{2} \in J,

then

(r_{1} + s_{1}) + (r_{2} + s_{2}) = (r_{1} + r_{2}) + (s_{1} + s_{2})

is in

I + J .

For

a \in R,

a (r_{1} + s_{1}) = a r_{1} + a s_{1} \in I + J;

hence,

I + J

is an ideal in

R .

19.5.18.

Hint.

(a) No.

19.5.20.

Hint.

(\Rightarrow) .

a = b \Rightarrow (a \land b^{'}) \lor (a^{'} \land b) = (a \land a^{'}) \lor (a^{'} \land a) = O \lor O = O .

(\Leftarrow) .

(a \land b^{'}) \lor (a^{'} \land b) = O \Rightarrow a \lor b = (a \lor a) \lor b = a \lor (a \lor b) = a \lor [I \land (a \lor b)] = a \lor [(a \lor a^{'}) \land (a \lor b)] = [a \lor (a \land b^{'})] \lor [a \lor (a^{'} \land b)] = a \lor [(a \land b^{'}) \lor (a^{'} \land b)] = a \lor 0 = a .

A symmetric argument shows that

a \lor b = b .

20 Vector Spaces
20.5 Exercises

20.5.3.

Hint.

Q (\sqrt{2}, \sqrt{3})

has basis

{1, \sqrt{2}, \sqrt{3}, \sqrt{6}}

over

Q .

20.5.5.

Hint.

The set

{1, x, x^{2}, \dots, x^{n - 1}}

is a basis for

P_{n} .

20.5.7.

Hint.

(a) Subspace of dimension

2

with basis

{(1, 0, - 3), (0, 1, 2)};

(d) not a subspace

20.5.10.

Hint.

Since

0 = α 0 = α (- v + v) = α (- v) + α v,

it follows that

- α v = α (- v) .

20.5.12.

Hint.

Let

v_{0} = 0, v_{1}, \dots, v_{n} \in V

and

α_{0} \neq 0, α_{1}, \dots, α_{n} \in F .

Then

α_{0} v_{0} + \dots + α_{n} v_{n} = 0 .

20.5.15. Linear Transformations.

Hint.

(a) Let

u, v \in \ker (T)

and

α \in F .

Then

\begin{matrix} T (u + v) = T (u) + T (v) = 0 \\ T (α v) = α T (v) = α 0 = 0 . \end{matrix}

Hence,

u + v, α v \in \ker (T),

and

\ker (T)

is a subspace of

V .

T (u) = T (v)

is equivalent to

T (u - v) = T (u) - T (v) = 0,

which is true if and only if

u - v = 0

u = v .

20.5.17. Direct Sums.

Hint.

(a) Let

u, u^{'} \in U

and

v, v^{'} \in V .

Then

\begin{aligned} (u + v) + (u^{'} + v^{'}) & = (u + u^{'}) + (v + v^{'}) \in U + V \\ α (u + v) & = α u + α v \in U + V . \end{aligned}

21 Fields
21.5 Exercises

21.5.1.

Hint.

(a)

x^{4} - (2 / 3) x^{2} - 62 / 9;

(c)

x^{4} - 2 x^{2} + 25 .

21.5.2.

Hint.

(a)

{1, \sqrt{2}, \sqrt{3}, \sqrt{6}};

(c)

{1, i, \sqrt{2}, \sqrt{2} i};

(e)

{1, 2^{1 / 6}, 2^{1 / 3}, 2^{1 / 2}, 2^{2 / 3}, 2^{5 / 6}} .

21.5.3.

Hint.

(a)

Q (\sqrt{3}, \sqrt{7}) .

21.5.5.

Hint.

Use the fact that the elements of

Z_{2} [x] / ⟨ x^{3} + x + 1 ⟩

are 0, 1,

α,

1 + α,

α^{2},

1 + α^{2},

α + α^{2},

1 + α + α^{2}

and the fact that

α^{3} + α + 1 = 0 .

21.5.8.

Hint.

False.

21.5.14.

Hint.

Suppose that

E

is algebraic over

F

and

K

is algebraic over

E .

Let

α \in K .

It suffices to show that

α

is algebraic over some finite extension of

F .

Since

α

is algebraic over

E,

it must be the zero of some polynomial

p (x) = β_{0} + β_{1} x + \dots + β_{n} x^{n}

E [x] .

Hence

α

is algebraic over

F (β_{0}, \dots, β_{n}) .

21.5.22.

Hint.

Since

{1, \sqrt{3}, \sqrt{7}, \sqrt{21}}

is a basis for

Q (\sqrt{3}, \sqrt{7})

over

Q,

Q (\sqrt{3}, \sqrt{7}) \supset Q (\sqrt{3} + \sqrt{7}) .

Since

[Q (\sqrt{3}, \sqrt{7}) : Q] = 4,

[Q (\sqrt{3} + \sqrt{7}) : Q] = 2

or 4. Since the degree of the minimal polynomial of

\sqrt{3} + \sqrt{7}

is 4,

Q (\sqrt{3}, \sqrt{7}) = Q (\sqrt{3} + \sqrt{7}) .

21.5.27.

Hint.

Let

β \in F (α)

not in

F .

Then

β = p (α) / q (α),

where

p

and

q

are polynomials in

α

with

q (α) \neq 0

and coefficients in

F .

β

is algebraic over

F,

then there exists a polynomial

f (x) \in F [x]

such that

f (β) = 0 .

Let

f (x) = a_{0} + a_{1} x + \dots + a_{n} x^{n} .

Then

0 = f (β) = f (\frac{p (α)}{q (α)}) = a_{0} + a_{1} (\frac{p (α)}{q (α)}) + \dots + a_{n} {(\frac{p (α)}{q (α)})}^{n} .

Now multiply both sides by

q (α)^{n}

to show that there is a polynomial in

F [x]

that has

α

as a zero.

21.5.28.

Hint.

See the comments following Theorem 21.13.

22 Finite Fields
22.4 Exercises

22.4.1.

Hint.

Make sure that you have a field extension.

22.4.4.

Hint.

There are eight elements in

Z_{2} (α) .

Exhibit two more zeros of

x^{3} + x^{2} + 1

other than

α

in these eight elements.

22.4.5.

Hint.

Find an irreducible polynomial

p (x)

Z_{3} [x]

of degree

3

and show that

Z_{3} [x] / ⟨ p (x) ⟩

has

27

elements.

22.4.7.

Hint.

(a)

x^{5} - 1 = (x + 1) (x^{4} + x^{3} + x^{2} + x + 1);

(c)

x^{9} - 1 = (x + 1) (x^{2} + x + 1) (x^{6} + x^{3} + 1) .

22.4.8.

Hint.

True.

22.4.11.

Hint.

(a) Use the fact that

x^{7} - 1 = (x + 1) (x^{3} + x + 1) (x^{3} + x^{2} + 1) .

22.4.12.

Hint.

False.

22.4.17.

Hint.

p (x) \in F [x],

then

p (x) \in E [x] .

22.4.18.

Hint.

Since

α

is algebraic over

F

of degree

n,

we can write any element

β \in F (α)

uniquely as

β = a_{0} + a_{1} α + \dots + a_{n - 1} α^{n - 1}

with

a_{i} \in F .

There are

q^{n}

possible

n

-tuples

(a_{0}, a_{1}, \dots, a_{n - 1}) .

22.4.24. Wilson’s Theorem.

Hint.

Factor

x^{p - 1} - 1

over

Z_{p} .

23 Galois Theory
23.5 Exercises

23.5.1.

Hint.

(a)

Z_{2};

(c)

Z_{2} \times Z_{2} \times Z_{2} .

23.5.2.

Hint.

(a) Separable over

Q

since

x^{3} + 2 x^{2} - x - 2 = (x - 1) (x + 1) (x + 2);

Z_{3}

since

x^{4} + x^{2} + 1 = (x + 1)^{2} (x + 2)^{2} .

23.5.3.

Hint.

[GF (729) : GF (9)] = [GF (729) : GF (3)] / [GF (9) : GF (3)] = 6 / 2 = 3,

then

G (GF (729) / GF (9)) ≅ Z_{3} .

A generator for

G (GF (729) / GF (9))

σ,

where

σ_{3^{6}} (α) = α^{3^{6}} = α^{729}

for

α \in GF (729) .

23.5.4.

Hint.

(a)

S_{5};

(c)

S_{3};

(g) see Example 23.11.

23.5.5.

Hint.

(a)

Q (i)

23.5.7.

Hint.

Let

E

be the splitting field of a cubic polynomial in

F [x] .

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

Z_{3}

S_{3} .

23.5.9.

Hint.

G

is a subgroup of

S_{n} .

23.5.16.

Hint.

True.

23.5.20.

Hint.

Clearly $ω, ω^{2}, \dots, ω^{p - 1}$ are distinct since $ω \neq 1$ or 0. To show that $ω^{i}$ is a zero of $Φ_{p},$ calculate $Φ_{p} (ω^{i}) .$
The conjugates of $ω$ are $ω, ω^{2}, \dots, ω^{p - 1} .$ Define a map $ϕ_{i} : Q (ω) \to Q (ω^{i})$ by

$ϕ_{i} (a_{0} + a_{1} ω + \dots + a_{p - 2} ω^{p - 2}) = a_{0} + a_{1} ω^{i} + \dots + c_{p - 2} (ω^{i})^{p - 2},$

where $a_{i} \in Q .$ Prove that $ϕ_{i}$ is an isomorphism of fields. Show that $ϕ_{2}$ generates $G (Q (ω) / Q) .$
Show that ${ω, ω^{2}, \dots, ω^{p - 1}}$ is a basis for $Q (ω)$ over $Q,$ and consider which linear combinations of $ω, ω^{2}, \dots, ω^{p - 1}$ are left fixed by all elements of $G (Q (ω) / Q) .$

Prev Top Next

Appendix B Hints and Answers to Selected Exercises

1 Preliminaries1.4 Exercises

1.4.1.

1.4.2.

1.4.6.

1.4.10.

1.4.14.

1.4.17.

1.4.18.

1.4.20.

1.4.22.

1.4.23.

1.4.24.

1.4.25.

1.4.28.

2 The Integers2.4 Exercises

2.4.1.

2.4.3.

2.4.8.

2.4.11.

2.4.17. Fibonacci Numbers.

2.4.19.

2.4.23.

2.4.27.

2.4.29.

3 Groups3.5 Exercises

3.5.1.

3.5.2.

3.5.6.

3.5.8.

3.5.15.

3.5.16.

3.5.17.

3.5.18.

3.5.25.

3.5.31.

3.5.35.

3.5.41.

3.5.46.

3.5.49.

4 Cyclic Groups4.5 Exercises

4.5.1.

4.5.2.

4.5.3.

4.5.4.

4.5.10.

4.5.11.

4.5.15.

4.5.16.

4.5.17.

4.5.18.

4.5.22.

4.5.27.

4.5.31.

4.5.37.

5 Permutation Groups5.4 Exercises

5.4.1.

5.4.2.

5.4.3.

5.4.4.

5.4.5.

5.4.8.

5.4.11.

5.4.17.

5.4.25.

5.4.29.

5.4.30.

6 Cosets and Lagrange’s Theorem6.5 Exercises

6.5.1.

6.5.2.

6.5.3.

6.5.4.

6.5.5.

6.5.7.

6.5.12.

6.5.19.

6.5.22.

7 Introduction to Cryptography7.4 Exercises

7.4.1.

7.4.3.

1 Preliminaries
1.4 Exercises

2 The Integers
2.4 Exercises

3 Groups
3.5 Exercises

4 Cyclic Groups
4.5 Exercises

5 Permutation Groups
5.4 Exercises

6 Cosets and Lagrange’s Theorem
6.5 Exercises

7 Introduction to Cryptography
7.4 Exercises

8 Algebraic Coding Theory
8.6 Exercises

9 Isomorphisms
9.4 Exercises

10 Normal Subgroups and Factor Groups
10.4 Exercises

11 Homomorphisms
11.4 Exercises

12 Matrix Groups and Symmetry
12.4 Exercises

13 The Structure of Groups
13.4 Exercises

14 Group Actions
14.5 Exercises

15 The Sylow Theorems
15.4 Exercises