MA10209 Algebra 1A

Sheet 5 Problems and Solutions: GCS

26-xi-12

The course website is http://people.bath.ac.uk/masgcs/diary.html

Hand in work to your tutor by 15:15, Monday Nov 5.

1. (a) Find g = gcd(75, 27) by means of a hand calculation.
Solution 75 = 2 27 + 21; 27 = 1 21 + 6; 21 = 3 6 + 3; 6 = 2 3 + 0. Therefore gcd(75, 27) = 3.
(b) Find integers 0 and 0 such that 750 + 270 = g.
Solution 3 = 12136 = 1213(2721) = 421327 = 4(75227)327 = 4751127.
(Notice that it is easy to verify that this statement is correct). Therefore we may choose 0 = 4 and
0 = 11.
(c) Find all pairs of integers , such that 75 + 27 = g.
Solution Integers , satisfy 75 + 27 = g if, and only if, 75(0 ) + 27( 0 ) = 0 and this happens
if, and only if, 25(0 ) + 9(0 ) = 0. 25 and 9 are coprime, so 0 = 9k for some k Z,
and then it follows that 0 = 25k. Conversely, provided the integer k satisfies these conditions,
then 75(0 ) + 27( 0 ) = 0. Therefore the legitimate values of (, ) are the elements of the set
{(4 9k, 11 + 25k) | k Z}.
2. (a) Find g = gcd(8633, 13439) by means of a hand calculation.
Solution 13439 = 18633+4806; 8633 = 14806+3827; 4806 = 13827+979; 3827 = 3979+890; 979 =
1 890 + 89; 890 = 10 89 + 0. Therefore gcd(8633, 13439) = 89.
(b) Find integers 0 and 0 such that 86330 + 134390 = g.
Solution 89 = 979890 = 979(38273979) = 49793827 = 4(48063827)3827 = 448065
3827 = 448065(86334806) = 9480658633 = 9(134398633)58633 = 913439148633.
This may be directly verified. Thus we may choose 0 = 14 and 0 = 9.
(c) Find all pairs of integers , such that 8633 + 13439 = g.
Solution Integers , satisfy 8633 + 13439 = 89 if, and only if, 8633(0 ) + 13439( 0 ) = 0 and
this happens if, and only if, 97(0 ) + 151(0 ) = 0 (dividing through by 89) Now 97 and 151 are
coprime, so 0 = 151k for some k Z, and then it follows that 0 = 97k. Conversely, provided
the integer k satisfies these conditions, then 97(0 ) + 151( 0 ) = 0. Therefore the legitimate values
of (, ) are the elements of the set {(14 151k, 9 + 97k) | k Z}.
(d) Show that there are positive integers a, b in the range 1 a, b 15 such that a/b and 8633/13439 differ by
less than 1/2000.
Solution 9 13439 14 8633 = 89 so 9/14 8633/13439 = 89/(13439 14) = 1/(151 14) = 1/2114 <
1/2000.
3. The integers m and n are not both 0 and g = gcd(m, n). Suppose that integers , are such that m + n = g.
Prove that there are integers u, v such that u + v = 1.
Solution Let u = m/g and v = n/g so u, v Z.
4. (a) Which natural numbers n have an odd number of natural number divisors?
Solution The squares are precisely the numbers with this property. If a positive integer is not a square,
its positive divisors come in pairs d, d0 where dd0 = n so there are an even number of them. In the case that

n = k 2 for k N, then the pair k, k counts the divisor k twice when it should only be counted once, so n
has an odd number of divisors. There is Q
an alternative solution where you use the Fundamental
Theorem
Q
of Arithmetic to express n as a product i pai i of distinct prime numbers. Then n has i (ai + 1) positive
divisors, and this number is odd if, and only if, each ai is even, and by the FTA, this happens if, and only
if, n is a perfect square.
(b) Which natural numbers m have a prime number of natural number divisors? Q
Q
Solution 1 has 1 divisor. Suppose that n > 1 has prime factorization n = i pai i , then n has i (ai +
1) positive integer divisors. This expression is prime if, and only if, there is only one prime p1 in the
factorization, and ai = q 1 where q is prime. Thus the required numbers are those of the form q p1 as p, q
range over the prime numbers.
(c) Suppose that k > 1 is a natural number. Prove that there are infinitely many natural numbers n which
each have exactly k natural number divisors.
Solution Suppose that p is a prime number, then pk1 has exactly k positive divisors. This yields infinitely
many examples since p can be any prime number.
5. Suppose that n is a natural number. Let n denote the equivalence relation on Z defined by a n b if, and only
if, n | (a b). The equivalence classes of this relation form a finite set Z/ n . This notation is ponderous, so we
introduce compact notation Zn for Z/ n . Write out the addition and multiplication tables for
(a) Z4 ;
Solution
+
[0]
[1]
[2]
[3]

