CSC165H1 : Summer.2012.e4_solutions.pdf
22 Sep 2013
School
Department
Course
Professor
3
CSC165H1 Full Course Notes
Verified Note
3 documents
Document Summary
Summer 2012: for natural numbers a and b, ab is divisible by 3 exactly when either a or b is divisible by 3. (a) a n, b n, d(ab, 3) d(a, 3) d(b, 3) Of course, it"s ne to use the divisor notation: A n, b n, 3|ab 3|a 3|b (b) assume a n, b n. # to prove an equivalence, we prove the implication in each direction. Then, k n, a = 3k # de nition of divides. Let k0 n be such that a = 3k0 # [ e] Then, ab = 3k0b # [m] k0b n # n is closed under multiplication. Then, k n, b = 3k # de nition of divides. Let k0 n be such that b = 3k0 # [ e] Then, ab = 3k0a # [m] k0a n # n is closed under multiplication. Then, k n, ab = 3k # [ i] Then, 3|ab # [proof by cases, 3|a 3|b]
