CM121A, Abstract Algebra Solution Sheet 1
1. Consider the following subsets of Z:
A = { multiples of 3 }, B = { a ∈ Z | −6 < a ≤ 6 }, C = { −3, 2, 4, 9, 31 }.
(a) Find B ∪ (A ∩ C).
Solution: A ∩ C = {−3, 9}, so
B ∪ (A ∩ C) = {5, −4, −3, −2, −1, 0, 1, 2, 3, 4, 5, 6, 9 }.
(b) Find (B ∪ A) ∩ C.
Solution: The only element of C which is not in B ∪ A is 31, so
(B ∪ A) ∩ C = {−3, 2, 4, 9}.
(c) Find (B \ A) ∩ C (where X \ Y denotes the set of elements of X
which are not in Y ).
Solution: B \ A = {−5, −4, −2, −1, 1, 2, 4, 5}, so (B \ A) ∩ C =
{2, 4}.
2. Let A, B and C be subsets of a set X. Prove that
(A ∪ B) ∩ C = (A ∩ C) ∪ (B ∩ C).
Solution: Suppose that x ∈ (A ∪ B) ∩ C. Then x ∈ A ∪ B, and
x ∈ C. Since x ∈ A ∪ B, we have that x ∈ A or x ∈ B. Suppose
first that x ∈ A. Since also x ∈ C, it follows that x ∈ A ∩ C, and
therefore x ∈ (A ∩ C) ∪ (B ∩ C). Simlarly, if x ∈ B, then x ∈ B ∩ C,
so x ∈ (A ∩ C) ∪ (B ∩ C). We have now shown that
(A ∪ B) ∩ C ⊆ (A ∩ C) ∪ (B ∩ C).
Now suppose that x ∈ (A∩C)∪(B ∩C). Then x ∈ A∩C, or x ∈ B ∩C.
Suppose first that x ∈ A ∩ C. Then x ∈ A ⊆ A ∪ B and x ∈ C, so
x ∈ (A ∪ B) ∩ C. Similarly if x ∈ B ∩ C, then x ∈ B ⊆ A ∪ B and
x ∈ C, so x ∈ (A ∪ B) ∩ C. We have now shown that
(A ∪ B) ∩ C ⊇ (A ∩ C) ∪ (B ∩ C).
Combining the two inclusions shows the two sets are equal.
3. Decide which of the following assertions are true for all x, y, z ∈ R. If
false, give a counterexample.
(a) If x2 ≤ y 2 , then x ≤ y.
Solution: False, take x = 0, y = −1.
(b) 0 ≤ x ≤ y ⇒ x2 ≤ y 2 .
Solution: True.
1
(c) x − z ≥ y − z if and only if x ≥ y.
Solution: True.
(d) x ≥ 2 ⇔ x2 ≥ 2x.
Solution: False, take x = −1.
4. Prove by induction that the sum of the first n odd positive squares is
1 3
3 (4n − n), i.e., that
1
1 + 9 + 25 + · · · + (2n − 1)2 = (4n3 − n).
3
Solution: Let P (n) be the equation we need to prove. Then P (1) is
obviously true since 1 = 13 (4 · 13 − 1). Suppose now that n ≥ 1 and
P (n) is true, and we will show that P (n + 1) is true. Adding (2n + 1)2
(the next odd square) to both sides of P (n) gives
1
1 + 9 + 25 + · · · + (2n + 1)2 = 3
3 (4n − n) + (2n + 1)
2
4 3 1 2
= 3 n − 3 n + 4n + 4n + 1
4 3 2 11
= 3 n + 4n + 3 n + 1.
We need to show that this agrees with the right-hand-side of P (n + 1),
which is
1 1
3 (4(n + 1)3 − (n + 1)) = 3 2
3 (4(n + 3n + 3n + 1) − (n + 1))
4 3 2 11
= 3 n + 4n + 3 n + 1.
Since P (1) is true, and P (n) ⇒ P (n + 1) for all n ≥ 1, it follows that
P (n) is true for all n ∈ N.
5. Suppose that a, b, c, d ∈ Z and n ∈ N. Prove the following:
(a) If a|b and b|c, then a|c.
Solution: If a|b then b = sa for some s ∈ Z (by definition of
divisibility), and if b|c then c = tb for some t ∈ Z (again by
definition). Therefore c = tb = t(sa) = (ts)a, and since ts ∈ Z,
we conclude that c is divisible by a.
(b) If a|n, then a ≤ n.
Solution: First note that if a ≤ 0, then a ≤ n (since we assumed
n > 0). So we may assume that a > 0. If a|n, then n = sa for
some s ∈ Z. Since a and n are positive, so is s. Therefore s ≥ 1.
Since a is positive, it follows that as ≥ a · 1, so n ≥ a.
(c) If n|a and n|b, then n|(ac + bd).
Solution: If n|a and n|b, then a = sn and b = tn for some
s, t ∈ Z. Therefore ac + bd = (sn)c + (tn)b = (sc + tb)n, so ac + bd
is divisible by n.
2
6. Use the Euclidean algorithm to find gcd(1066, 2009) and express it in
the form 1066m + 2009n with m, n ∈ Z.
Solution: The Euclidean algorithm gives:
2009 = 1 · 1066 + 943,
1066 = 1 · 943 + 123,
943 = 7 · 123 + 82,
123 = 1 · 82 + 41,
82 = 2 · 41.
Therefore gcd(1066, 2009) = 41.
Writing 41 in terms of the preceding two remainders and iteratively
substituting gives:
41 = 123 − 82 = 123 − (943 − 7 · 123) = 8 · 123 − 943
= 8(1066 − 943) − 943 = 8 · 1066 − 9 · 943
= 8 · 1066 − 9(2009 − 1066) = 17 · 1066 − 9 · 2009,
so let m = 17 and n = −9.
7. Suppose that a1 , a2 , . . . , ak are integers, not all of which are 0.
(a) Write down the definition of gcd(a1 , a2 , . . . , ak ).
Solution: g = gcd(a1 , a2 , . . . , ak ) (the greatest common divisor
of a1 , a2 , . . . , ak ) if:
1) g ∈ Z and g|ai for i = 1, . . . , k, and
2) d ∈ Z and d|ai for i = 1, . . . , k ⇒ d ≤ g.
Remark: Variants on this with the same meaning are fine, for
example:
gcd(a1 , a2 , . . . , ak ) is the greatest integer g such that g|a1 , g|a2 ,
. . . , g|ak .
(b) Prove that gcd(a1 , a2 , . . . , ak ) is the least positive integer of the
form n1 a1 + n2 a2 + · · · + nk ak with n1 , n2 , . . . , nk ∈ Z.
Solution: Let
S = { n1 a1 + n2 a2 + · · · + nk ak | n1 , n2 . . . , nk ∈ Z }.
Then S contains a positive integer, for example choose i so that
ai �= 0 and then |ai | is a positive element of S. Let m be the least
positive element of S.
We show that m|ai for each i = 1, . . . , k. By the Division Algo-
rithm, ai = mq + r for some q, r ∈ Z, and 0 ≤ r < m. We will
prove by contradiction that r = 0. Suppose that r > 0. Since
m = n1 a1 + n2 a2 + · · · + nk ak for some n1 , n2 , . . . , nk ∈ Z, we
3
have
r = ai − qm
= ai − q(n1 a1 + n2 a2 + · · · + nk ak )
= (−qn1 )a1 + (−qn2 )a2 + · · · + (1 − qni )ai + · · · + (−qnk )ak .
Therefore r ∈ S. Recall that 0 ≤ r < m. If r > 0, then since
r < m, we get a contradiction to m being the least element of S.
We therefore conclude that r = 0 and ai = mq is divisible by m.
We have now shown that m is a common divisor of a1 , a2 , · · · , ak .
Now suppose that d is any common divisor of a1 , a2 , · · · , ak . Then
for each i = 1, 2, . . . , k, we have ai = dci for some ci ∈ Z. There-
fore
m = n1 a1 + n2 a2 + · · · + nk ak = d(n1 c1 + n2 c2 + · · · + nk ck )
is divisible by d. Since d|m and m > 0, it follows that d ≤ m.
We have now shown that m = gcd(a1 , a2 , . . . , ak ).
