Summer.2012.e4_solutions.pdf

2 Pages
118 Views
Unlock Document

Department
Computer Science
Course
CSC165H1
Professor
Nathalie Fournier
Semester
Fall

Description
CSC165H1Y Homework Exercise # 4 Summer 2012 1. For natural numbers a and b, ab is divisible by 3 exactly when either a or b is divisible by 3. (a) 8a 2 N;8b 2 N;D(ab;3) , D(a;3) _ D(b;3) Of course, it’s ▯ne to use the divisor notation: 8a 2 N;8b 2 N;3jab , 3ja _ 3jb (b) Assume a 2 N;b 2 N. # To prove an equivalence, we prove the implication in each direction. Assume 3ja _ 3jb Case 1: Assume 3ja Then, 9k 2 N;a = 3k # De▯nition of divides Let k02 N be such that a = 3k 0 # [9E] Then, ab = 3k 0 # [M] k0b 2 N # N is closed under multiplication Then, 9k 2 N;ab = 3k # [9I] Then, 3jab # De▯nition of divides Case 1: Assume 3jb Then, 9k 2 N;b = 3k # De▯nition of divides Let k02 N be such that b = 3k 0 # [9E] Then, ab = 3k 0 # [M] k0a 2 N # N is closed under multiplication Then, 9k 2 N;ab = 3k # [9I] Then, 3jab # De▯nition of divides Then, 3jab # [Proof by cases, 3ja _ 3jb] Then, 3ja _ 3jb ) 3jab # [) I] # For the other side, we’ll use an indirect proof. Assume :(3ja _ 3jb) Then, :(3ja) ^ :(3jb) # De Morgan’s law Then, :(3ja) # [^E] Then, :(3jb) # [^E] Then, 9q 2 N;r 2 N;a = 3q + r ^ 0 < r < 3 # The remainder of division of a by 3 is not 0 Let q 0 N and r 20N be such that a = 3q + r 0 0 <0r < 3 0 # [9 E] Then, 9q 2 N;r 2 N;b = 3q + r ^ 0 < r < 3 # The remainder of division of b by 3 is not 0
More Less

Related notes for CSC165H1

Log In


OR

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


OR

By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.


Submit