[0]
[0]
[1]
[2]
[3]

[1]
[1]
[2]
[3]
[0]

[2]
[2]
[3]
[0]
[1]

[3]
[3]
[0]
[1]
[2]

+
[0]
[1]
[2]
[3]
[4]

[0]
[0]
[1]
[2]
[3]
[4]

[1]
[1]
[2]
[3]
[4]
[0]

[2]
[2]
[3]
[4]
[0]
[1]

[3]
[3]
[4]
[0]
[1]
[2]

[4]
[4]
[0]
[1]
[2]
[3]

[0]
[0]
[1]
[2]
[3]
[4]
[5]

[1]
[1]
[2]
[3]
[4]
[5]
[0]

[2]
[2]
[3]
[4]
[5]
[0]
[1]

[3]
[3]
[4]
[5]
[0]
[1]
[2]

[4]
[4]
[5]
[0]
[1]
[2]
[3]

[5]
[5]
[0]
[1]
[2]
[3]
[4]

and

[0]
[1]
[2]
[3]

[0]
[0]
[0]
[0]
[0]

[1]
[0]
[1]
[2]
[3]

[2]
[0]
[2]
[0]
[2]

[3]
[0]
[3]
[2]
[1]

and

[0]
[1]
[2]
[3]
[4]

[0]
[0]
[0]
[0]
[0]
[0]

[1]
[0]
[1]
[2]
[3]
[4]

[2]
[0]
[2]
[4]
[1]
[3]

[3]
[0]
[3]
[1]
[4]
[2]

[4]
[0]
[4]
[3]
[2]
[1]

and

[0]
[1]
[2]
[3]
[4]
[5]

[0]
[0]
[0]
[0]
[0]
[0]
[0]

[1]
[0]
[1]
[2]
[3]
[4]
[5]

[2]
[0]
[2]
[4]
[0]
[2]
[4]

[3]
[0]
[3]
[0]
[3]
[0]
[3]

[4]
[0]
[4]
[2]
[0]
[4]
[2]

(b) Z5 ;
Solution

(c) Z6 ;
Solution
+
[0]
[1]
[2]
[3]
[4]
[5]

[5]
[0]
[5]
[4]
[3]
[2]
[1]

(d) Z7 .
Solution
+
[0]
[1]
[2]
[3]
[4]
[5]
[6]

[0]
[0]
[1]
[2]
[3]
[4]
[5]
[6]

[1]
[1]
[2]
[3]
[4]
[5]
[6]
[0]

[2]
[2]
[3]
[4]
[5]
[6]
[0]
[1]

[3]
[3]
[4]
[5]
[6]
[0]
[1]
[2]

[4]
[4]
[5]
[6]
[0]
[1]
[2]
[3]

[5]
[5]
[6]
[0]
[1]
[2]
[3]
[4]

[6]
[6]
[0]
[1]
[2]
[3]
[4]
[5]

and

[0]
[1]
[2]
[3]
[4]
[5]
[6]

[0]
[0]
[0]
[0]
[0]
[0]
[0]
[0]

[1]
[0]
[1]
[2]
[3]
[4]
[5]
[6]

[2]
[0]
[2]
[4]
[6]
[1]
[3]
[5]

[3]
[0]
[3]
[6]
[2]
[5]
[1]
[4]

[4]
[0]
[4]
[1]
[5]
[2]
[6]
[3]

[5]
[0]
[5]
[3]
[1]
[6]
[4]
[2]

