COMP9020 Assignment 1 2024 Term 1
Due: Thursday, 29th February, 18:00 (AEDT)
Submission is through inspera. Your assignment will be automatically submitted at the above due date. If you manually submit before this time, you can reopen your submission and con- tinue until the deadline.
If you need to make a submission after the deadline, please use this link to request an extension:
Answers are expected to be provided either:
• In the text box provided using plain text, including unicode characters and/or the built-in formula editor (diagrams can be drawn using the built-in drawing tool); or
• as a pdf (e.g. using LATEX) – each question should be submitted on its own pdf, with at most one pdf per question.
Handwritten solutions will be accepted if unavoidable, but that we don’t recommend this ap- proach as the assessments are designed to familiarise students with typesetting mathematics in preparation for the final exam and for future courses.
Discussion of assignment material with others is permitted, but the work submitted must be your own in line with the University’s plagiarism policy.
Problem 1
For x,y ∈ Z, we define the set
Sx,y ={mx+ny:m,n∈Z}
a) Provethatforallm,n,x,y,z∈Z,ifz|xandz|ythenz|(mx+ny).
(33 marks)
b) Prove that 2 is the smallest positive element of S4,6.
Hint: To show that the element is the smallest, you will need to show that some values cannot be obtained.
Use the fact proven in part (a)
c) Find the smallest positive element of S−6,15.
For the following questions let d = gcd(x, y) and z be the smallest positive number in Sx,y, or 0 if there are no positive numbers in Sx,y.
d) ProvethatSx,y ⊆{n∈Z:d|n}.
e) Prove that d ≤ z.
f) Prove that z|x and z|y.
Hint: consider (x%z) and (y%z)
g) Prove that z ≤ d.
h) Using the answers from (e) and (g), explain why Sx,y ⊇ {n ∈ Z : d|n}
4 marks
4 marks
4 marks
3 marks
8 marks
2 marks
4 marks
4 marks
Remark
The result that there exists m, n ∈ Z such that mx + ny = gcd(x, y) is known as Bézout’s identity. Two useful consequences of Bézout’s identity are:
• If c|x and c|y then c| gcd x, y (i.e. gcd(x, y) is a multiple of all common factors of x and y) • If gcd(x, y) = 1, then there is a unique w ∈ [0, y) such that xw =(y) 1 (i.e. multiplicative
inverses exist in modulo y, if x is coprime with y)
Problem 2 (16 marks) Proof Assistant:
Prove, using the laws of set operations (and any results proven in lectures), the following identities hold for all sets A, B, C.
a) (Annihilation) A ∩ ∅ = ∅
b) (A\C)∪(B\C) = (A∪B)\C
c) A ⊕ U = Ac
d) (DeMorgan’slaw)(A∩B)c =Ac∪Bc
4 marks
4 marks
4 marks
4 marks
4 marks
4 marks
8 marks
6 marks
Problem 3
Let Σ = {a, b}, and let
(26 marks)
d) Prove that:
L2 ∩ L3 = (Σ=6)∗
negative even number, prove that:
L2L3 =Σ∗\{a,b}
L2 = (Σ=2)∗
and L3 = (Σ=3)∗.
a) Give a complete description of Σ=2 and Σ=3; and an informal description of L2 and L3.
b) Prove that for all w ∈ L1, length(w) =(2) 0.
c) Show that Σ2 and Σ3 give a counter-example to the proposition that for all sets X,Y ⊆ Σ∗, (X ∩ Y)∗ = X∗ ∩ Y∗.
e) Using the observation that every natural number n ≥ 2 is either even or 3 more than a non-
4 marks
Advice on how to do the assignment
Collaboration is encouraged, but all submitted work must be done individually without consulting someone else’s solutions in accordance with the University’s “Academic Dishonesty and Plagiarism” policies.
• Assignments are to be submitted in inspera.
• When giving answers to questions, we always would like you to prove/explain/motivate your answers. You are being assessed on your understanding and ability.
• Be careful with giving multiple or alternative answers. If you give multiple answers, then we will give you marks only for your worst answer, as this indicates how well you understood the question.
• Some of the questions are very easy (with the help of external resources). You may make use of external material provided it is properly referenced1 – however, answers that depend too heavily on external resources may not receive full marks if you have not adequately demonstrated ability/understanding.
• Questions have been given an indicative difficulty level:
Credit Distinction High distinction
This should be taken as a guide only. Partial marks are available in all questions, and achievable
by students of all abilities.
Pass
1Proper referencing means sufficient information for a marker to access the material. Results from the lectures or textbook can be used without proof, but should still be referenced.
