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