[6]
[0]
[6]
[5]
[4]
[3]
[2]
[1]

100

6. (a) What is the remainder when 22 is divided by 7?

Solution In Z7 we have [26 ] = [1]. Now 2100 = 6k + r where k, r are integers and 0 r 5. In Z6 we have
[2]2m = [4] for all positive integers m by induction, so [2100 ] = [4] and so 2100 = 6k + 4 for some positive
100
100
integer k. Now return to working in Z7 . We have [22 ] = [26k+4 ] = [26 ]k [2]4 = [1]k [2] = [2]. Therefore 22
leaves remainder 2 on division by 7.
(b) Show that no prime number p of the form 4m + 3 is the sum of two squares. There is a theorem of Fermat
which states that all the other prime numbers can be written as the sum of two squares. This is not part of
the course, but if you are interested search on: Proofs of Fermats theorem on sums of two squares.
Solution In Z4 , the squares are [0] and [1]. The sum of two equivalence classes, each one of these two,
cannot be [3]. Therefore integers of the form 4m + 3 cannot be the sum of two squares.
(c) Prove that there are infinitely many natural numbers which are not the sum of three squares. Lagrange
proved that every positive integer is the sum of four squares.
Solution In Z8 , the squares are [0], [1] and [4]. The sum of three equivalence classes, each one these three,
cannot be [7]. Therefore numbers of the form 8m + 7 cannot be sums of three squares.
7. Let S = Z (Z \ {0}). Define a relation on S via (u1 , v1 ) (u2 , v2 ) if, and only if, u1 v2 = u2 v1 .
(a) Prove that is an equivalence relation.
Solution Suppose that (u, v) S. Then uv = uv so (u, v) (u, v) and we have reflexivity. Next suppose
that (u, v), (w, x) S and (u, v) (w, x). Therefore ux = wv, so wv = ux and thus (w, x) (u, v).
Symmetry is established. Finally suppose that (u, v), (w, x), (y, z) S and that (u, v) (w, x) and (w, x)
(y, z). Therefore ux = wv and wz = yx. Now multiplying we have uxwz = wvyx. If w 6= 0, we divide
by the non-zero integer xw to obtain uz = vy and thus (u, v) (y, z). On the other hand, if w = 0, then
u = y = 0 so (u, v) (y, z). Transitivity is established and we have an equivalence relation.
(b) Pretend the rational numbers do not exist, and create them anew by putting Q = S/ . Introduce the
notation ab for [(a, b)], the equivalence class of (a, b). Suppose that ab11 = ab22 and dc11 = dc22 , prove that
a1 d1 +b1 c1
2 c2
= a2 db22+b
and ab11dc11 = ab22dc22 .
b1 d1
d2
Solution We have a1 b2 = a2 b1 and c1 d2 = c2 d1 . The first (addition) condition will hold provided that we
can show that (a1 d1 + b1 c1 )b2 d2 = (a2 d2 + b2 c2 )b1 d1 i.e. a1 b2 d1 d2 + b1 b2 c1 d2 = a2 b1 d1 d2 + b1 b2 c2 d1 and this
follows from our first two equations. As for the second formula, we need to show that a1 b2 c1 d2 = a2 b1 c2 d1
and again this follows immediately from our first two equations.
(c) Show how to define addition and multiplication on Q.
a c
Solution Define addition + in Q via ab + dc = ad+bc
bd . Define multiplication on Q via b d =

ac
bd .

(d) Why is part (b) vital to ensure that this definition makes sense?
Solution Until we check (b) holds (say for addition), then there is the concern that the definition of addition
given in (c) is nonsense, because each given equivalence class has many names. For example 24 = 36 . Once
you know that (b) holds, it does not matter which name for each equivalence class you use in the recipe for
addition in (c). A similar remark applies to multiplication.
8. (a) Suppose that x Z is a square. Which are the possible equivalence classes [x] in Z7 ?
Solution These are [0]2 = [0], [1]2 = [6]2 = [1], [2]2 = [5]2 = 4, [3]2 = [4]2 = [2].

