Title [Solution] Contemporary Abstract Algebra (J.gallian) (1) 217.4 KB 32
##### Document Text Contents
Page 1

Contemporary Abstract Algebra (6th ed.) by Joseph Gallian

0.4 Find integers s and t such that 1 = 7 · s+ 11 · t. Show that s and t are not unique.

We can choose s and t to be −3 and 2, respectively. By the Euclidean algorithm:

11 = 7 · 1 + 4
7 = 4 · 1 + 3
4 = 3 · 1 + 1
3 = 1 · 3

Since 1 is the last nonzero remainder, gcd(11, 7) = 1. Thus, we can show that
s = −3 and t = 2 are two integers that we can find. Hence,

1 = 4 + 3(−1) = 4 + [7 + 4(−1)](−1)
= 7(−1) + 4(2) = 7(−1) + [11 + 7(−1)](2)
= 11(2) + 7(−1) + 7(−2)
= 11(2) + 7(−3)

s and t cannot be unique because of the fact that s = −3 + 11k and t = 2− 7k,
for some k ∈ Z, will also satisfy our requirements.

0.10 Let d =gcd(a, b). If a = da′ and b = db′, show that gcd(a′, b′) = 1.

By theorem 0.2, gcd(a, b) = as + bt where s and t are integers, but gcd(a, b) = d
as well, thus d = as+ bt. Since a = da′ and b = db′, d = (da′)s+ (db′)t which we
can divide by d and end up with 1 = a′s + b′t. Since we know that gcd(a, b) = d
and d 6= 0, it follows that 1 = a′s+ b′t = gcd(a′, b′).

0.11 Let n be a fixed positive integer greater than 1. If a mod n = a′ and b mod n = b′,
prove that (a+ b) mod n = (a′ + b′) mod n and (ab) mod n = (a′b′) mod n.

If a mod n = a′ and b mod n = b′, then by definition, a = a′+rn and b = b′+sn
for some r, s ∈ Z. Now,

a+ b = a′ + rn+ b′ + sn = (a′ + b′) + n(r + s)

Since n divides n(r+ s) evenly, we have (a+ b) mod n = (a′ + b′) mod n. Also,

ab = (a′ + rn)(b′ + sn) = a′b′ + sna′ + rnb′ + rsn2 =

a′b′ + n(sa′ + rb′ + rsn)

Since n divides n(sa′ + rb′ + rsn) evenly, we have (ab) mod n = (a′b′) mod n.

0.13 Let n and a be positive integers and let d =gcd(a, n). Show that the equation ax mod
n = 1 has a solution if and only if d = 1.

1

Page 2

Firstly suppose that ax mod n = 1 has a solution. Then kn + 1 = ax by
definition. Also, ax − kn = 1, which also happens to be the form of gcd(a, n)
by theorem 0.2. Thus gcd(a, n) = d and gcd(a, n) = 1, then d = 1 as required.
Conversely, if d = gcd(a, n) = 1, then by Theorem 0.2, there exists x, t such that
1 = ax + nt. Now, [1]n = [ax]n + [nt]n and since n divides nt evenly, it is clear
that ax mod n = 1 and a solution exists.

0.14 Show that 5n+ 3 and 7n+ 4 are relatively prime for all n.

We can show using the Euclidean algorithm:

7n+ 4 = (5n+ 3) · 1 + (2n+ 1)
5n+ 3 = (2n+ 1) · 2 + (n+ 1)
2n+ 1 = (n+ 1) · 1 + n
n+ 1 = n · 1 + 1

n = 1 · n

Since 1 is the last nonzero remainder, gcd(7n+ 4, 5n+ 3) = 1, which shows that
they are relatively prime.

0.16 Use the Euclidean algorithm to find gcd(34, 126) and write it as a linear combination
of 34 and 126.

Use Euclidean algorithm to find gcd(34, 126):

126 = 34 · 3 + 24
34 = 24 · 1 + 10
24 = 10 · 2 + 4
10 = 4 · 2 + 2
4 = 2 · 2

Since 2 is the last nonzero remainder, gcd(34, 126) = 2.
Now to express it as a linear combination:

2 = 10 + 4(−2) = 10 + [24 + 10(−2)](−2) = 24(−2) + 10(5)
= 24(−2) + [34 + 24(−1)](5) = 24(−7) + 34(5)
= [126 + 34(−3)](−7) + 34(5) = 126(−7) + 34(26)

Hence, we can express 2 as 126(−7) + 34(26).

0.26 What is the largest bet that cannot be made with chips worth 7 dollars and 9 dollars?

2

Page 16

