Report

Discrete Structures Chapter 4: Elementary Number Theory and Methods of Proof 4.3 Direct Proof and Counter Example III: Divisibility The essential quality of a proof is to compel belief. – Pierre de Fermat, 1601-1665 4.3 Direct Proof and Counter Example III: Divisibility 1 Definitions If n and d are integers and d 0 then n is divisible by d iff n equals d times some integer. Instead of “n is divisible by d,” we can say that n is a multiple of d d is a factor of n d is a divisor of n d divides n The notation d | n is read “d divides n.” Symbolically, if n and d are integers and d 0. d | n an integer k s.t. n = dk. 4.3 Direct Proof and Counter Example III: Divisibility 2 NOTE • Since the negation of an existential statement is universal, it follows that d does not divide n iff, for all integers k, n dk, or, in other words, n/d is not an integer. n and d , d | n n is not an integer. d 4.3 Direct Proof and Counter Example III: Divisibility 3 Theorems • Theorem 4.3.1 – A Positive Divisor of a Positive Integer For all integers a and b, if a and b are positive and a divides b, then a b. • Theorem 4.3.2 – Divisors of 1 The only divisors of 1 are a and -1. • Theorem 4.3.3 – Transitivity of Divisibility For all integers a ,b, and c, if a divides b and b divides c, then a divides c. 4.3 Direct Proof and Counter Example III: Divisibility 4 Theorems • Theorem 4.3.4 – Divisibility by a Prime Any integer n > 1 is divisible by a prime number. • Theorem 4.3.5 – Unique Factorization of Integers Theorem (Fundamental Theorem of Arithmetic) G iven any integer n 1, k , distinct prim e n um bers p1 , p 2 , p 3 , ..., p n , and positive integers e1 , e 2 , e 3 , ..., e n s .t. n p1 1 p 2 2 p 3 3 e e e e p nn and any other expression for n as a pr oduct of prim e num bers is identical to this except, perhaps, fo r the order in w hich the factors are w ritten. 4.3 Direct Proof and Counter Example III: Divisibility 5 Definition G iven any integer n 1, the standar d factored form of n is an expression of the form n p1 1 p 2 2 p 3 3 e e e e pkk w here k is a positive integer; p1 , p 2 , p 3 , ..., p k are prim e num bers; e1 , e 2 , e 3 , ..., e k are positive integers; and p1 p 2 p 3 ... p k . 4.3 Direct Proof and Counter Example III: Divisibility 6 Example – pg. 178 # 12 • Give a reason for your answer. Assume that all variable represent integers. If n 4 k 1, does 8 divide n 1? 2 4.3 Direct Proof and Counter Example III: Divisibility 7 Example – pg. 178 # 16 • Prove the statement directly from the definition of divisibility. For all integers a , b , and c , if a | b and a | c then a | b c . 4.3 Direct Proof and Counter Example III: Divisibility 8 Example – pg. 178 # 27 • Determine whether the statement is true or false. Prove the statement directly from the definitions if it is true, and give a counterexample if it is false. For all integers a , b , and c , if a | b c then a | b o r a | c . 4.3 Direct Proof and Counter Example III: Divisibility 9 Example – pg. 178 # 28 • Determine whether the statement is true or false. Prove the statement directly from the definitions if it is true, and give a counterexample if it is false. F o r all in teg ers a , b , an d c , if a | b c th en a | b o r a | c . 4.3 Direct Proof and Counter Example III: Divisibility 10 Example – pg. 178 # 35 • Two athletes run a circular track at a steady pace so that the first completes one round in 8 minutes and the second in 10 minutes. If they both start from the same spot at 4 pm, when will be the first they return to the start together. 4.3 Direct Proof and Counter Example III: Divisibility 11 Example – pg. 178 # 37 • Use the unique factorization theorem to write the following integers in standard factored form. – b. 5,733 – c. 3,675 4.3 Direct Proof and Counter Example III: Divisibility 12