(b) Suppose that C is a set of six consecutive positive integers. Is it possible that C can be partitioned into two
subsets A and B so that the product of all the elements of A is the same as the product of all the elements
of B? If S = {s} is a singleton subset of Z, we define the product of all the elements of S to be s.
Solution Suppose, for contradiction, that such a partition exists. Clearly 7 cannot divide any of these 6
consecutive integers else the FTA will ensure that the two products are different. Work in Z7 . The product
of the six consecutive integers will be in the equivalence class [6!] = [6], but [6] is not a square in Z7 by part
(a). This is the required contradiction.
9. Let n be a natural number. Prove that there are natural numbers a1 , a2 , . . . , an and natural numbers b1 , . . . , bn
such that the following conditions are satisfied.
(a) If i 6= j, then ai and aj are coprime.
(b) If i 6= j, then bi and bj are coprime.
(c) The numbers ai and bj are not coprime for all i and for all j.
Solution Choose n2 different prime numbers and write them in an n by n square. There is an infinite supply
of prime numbers, thanks to Euclid, so this can be done. Let ai denote the product of the numbers in the i-th
row, and let bj denote the product of the numbers in the j-th column. That does it.
If you would
Qn more formal, for i = 1 . . . n and j = 1 . . . n let pij be a different prime number.
Qn like to be a touch
Let ai = j=1 pij and bj = i=1 pij . Then for each i and for each j, gcd(ai , bj ) = pij 6= 1.
10. (Tutor Pacifier) Let S be a finite set of positive integers which has the following property: if x is an element of S,
then so too are all positive divisors of x. A non-empty subset T of S is good if whenever x, y T and x < y, the
ratio y/x is a power of a prime number. A non-empty subset T of S is bad if whenever x, y T and x < y, the
ratio y/x is not a power of a prime number. A single element set is considered both good and bad (by definition,
or by vacuous reasoning, as you please). Let k be the largest possible size of a good subset of S. Prove that k is
also the smallest number of pairwise-disjoint bad subsets whose union is S.
Solution Not yet, but here is the solution to Problem 10 of Sheet 3. This was to Prove the Schr
oder-Bernstein
Theorem unaided (no books, internet etc). The theorem states that if A, B are sets, and there are injective
maps f : A B and g : B A, then there is a bijective map h : A B. By replacing B with an appropriate
copy of itself if necessary, you can assume that A B = . This trick may well simplify writing up the proof.
Proof We may assume wlog that A B = . Suppose that x A \ Im g, then we say that x is an A-stopper. Any
element of A obtained from an A-stopper by finitely many applications of the map g f is also an A-stopper.
Suppose that y B \ Im f . We say that g(y) is a B-stopper. Any element of A obtained from g(y) by finitely
many applications of the map g f is also called a B-stopper.
If a A, then by looking at successive (unique where defined) preimages of a under g, then f , then g, then f
etc, so see that the A-stoppers and the B-stoppers form disjoint subsets of A. The elements which are neither
A-stoppers nor B-stoppers we call non-stoppers.
If y B, we say that y is an A-stopper, B-stopper or non-stopper as g(y) is an A-stopper, B-stopper or nonstopper. Notice the meaning of this language. Given any element of A or B, you can look for a pre-image of
this element under f or g as appropriate, and if you succeed, iterate (do it again and again). Either you can do
this indefinitely, or you get stuck (you stop) in A or in B.
We now define a map : A B which will be the required bijection. Suppose that a A. If a is a B-stopper,
we define (a) to be the unique element of B such that g((a)) = a. Otherwise a is an A-stopper or a non-stopper.
In that case we define (a) to be f (a).
Notice that maps A-stoppers to A-stoppers, B-stoppers to B-stoppers and non-stoppers to non-stoppers.
Injectivity: suppose that (a1 ) = (a2 ) is an A-stopper or a non-stopper, then f (a1 ) = f (a2 ) so a1 = a2 by
injectivity of f . If (a1 ) = (a2 ) is a B-stopper, then a1 = g((a1 ) = g((a2 )) = a2 . Therefore is injective.
Now suppose that b B is an A-stopper or a non-stopper, so there is a A such that b = f (a) = (a). on the
other hand, suppose that b B is a B-stopper. Therefore (g(b)) = b. Therefore is surjective, and hence a
bijection.