Theorem 3.4 tells us that if G = {e, a, b} is a group with all elements distinct,
then 〈a〉 ⊆ G. Moreover, theorem 4.1 shows that |a| = |〈a〉|. If we let e be the
identity of G, it suffices to show that |a| = |〈a〉| = |G| to show that 〈a〉 = G.
So, suppose that 〈a〉 6= G, then |a| < 3. Also since a 6= e, then |a| 6= 1 6= |〈a〉|,
so |a| = 2 = |〈a〉|. Because G is a group we have that ab ∈ G and with a 6= e
then ab 6= b and with b 6= e then ab 6= a either. Thus ab = e, hence a(ab) = ae
which implies that a2b = a, yet a2 = e so b = a. Contradiction since a and b were
distinct. Thus |〈a〉| = 3 ⇒ 〈a〉 = G.

4.28 Let a be a group element that has infinite order. Prove that 〈ai〉 = 〈aj〉 if and only if
i = ±j.

Suppose that i = ±j. Well, then we can break it down to two cases. When i = j
and when i = −j. Firstly, when i = j, then it is quite obvious that ai = aj,
which means by definition that 〈ai〉 = 〈aj〉. Now, when i = −j, we know that
i = −i, which we know by definition that a−i = (a−1)|i|, which then shows us that
(a−1)|i| ∈ 〈ai〉. There is no need to show that ai ∈ 〈ai〉 for all nonnegative integers
i, thus 〈ai〉 = 〈a−j〉.

4.33 Determine the subgroup lattice for Zp2q, where p and q are distinct primes.

〈1〉

xx
xx

xx
xx

x

FF
FF

FF
FF

F

〈p〉

RRR
RRR

RRR
RRR

RRR
RRR

〈q〉

〈p2〉

EE
EE

EE
EE

〈pq〉

yy
yy

yy
yy

〈p2q〉

4.36 Prove that a finite group is the union of proper subgroups if and only if the group is
not cyclic.

Suppose that a finite group, G, is the union of proper subgroups,
that is G = G1∪G2∪· · ·∪Gk. Now let’s assume for the sake of contradiction that
G is cyclic. This means that there is some a ∈ G such that 〈a〉 = G. But then
since G is comprised of a finite number of Gi, then a ∈ Gi. Clearly, whatever Gi
that contains a, must also contain G, which contradicts Gi being a proper subset.
Conversely, suppose that a finite group G is not cyclic. This means that there
is no a ∈ G such that 〈a〉 = G, thus for every a ∈ G, 〈a〉 < G, by theorem 3.4.
Then it must follow that G =

a∈G〈a〉 and we’re done.

16

Page 17

4.42 Prove that an infinite group must have an infinite number of subgroups.

Suppose that G is an infinite group. For the sake of contradiction, let’s assume
that G has a finite number of subgroups. Let C be a finite subset of G such
that for every a, b ∈ C, then 〈a〉 ∩ 〈b〉 = ∅ and

a∈C〈a〉 = G. Clearly, there

has to be one infinite 〈a〉 otherwise our finite union of subgroups would fall short
of being equal to G. Now, since 〈a〉 is infinite, then we know by theorem 4.1
that all distinct powers of a are distinct group elements. Furthermore, 〈ai〉 is a
subgroup of 〈a〉 for all ai ∈ 〈a〉. Thus a contradiction that G has a finite amount
of subgroups.

4.60 Suppose that |x| = n. Find a necessary and sufficient condition on r and s such that
〈xr〉 ⊆ 〈xs〉.

Just by inspecting some of the examples on page 79 and 80, we can build a
conjecture that our necessary and sufficient condition is going to be 〈xr〉 ⊆ 〈xs〉 if
and only if s|r, where s and r have to be divisors of n. Now, let us see if this holds
true. Suppose that s|r, then for some nonzero integer k and since r|n, xn = xkr by
theorem 0.2, but this is the identity and clearly the identity is in 〈xs〉. So, if we let
0 < k < n/r, then xkr = (xk)r = (xst)r = (xs)tr ∈ 〈xs〉, for some nonzero integer
t and by theorem 0.2 again. Thus, we can conclude that 〈xr〉 ⊆ 〈xs〉. Conversely,
suppose that 〈xr〉 ⊆ 〈xs〉, then working backwards from the proof of Theorem 4.2
on page 76, we know that ar = (as)t for some integer t. By what was said on page
75 about Theorem 4.1 in the finite case, this is essentially, addition modulo n, so
r = st, which by theorem 0.2 is a linear combination of r with remainder 0, thus
s must divide r.

4.64 Suppose that G is a finite group with the property that every nonidentity element
has prime order (for example, D3 and D5). If Z(G) is not trivial, prove that every
nonidentity element of G has the same order.

