Study Guides (248,228)
CSC165H1 (27)

# Summer.2012.e4_solutions.pdf

2 Pages
118 Views

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
Me

OR

Join OneClass

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

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.