This chapter includes contents: A justification for a mathematical framework, the ceiling and floor functions, L’Hôpital’s rule, logarithms, arithmetic and other polynomial series, geometric series, recurrence relations, weighted averages, combinations. | (CSC 102) Lecture 12 Discrete Structures Previous Lecture Summary Floor and Ceiling Functions Definition of Proof Methods of Proof Direct Proof Disproving by Counterexample. Indirect Proof: Proof by Contradiction Methods of Proof and Number Theory Today's Lecture Mod Functions Divisibility and Floor Mod Congruence Indirect Proofs Proof by Contra-positive Relation between Contradiction and Contra-positive methods of Proof Compute following 113 mod 24 -29 mod 7 113 mod 24: 113 div 24 -29 mod 7: -29 div 7 Mod Functions Mod and div Definitions Theorem Divisibility and Floor Cont Use the floor notation to compute 3850 div 17 and 3850 mod 17. Sol: Computing div and mod Let a, b be integers and n be a positive integer. We say that a is congruent to b modulo n (. a b(mod n) ) iff n | (b-a), implies that there exist some integer k such that b-a = n·k. Note: a mod n = b mod n Which of the following are true? 3 3 (mod 17) 3 -3 (mod 17) 172 177 (mod 5) -13 13 (mod 26) Mod Congruence's Cont 3 3 (mod 17) True: any number is congruent to itself (3-3 = 0, divisible by all) 3 -3 (mod 17) False: (-3-3) = 6 isn’t divisible by 17. 172 177 (mod 5) True: 177-172 = 5 is a multiple of 5 -13 13 (mod 26) True: 13-(-13) = 26 divisible by 26. Congruence's Identities Let n > 1 be fixed and a, b, c, d be arbitrary integers. Then the following properties holds: (Reflexive Property ) a a (mod n). (Symmetric Property) If a b(mod n) then b a(mod n). ( Transitive Property) If a b(mod n) and b c (mod n) then a c(mod n). If a b(mod n) and c d (mod n) then a + c (b + d ) (mod n) and a·c b·d(mod n). If a b(mod n) then a + c b+c(mod n) and a·c b·c(mod n). If a b(mod n) then a k b k (mod n) for any positive integer k. Theorem If k is any integer such that k 1 (mod 3), then k3 1 (mod 9). Proof: k Z, k 1(mod 3) k 3 1(mod 9) k 1(mod 3) n, k-1 = 3n n, k = 3n + 1 n, k 3 = (3n + 1)3 n, k 3 = 27n 3 + 27n 2 + 9n + 1 n, k 3-1 = 27n 3 | (CSC 102) Lecture 12 Discrete Structures Previous Lecture Summary Floor and Ceiling Functions Definition of Proof Methods of Proof Direct Proof Disproving by Counterexample. Indirect Proof: Proof by Contradiction Methods of Proof and Number Theory Today's Lecture Mod Functions Divisibility and Floor Mod Congruence Indirect Proofs Proof by Contra-positive Relation between Contradiction and Contra-positive methods of Proof Compute following 113 mod 24 -29 mod 7 113 mod 24: 113 div 24 -29 mod 7: -29 div 7 Mod Functions Mod and div Definitions Theorem Divisibility and Floor Cont Use the floor notation to compute 3850 div 17 and 3850 mod 17. Sol: Computing div and mod Let a, b be integers and n be a positive integer. We say that a is congruent to b modulo n (. a b(mod n) ) iff n | (b-a), implies that there exist some integer k such that b-a = n·k. Note: a mod n = b mod n Which of the following are true? 3 3 (mod 17) 3 -3 (mod 17) 172 177 (mod 5) -13 13 (mod 26) Mod .
