CSC165H1, Winter 2022 CSC165H1: Worksheet 7—Proofs IV (Partial Solutions)
Learning Objectives
By the end of this worksheet, you will:
• Prove statements about primes and greatest common divisors.
Copyright By PowCoder代写 加微信 powcoder
• Use external facts in a proof.
Here is a reminder of two definitions from Worksheet 6:
Definition 1 (common divisor, greatest common divisor). Let x, y, d ∈ Z. We say that d is a common divisor of x and y when d divides x and d divides y. When x and y are not both 0, we say that d is the 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.
Here are some facts about divisibility, primes, and greatest common divisors that you’ll use for this worksheet (you do not need to prove them before using them). Read them carefully and make sure you understand what each one is saying before moving onto the first question. You may find it helpful to translate them into English for extra practice.1
∀x,y∈N, y≥1∧x|y⇒1≤x≤y ∀n,p∈Z, Prime(p)∧p∤n⇒gcd(p,n)=1 ∀n,m∈N, n̸=0∨m̸=0⇒gcd(n,m)≥1 ∀n,m,∈N, ∀r,s∈Z, gcd(n,m)|(rn+sm) ∀n,m∈N, ∃r,s∈Z, rn+sm=gcd(n,m)
(Fact 1) (Fact 2) (Fact 3) (Fact 4) (Fact 5) (Fact 6)
1Facts 4, 5, and 6 rely on defining gcd(0, 0) = 0 so that the statements hold for all pairs of natural numbers.
CSC165H1, Winter 2022 CSC165H1: Worksheet 7—Proofs IV (Partial Solutions)
1. Recall the first statement we considered in lecture this week:
∀n∈N, ¬Prime(n)⇒n≤1∨∃a,b∈N, n∤a∧n∤b∧n|ab
We have provided a proof header for you below. Read through it carefully to make sure you understand it, and then using Facts 1 and 2, complete the proof. Whenever you use one of these facts, clearly state which one you are using.
Hint: you may want to use the contrapositive of the implication in (Fact 2) as well.
Proof. Letn∈N. Assumethatnisnotprime,i.e.,thatn≤1orthereexistsad∈Nsuchthatd|n,d̸=1,and d ̸= n (this is the expanded definition of ¬Prime(n). We want to prove that n ≤ 1 or that there exist a, b ∈ N such that n ∤ a, n ∤ b, and n | ab.
Since our assumption is an OR, we will divide our proof into two cases (based on which part we assume to be true). Case 1: assume that n ≤ 1.
Case 2: assume there exists d ∈ N where d | n ∧ d ̸= 1 ∧ d ̸= n. Expanding the definition of divisibility, this means that there also exists k ∈ Z such that n = dk. Because n, d ∈ N, we conclude that k ∈ N as well. Also, because we handled the case of n ≤ 1 in “Case 1” above, we can assume in this case that n > 1.
Leta=dandb=k. Wewanttoprovethatn∤a,n∤b,andn|ab.
In this case, we’ve assumed that n ≤ 1, which is exactly the first part of the OR we wanted to prove.
Part 1: proving n ∤ a and n ∤ b.
Byourchoicesofaandb,weknowthata|nandb|n. ByFact2andtheassumptionn>1,thismeansthat 1≤a≤nand1≤b≤n. Sinceweseta=dandweassumedd̸=n,wecanconcludethata
We proved the statement in lecture using two facts, which you’ll now prove using the external facts from the previous page. Whenever you use a statement from the previous page, clearly state which one you are using.
(a) ∀n,m∈N, Prime(n)∧n∤m⇒∃r,s∈Z, rn+sm=1.
(b) ∀n,m∈N, Prime(n)∧∃r,s∈Z, rn+sm=1⇒n∤m.
Proof. Let n,m ∈ N. Assume that n is prime and that n ∤ m. We want to prove there exist r,s ∈ Z, rn+sm=1.
By Fact 3 and our two assumptions, we know that gcd(n, m) = 1. And then using Fact 6, there exist r, s ∈ Z such that rn + sm = gcd(n, m) = 1.
Proof. Letn,m∈N. Assumethatnisprime,andthatthereexistr,s∈Zsuchthatrn+sm=1.
By Fact 5, we know that gcd(n, m) | (rn + sm), i.e., gcd(n, m) | 1. Then using Fact 2 (substituting x = gcd(n,m) and y = 1), we know that 1 ≤ gcd(n,m) ≤ 1, and therefore gcd(n,m) = 1.
Since n is prime, its only positive divisors are 1 and itself (by the definition of prime). Since gcd(n, m) = 1 and n > 1 (by the definition of prime again), n is not a common divisor of n and m. Finally, since Fact 1 tells us that n | n, if we know that n is not a common divisor of n and m, it must be that n ∤ m.
CSC165H1, Winter 2022 CSC165H1: Worksheet 7—Proofs IV (Partial Solutions)
3. Extra. For extra practice, try proving Facts 1-5.2 They can all be proven using the definitions of divisibility, prime, and gcd. Try to use as few external facts as possible, and if you use any, prove them as well!
2Fact 6 is quite a bit harder to prove, so don’t worry about proving it here.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com