CSC165H1: Problem Set 2

CSC165H1 Problem Set 2
CSC165H1: Problem Set 2
General instructions
Please read the following instructions carefully before starting the problem set. They contain important
information about general problem set expectations, problem set submission instructions, and reminders
of course policies.
? Your problem sets are graded on both correctness and clarity of communication. Solutions which
are technically correct but poorly written will not receive full marks. Please read over your solutions
carefully before submitting them. Proofs should have headers and bodies in the form described in
the course note.
? Each problem set may be completed in groups of up to three. If you are working in a group for this
problem set, please consult https://github.com/MarkUsProject/Markus/wiki/Student_Groups
for a brief explanation of how to create a group on MarkUs.
Exception: Problem Sets 0 and 1 must be completed individually.
? Solutions must be typeset electronically, and submitted as a PDF with the correct ?lename. Handwritten submissions will receive a grade of ZERO.
The required ?lename for this problem set is problem set2.pdf.
? Problem sets must be submitted online through MarkUs. If you haven't used MarkUs before, give
yourself plenty of time to ?gure it out, and ask for help if you need it! If you are working with a
partner, you must form a group on MarkUs, and make one submission per group. \I didn't know
how to use MarkUs" is not a valid excuse for submitting late work.
? Your submitted ?le should not be larger than 9MB. This may happen if you are using a word
processing software like Microsoft Word; if it does, you should look into PDF compression tools to
make your PDF smaller, although please make sure that your PDF is still legible before submitting!
? The work you submit for credit must be your own; you may not refer to or copy from the work of
other groups, or external sources like websites or textbooks. You may, however, refer to any text
from the Course Notes (or posted lecture notes), except when explicitly asked not to.
Additional instructions
? For each proof you write, make sure to ?rst write in predicate logic the precise statement, fully
simpli?ed, that you're going to prove. For a disproof, clearly write the fully simpli?ed negation.
You do not need to show your work for computing negations of statements. Your proof should include
a header, where names and assumptions are introduced, and a body, where statements leading to
the conclusion are derived.
? For proofs involving divisibility, primes, and the oor function, you may not use any external facts
other than those mentioned in the questions. You should not (and will not need to) prove any external
facts to complete this problem set.
Page 1/3
CSC165H1, Fall 2017 Problem Set 2
? For any concrete numbers, you may state whether one divides another, or whether a number is
prime, without proof. For example, you can write statements \3 j 12" and \15 is not prime" without
justi?cation.
1. [6 marks] divisibility...
Composite(n): \n is greater than 1 and not prime." for n 2 N. Prove the statements below.
(a) [3 marks]
8n 2 N
+; Composite(n
2 + 3n + 2)
(b) [3 marks]
8n 2 N
+; Composite(n
2 + 6n + 5)
2. [21 marks] more gcd!
Let a; b 2 N, assume they are not both 0. De?ne L = fn 2 N
+ : 9x; y 2 Z; n = ax + byg. Prove the
claims below, being sure to ?rst state the claim you are proving in predicate logic, and then to write the
complete proof. You may use the result of earlier claims in proving later ones, for example you might use
claim (f) to help prove claim (g). Anti-hint: You may not use Claims (1){(6) from Tutorial 4, since you
are proving some of them!
(a) [3 marks] Claim: L has a minimum element m, i.e. m is no larger than any other element of L. You
may use, without proof, the fact that any non-empty, ?nite set of real numbers has a minimum
element1
(b) [3 marks] Claim: Any multiple km, where k 2 N
+, is an element of L.
(c) [3 marks] Claim: Any element c 2 L is a multiple of m. Hint: Show that you may assume that
c is non-negative, no smaller than m, and then use the Quotient-Remainder Theorem to derive a
contradiction.
(d) [3 marks] Claim: m divides a and m divides b.
(e) [3 marks] Claim: Any natural number n that divides both a and b also divides m.
(f) [3 marks] Claim: m is the greatest common divisor of a and b.
(g) [3 marks] Claim: If a and b are coprime, i.e. m = gcd a; b = 1, and c 2 Z, and a j bc, then a divides c.
Hint: a j c is equivalent to c ? 0 (mod a), and 2(f) should be helpful here.
3. [3 marks] a prime example...
Theorem 2.3 established that there are in?nitely many prime numbers. It seems pretty clear all but one
prime number are odd. You can go further:
(a) [3 marks] Prove that that the set P = fp j P rime(p) ^ p ? 3 (mod 4)g is in?nite.
Hint: Think about the technique of Theorem 2.3, and also that there are other arithmetic manipulations
other than adding one, such as multiplying by 4 or even subtracting 1.
1Notice that this is not necessarily true of in?nite sets, for example Z or (0; 1), nor is it true of the empty set.
Page 2/3
CSC165H1, Fall 2017 Problem Set 2
4. [7 marks] Function growth. Now let's leave numbers and talk about functions. Consider the following
de?nition:2
Definition 1. Let f; g : N ! R
?0
. We say that g is eventually dominated by f if and only if there exists
n0 2 R
?0
such that every natural number n greater than or equal to n0 satis?es g(n) ? f(n).
We can express this de?nition in a predicate Edom(f; g): \g is eventually dominated by f", where
f; g : N ! R
?0
, in the following way:
EDom(f; g) : 9n0 2 R
?0
; 8n 2 N; n ? n0 ) g(n) ? f(n)
(a)Let f(n) = 0:5n
2
and g(n) = 2n + 1650. Prove that g is eventually dominated by f. Do NOT use
part (b) to prove this part; we want to see you construct a proof with concrete numbers rather than
the variables you'll use in part (b).
Hint: pay attention to the order of the quanti?ers. The ?rst line of your proof should introduce the
variable n0, and give it a concrete value.
(b)Prove the following statement, which is a generalization of the previous part:
8a; b 2 R
?0
; g(n) = an + b is eventually dominated by f(n) = 0:5n
2
:
Hint: you don't need to pick the \best" n0 here, just pick one that works and makes the proof's
calculations easy for you to work with! Which variables can n0 depend on?
2The symbol R
?0
denotes the set of all nonnegative real numbers, i.e., R
?0 = fx j x 2 R ^ x ? 0g.
Page 3/3