Since Z(G) is not trivial, then that means there exists an element, a ∈ Z(G), a 6=
e. Since, a ∈ Z(G), then we know that for all b ∈ G, ab = ba and (ab)n = anbn.
Now, let’s assume for the sake of contradiction that m = |a| 6= |b| = n, yet both
orders are prime. Then it must be that the lcm(m,n) = mn and (ab)mn = e. So
let k = |ab| and by theorem 4.1, corollary 2, k must divide mn. In order for k to
divide mn because m and n are distinct primes, k must be n or m or mn. But
then,

(ab)m = ambm = ebm = bm 6= e

(ab)n = anbn = ane = an 6= e

which means that k must be mn, since neither m|n nor n|m. Clearly mn is not
prime since m|mn and n|mn which means that ab 6∈ G, which is a contradiction.
Therefore, |a| = |b|.

17

Page 31

If we take a look at exercise 2.34, we see that c = 0 in this case, so that the
defined multiplication is really just standard matrix multiplication. With this in
mind, we show that H is Abelian, by taking any a′, a, b, b′ ∈ Z3 and concluding
that 

 1 a b0 1 0
0 0 1

 1 a′ b′0 1 0

0 0 1

 =

 1 (a′ + a) (b′ + b)0 1 0

0 0 1

 =

 1 (a+ a′) (b+ b′)0 1 0

0 0 1

 =

 1 a′ b′0 1 0

0 0 1

 1 a b0 1 0

0 0 1

since Z3 is Abelian. Furthermore, because we have 3 possiblities for a and 3
possibilities for b, which is 3 · 3 = 9 possibilities in total. Hence, |H| = 9.
Now, let us note that Z9 6∼= Z3 ⊕ Z3 since Z3 ⊕ Z3 does not contain an element
of order 9. So, for this same reason, H 6∼= Z9. Thus H must be isomorphic
to Z3 ⊕ Z3. We can further prove this by letting φ : H → Z3 ⊕ Z3 such that

φ

 1 a b0 1 0

0 0 1

 = (a, b). It is not hard to see that φ is bijective, so all that is

left is operation preservation, which easily follows from the argument above where
we showed that H is Abelian.

8.38 Determine Aut(Z2 ⊕ Z2).

Z2⊕Z2 = {(0, 0), (1, 0), (0, 1), (1, 1)}. To determine Aut(Z2⊕Z2), we notice that
there are 3 nonidentity elements of order 2 and any isomorphism must map the
identity to the identity, so with that in mind we can already determine

|Aut(Z2 ⊕ Z2)| =
(

4
3

)
= 4. Since this is not a very large number, we can just

show the mappings (elements) of Aut(Z2 ⊕ Z2):

(0, 0) // (0, 0) (0, 0) // (0, 0) (0, 0) // (0, 0) (0, 0) // (0, 0)

(1, 0) // (1, 0) (1, 0)

##G
GG

GG
GG

GG
(1, 0) (1, 0)

��4
44

44
44

44
44

44
44

4
(1, 0) (1, 0) // (1, 0)

(0, 1) // (0, 1) (0, 1)

;;wwwwwwwww
(0, 1) (0, 1) // (0, 1) (0, 1)

##G
GG

GG
GG

GG
(0, 1)

(1, 1) // (1, 1) (1, 1) // (1, 1) (1, 1)

DD

(1, 1) (1, 1)

;;wwwwwwwww
(1, 1)

extra Because rotations commute we know that given any 2 rotations, R1 and R2,
then R1R2R

−1
1 = R2. Also with any reflection, F , and rotation, R, then FRF =

31

Page 32

FRF−1 = R−1, so that we find [R] = {R,R−1}. Notice that if n is even, Rπ ∈ Dn,
so [Rπ] = {Rπ, R−1π } = {Rπ}. Now for the reflections. We need only consider f
and rf . If we take any rotation, rp for 0 ≤ p ≤ n− 1, we find that

rpfr−p = rprpf = r2pf

and
rp(rf)r−p = rp+1fr−p = rp+1rpf = r2p+1f

Also given any reflection, rmf for 0 ≤ l ≤ n− 1, we find that

rmff(rmf)−1 = rmfff−1r−m = rmfr−m = r2mf

and
rmf(rf)(rmf)−1 = rmfrff−1r−m = rmfr1−m = r2m−1f

Thus, [f ] = {rxf | x is even } and [rf ] = {ryf | y is odd }.
So, if n is even, we find that [f ] = {rxf | x ∈ {0, 2, 4, . . . , n − 2}} and [rf ] =
{ryf | y ∈ {1, 3, 5, . . . , n−1}}. If n is odd, then [f ] = {rxf | x ∈ {0, 1, . . . , n−1}}.
With any reflection F ∈ [f ] for odd n or F ∈ [f ] ∪ [rf ] and knowing that
F ∈ [f ] ⇒ [F ] = [f ] and [f ] ∈ [f ] ∪ [rf ] ⇒ [F ] = [f ] or [F ] = [rf ], then we have
described the conjugacy classes of Dn.

32