Complete Solutions Manual to Accompany Contemporary Abstract Algebra NINTH EDITION Joseph Gallian University of Minnesota Duluth 
CHAPTER 0
Preliminaries
1. {1, 2, 3, 4}; {1, 3, 5, 7}; {1, 5, 7, 11}; {1, 3, 7, 9, 11, 13, 17, 19};
{1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 21, 22, 23, 24}
2. a. 2; 10 b. 4; 40 c. 4: 120; d. 1; 1050 e. pq2
; p
2
q
3
3. 12, 2, 2, 10, 1, 0, 4, 5.
4. s = −3, t = 2; s = 8, t = −5
5. By using 0 as an exponent if necessary, we may write a = p
m1
1
· · · p
mk
k
and
b = p
n1
1
· · · p
nk
k
, where the p’s are distinct primes and the m’s and n’s are
nonnegative. Then lcm(a, b) = p
s1
1
· · · p
sk
k
, where si = max(mi
, ni) and
gcd(a, b) = p
t1
1
· · · p
tk
k
, where ti = min(mi
, ni) Then
lcm(a, b) · gcd(a, b) = p
m1+n1
1
· · · p
mk+nk
k = ab.
6. The first part follows from the Fundamental Theorem of Arithmetic; for
the second part, take a = 4, b = 6, c = 12.
7. Write a = nq1 + r1 and b = nq2 + r2, where 0 ≤ r1, r2 < n. We may
assume that r1 ≥ r2. Then a − b = n(q1 − q2) + (r1 − r2), where
r1 − r2 ≥ 0. If a mod n = b mod n, then r1 = r2 and n divides a − b. If n
divides a − b, then by the uniqueness of the remainder, we then have
r1 − r2 = 0. Thus, r1 = r2 and therefore a mod n = b mod n.
8. Write as + bt = d. Then a
0
s + b
0
t = (a/d)s + (b/d)t = 1.
9. By Exercise 7, to prove that (a + b) mod n = (a
0 + b
0
) mod n and
(ab) mod n = (a
0
b
0
) mod n it suffices to show that n divides
(a + b) − (a
0 + b
0
) and ab − a
0
b
0
. Since n divides both a − a
0 and n divides
b − b
0
, it divides their difference. Because a = a
0 mod n and b = b
0 mod n
there are integers s and t such that a = a
0 + ns and b = b
0 + nt. Thus
ab = (a
0 + ns)(b
0 + nt) = a
0
b
0 + nsb0 + a
0nt + nsnt. Thus, ab − a
0
b
0
is
divisible by n.
10. Write d = au + bv. Since t divides both a and b, it divides d. Write
s = mq + r where 0 ≤ r < m. Then r = s − mq is a common multiple of
both a and b so r = 0.
11. Suppose that there is an integer n such that ab mod n = 1. Then there is
an integer q such that ab − nq = 1. Since d divides both a and n, d also
divides 1. So, d = 1. On the other hand, if d = 1, then by the corollary of
Theorem 0.2, there are integers s and t such that as + nt = 1. Thus,
modulo n, as = 1.
0/Preliminaries 2
12. 7(5n + 3) − 5(7n + 4) = 1
13. By the GCD Theorem there are integers s and t such that ms + nt = 1.
Then m(sr) + n(tr) = r.
14. It suffices to show that (p
2 + q
2 + r
2
) mod 3 = 0. Notice that for any
integer a not divisible by 3, a mod 3 is 1 or 2 and therefore a
2 mod 3 = 1.
So, (p
2 + q
2 + r
2
) mod 3 = p
2 mod 3 + q
2 mod 3 + r
2 mod 3 = 3 mod 3=
0.