CSC165H1, Winter 2022 CSC165H1: Worksheet 6—Proofs III (Partial Solutions)
Learning Objectives
By the end of this worksheet, you will:
• Understand and use the definition of greatest common divisor in statements and proofs.
Copyright By PowCoder代写 加微信 powcoder
• Write proofs and disproofs using the proof by cases and contrapositive (indirect) proof techniques.
1. Greatest common divisor. In this question, you’ll explore a new definition which is fundamental in number
theory: the greatest common divisor of two numbers.
(a) As a warm-up, we are going to first consider how to express the idea of the “greatest” or “maximum” number that satisfies some predicate. Let P : N → {True,False} be a predicate. Express in predicate logic the statement “123 is the maximum natural number that satisfies P.”
Hint: Think about trying to complete the sentence “every number that satisfies P is. . . ” Also, don’t forget to express the fact that 123 has to satisfy P .
(b) Now consider the following two definitions.
Definition 1 (common divisor, greatest common divisor). Let x,y,d ∈ Z. We say that d is a common divisorofxandywhenddividesxandddividesy. Whenxandyarenotboth0,wesaythatdisthe greatest common divisor (gcd) of x and y when it is the maximum common divisor of x and y. We also define the greatest common divisor of 0 and 0 to be equal to 0 (as a special case).
We also define the function gcd : Z × Z → N to be the function that takes two integers and returns their greatest common divisor.
In the space below, translate the above definitions as predicates. (You can use IsCD in the definition of IsGCD, and the divisibility predicate in both.)
IsCD(x,y,d): “d is a common divisor of x and y,” where x,y,d ∈ Z IsGCD(x, y, d): “d is the greatest common divisor of x and y,” where x, y, d ∈ Z
P(123)∧∀n∈N, P(n)⇒n≤123
IsCD(x,y,d):d|x∧d|y, wherex,y,d∈Z IsGCD(x, y, d) : x = 0 ∧ y = 0 ⇒ d = 0 ∧
x̸=0∨y̸=0⇒IsCD(x,y,d)∧∀d1 ∈Z, IsCD(x,y,d1)⇒d1 ≤d, wherex,y,d∈Z
CSC165H1, Winter 2022 CSC165H1: Worksheet 6—Proofs III (Partial Solutions)
(c) Using the definition of divisibility and gcd, determine how to complete the following statement, and then prove it. (Note: be very careful about what you’re proving, and make sure you give explicit proofs of divisibility here!)
∀x ∈ Z+, IsGCD(x, 0, ) Youcanuseinyourproofthefactthatforalln∈Z+ andd∈Z,ifddividesnthend≤n.
The full statement we’ll prove is
∀x ∈ Z+, IsGCD(x, 0, x)
Discussion. We want to prove that gcd(x, 0) = x, which (by the definition of gcd) consists of proving two
• xisacommondivisorofxand0.
• Every common divisor of x and 0 is ≤ x.
We should be able to do the first part using the definition of divisibility; for the second part, we’ll use the
fact given in the question.
Proof. Let x ∈ Z+. We’ll prove that IsGCD(x,0,x), i.e. (using the definition), x = 0 ∧ 0 = 0 ⇒ x = 0 and that x ̸= 0 ∨ 0 ̸= 0 ⇒ IsCD(x,0,x) ∧ (∀d1 ∈ Z, IsCD(x,0,d1) ⇒ d1 ≤ x). One subtlety here is that the first implication is actually vaucously true (since x = 0 is false, as x ∈ Z+). We’ll prove the second implication now.
First, assume x ̸= 0 ∨ 0 ̸= 0 (this is actually always true for x ∈ Z+). We’ll prove that x is a common divisorofxand0,andthatforeveryd1 ∈Z,ifd1 isacommondivisorofxand0,thend1 ≤x. Our proof will be divided into three parts.
Part 1: proving that x | x.
Letk1 =1. Thenx=k1x,andsox|x.
Part 2: proving that x | 0.
Letk2 =0. Then0=k2x,andsox|0.
Part 3: proving that every common divisor of x and 0 is ≤ x.
Let d ∈ Z, and assume that d divides both x and 0. Then because d | x and x ∈ Z+, using the “fact” given in the question we can conclude that d ≤ x.
(d) Here is one of the most famous and useful properties of the greatest common divisor. We probably won’t have time to prove this statement in the course, but we’ll certainly use it!
For every pair of integers a and b, if at least one of them is non-zero, then gcd(a,b) is the smallest positive integer that can be written in the form pa + qb, where p and q are integers.1
In the space below, translate the above statement into predicate logic. You may define helper predicates to help simplify your formula, and you can use “gcd(a, b)” directly in your translation.
Let’s define the following helper predicate:∗
LinComb(a,b,c):“∃p,q∈Z, c=pa+qb,′′ wherea,b,c∈Z.
Then we can express the above statement as:
∀a,b∈Z, a̸=0∨b̸=0⇒LinComb(a,b,gcd(a,b))∧∀d∈Z+, LinComb(a,b,d)⇒d≥gcd(a,b) ∗We call expressions of the form pa + qb a linear combination of a and b.
1For example, gcd(6,22) = 2, and 2 = (−7) · 6 + (2) · 22.
CSC165H1, Winter 2022 CSC165H1: Worksheet 6—Proofs III (Partial Solutions)
2. Proof by cases. Often when proving a universally-quantified statement, the same argument in a proof does not actually apply to all cases. Consider the following (True) statement:
For every integer n, n2 − 3n is even.
Such statements are usually easier to prove by dividing the domain into different parts, and giving a different argument for each part separately. We call such a proof a proof by cases, where the term “case” refers to one of the different parts of the domain that are considered.
In this question, we will use the fact that every integer is either even or odd, and so divide up our proof into two cases. Practice using the proof by cases technique by completing the following proof.
Proof. Let n ∈ Z. We will divide this proof into two cases: when n is even, and when n is odd. Case 1: assume that n is even, i.e., ∃k ∈ Z, n = 2k.
[TODO: prove that n2 − 3n is even, assuming that n is even.]
This can be proved using a simple calculation. Letting k1 = 2k2 − 3k, we have:
n2 − 3n = (2k)2 − 3(2k) = 4k2 − 6k
= 2(2k2 − 3k) = 2k1
Case 2: assume that n is odd, i.e., ∃k ∈ Z, n = 2k − 1. [TODO: prove that n2 − 3n is even, assuming that n is odd.]
3. An indirect (contrapositive) proof. We saw in lecture that the contrapositive form of an implication can often be easier to work with when writing a proof. Let’s study a more complex example.
∀a,b∈N, 1