Intro to Discrete Structures Lecture 12 Pawel M Wocjan School of Electrical Engineering and Computer Science University of Central Florida wocjan eecs ucf edu Intro to Discrete StructuresLecture 12 p 1 39 Produced with a Trial Version of PDF Annotator www PDFAnnotator com Division Definition 1 If a b Z with a 6 0 we say that a divides b if there exists c Z such that b ac When a divides b we say that a is a factor of b and that b is a multiple of a The notation a b denotes that a divides b We write a 6 b if a does not divide b a b if and only if c ac b Intro to Discrete StructuresLecture 12 p 2 39 Produced with a Trial Version of PDF Annotator www PDFAnnotator com Integers Divisible by d Example 2 Let n and d be positive integers How many positive integers not exceeding n are divisible by n Intro to Discrete StructuresLecture 12 p 3 39 Produced with a Trial Version of PDF Annotator www PDFAnnotator com Integers Divisible by d Example 2 Let n and d be positive integers How many positive integers not exceeding n are divisible by n This equals the number of integers k with 0 dk n or equivalently with 0 k n d Therefore there are n d positive integers not exceeding n that are divisible by d Intro to Discrete StructuresLecture 12 p 4 39 Produced with a Trial Version of PDF Annotator www PDFAnnotator com Properties of the Divides Relation Theorem 1 Let a b and c be integers Then a b a c a b c a b a b a c c a bc b c a c Corollary 1 a b m n a mb nc Intro to Discrete StructuresLecture 12 p 5 39 Produced with a Trial Version of PDF Annotator www PDFAnnotator com The Division Algorithm Theorem 2 Let a be an integer and d a positive integer Then there are unique integers q and r with 0 r d such that a dq r Quotient q a div d a d Remainder r a mod d a dq Intro to Discrete StructuresLecture 12 p 6 39 Produced with a Trial Version of PDF Annotator www PDFAnnotator com Modular Arithmetic Definition 3 If a and b are integers and m is a positive integer then a is congruent b modulo m if m divides a b We use the notation a b mod m to indicate that a is congruent to b modulo m If there are not congruent then we write a 6 b mod m a b mod m if and only if m a b Intro to Discrete StructuresLecture 12 p 7 39 Produced with a Trial Version of PDF Annotator www PDFAnnotator com Modular Arithmetic Intro to Discrete StructuresLecture 12 p 8 39 Produced with a Trial Version of PDF Annotator www PDFAnnotator com Modular Arithmetic Intro to Discrete StructuresLecture 12 p 9 39 Produced with a Trial Version of PDF Annotator www PDFAnnotator com Modular Arithmetic Intro to Discrete StructuresLecture 12 p 10 39 Produced with a Trial Version of PDF Annotator www PDFAnnotator com Modular Arithmetic Intro to Discrete StructuresLecture 12 p 11 39 Produced with a Trial Version of PDF Annotator www PDFAnnotator com Primes Definition 1 A positive integer p greater than 1 is called prime if the only positive integers of p are 1 and p A positive integer p greater than 1 and is not prime is called coprime http en wikipedia org wiki Prime number Intro to Discrete StructuresLecture 12 p 12 39 Produced with a Trial Version of PDF Annotator www PDFAnnotator com The Fundamental Theorem of Arithmetic Theorem 1 Every positive integer greater than 1 can be written uniquely as a prime or as the product of two or more primes where the prime factors are written in order of nondecreasing size Intro to Discrete StructuresLecture 12 p 13 39 Produced with a Trial Version of PDF Annotator www PDFAnnotator com Bound on Largest Prime Factor Theorem 2 If n is a composite integer then n has a prime divisor less than or equal to n Intro to Discrete StructuresLecture 12 p 14 39 Produced with a Trial Version of PDF Annotator www PDFAnnotator com The Infinitude of Primes Theorem 3 There are infinitely many primes Intro to Discrete StructuresLecture 12 p 15 39 Produced with a Trial Version of PDF Annotator www PDFAnnotator com Greatest Common Divisor Definition 2 Let a and b be integers not both zero The largest integer d such that d a and d b is called the greatest common divisor of a and b It is denoted by gcd a b Intro to Discrete StructuresLecture 12 p 16 39 Produced with a Trial Version of PDF Annotator www PDFAnnotator com Least Common Multiple Definition 5 Let a and b be integers not both zero The smallest positive d such that a d and b d is called the smallest common multiple of a and b It is denoted by lcm a b Intro to Discrete StructuresLecture 12 p 17 39 Produced with a Trial Version of PDF Annotator www PDFAnnotator com Prime Factorization Gcm Lcm Let a and b be two positive integers and a pe11 pe22 penn b pf11 pf22 pfnn n Y pj j j 1 n Y pj j e f j 1 their prime factorizations Intro to Discrete StructuresLecture 12 p 18 39 Produced with a Trial Version of PDF Annotator www PDFAnnotator com Prime Factorization Gcm Lcm Then the greatest common divisor and the least common multiple are given by min e f min e1 f1 min e2 f2 pn n n p2 gcd a b p1 lcm a b max e1 f1 max e2 f2 max en fn p1 p2 pn n Y min ej fj pj j 1 n Y max ej fj pj j 1 We also have the identity ab gcd a b lcm a b Intro to Discrete StructuresLecture 12 p 19 39 The Euclidean Algorithm Lemma 1 Let a bq r where a b q and r are integers Then gcd a b gcd b r Intro to Discrete StructuresLecture 12 p 20 39 The Euclidean Algorithm Intro to Discrete StructuresLecture 12 p 21 39 The Euclidean Algorithm Example 12 Find gcd 414 662 using the Euclidean Algorithm Intro to Discrete StructuresLecture 12 p 22 39 Some Useful Facts Theorem 1 a b s t gcd a b sa tb The pair s t can be efficiently computed with the extended Euclidean algorithm Intro to Discrete StructuresLecture 12 p 23 39 Some Useful Facts Lemma 2 If p is a prime and p a1 a2 an where each ai is an integer then p ai for some i Intro to Discrete StructuresLecture 12 p 24 39 Some Usful Facts Lemma 1 gcd a b 1 a bc a c Proof of the uniqueness of the prime factorization of a positive integer Intro to Discrete StructuresLecture 12 p 25 39 Intro to Discrete StructuresLecture 12 p 26 39 Mathematical Induction Intro to Discrete StructuresLecture …
View Full Document
Unlocking...