MATH1061 Assignment 4 Due 4pm Friday 28 October 2022
This Assignment is compulsory, and contributes 5% towards your final grade. It should be submitted
by 4pm on Friday 28 October 2022. In the absence of a medical certificate or other valid documented
excuse, assignments submitted after the due date will attract a penalty as outlined in the course
profile. Applications for extensions must be submitted online via my.UQ – applying for
an extension (there is a link in the course profile under Section 5.3 of Assessment).
Prepare your assignment as a pdf file, either by typing it, writing on a tablet or by scanning/
photographing your handwritten work. Ensure that your name, student number and tutorial group
number appear on the first page of your submission. Check that your pdf file is legible and that the
file size is not excessive. Files that are poorly scanned and/or illegible may not be marked. Upload
your submission using the assignment submission link in Blackboard. Please note that our online
systems struggle with filenames that contain foreign characters (e.g. Chinese, Japanese, Arabic) so
please ensure that your filename does not contain such characters.
1. Let n ≥ 2 be an integer, and define
Z∗n = {[x] ∈ Zn : gcd(x, n) = 1}.
If a and b are integers such that a ≡ b (mod n), then gcd(a, n) = gcd(b, n). You do not need to
prove this, but you should note that it implies that the set Z∗n is well defined – the truth of the
statement [x] ∈ Zn is independent of the choice of representative for the equivalence class [x].
If x and n are integers such that gcd(x, n) = 1, then there exist integers a and b such that
ax + bn = 1. You may use this in your answer to this question without proving it – it can be
proved by using the Extended Euclidean Algorithm, which first uses the Euclidean Algorithm to
determine the gcd of x and n, and then “works backwards” to determine the integers a and b.
(a) (5 marks) Prove that (Z∗n, ·) is a group.
(b) (2 marks) Determine whether (Z∗8, ·) ∼= (Z4,+), and justify your answer.
(c) (2 marks) Determine whether (Z∗9, ·) ∼= (Z6,+), and justify your answer.
(d) (2 marks) How many elements are in Z∗35?
(e) (2 marks) Determine whether (Z∗35, ·) ∼= S4, and justify your answer.
2. Let ρ be an equivalence relation on the set {1, 2, . . . , 100} such that ρ has 7 equivalence classes.
(a) (3 marks) Show that there are two equivalence classes S and T of ρ such that |S∪T | ≥ 30.
(b) (2 marks) Show that if x is an integer such that 0 ≤ x ≤ 15, then(
15+x
2
)
+
(
15−x
2
)
= 2
(
15
2
)
+ x2.
(c) (3 marks) Show that if a and b are positive integers such that a+ b ≥ 30, then(
a
2
)
+
(
b
2
) ≥ 210.
(d) (3 marks) Show that there exist two equivalence classes S and T of ρ and four distinct
integers w, x, y, z ∈ S ∪ T such that each of |S ∩ {w, x, y, z}| and |T ∩ {w, x, y, z}| is even
and w + x = y + z.
3. Let F = {0, 1, a, b, c, d, e, f} and let (F,+) be the group with Cayley table as follows.
+ 0 1 a b c d e f
0 0 1 a b c d e f
1 1 0 b a d c f e
a a b 0 1 e f c d
b b a 1 0 f e d c
c c d e f 0 1 a b
d d c f e 1 0 b a
e e f c d a b 0 1
f f e d c b a 1 0
A binary operation · is defined on F such that (F,+, ·) is a field.
(a) (1 mark) You know that 1 is the identity of the group (F \ {0}, ·), c · a = d and c · d = e.
Use this information to determine c · f . Show your working.
(b) (2 marks) You also know that c ·c = a. Use this information together with the information
from (a) to determine c · b and c · e. Show your working.
(c) (1 mark) Use the information from (a) and (b) to determine a · a. Show your working.
(d) (3 marks) Complete the Cayley table for the group (F \{0}, ·) (see below). No explanation
required.
· 1 a b c d e f
1
a
b
c
d
e
f