DivisionIntegers Divisible by $d$Integers Divisible by $d$Properties of the Divides RelationThe Division AlgorithmModular ArithmeticModular ArithmeticModular ArithmeticModular ArithmeticModular ArithmeticPrimesThe Fundamental Theorem of ArithmeticBound on Largest Prime FactorThe Infinitude of PrimesGreatest Common DivisorLeast Common MultiplePrime Factorization/Gcm/LcmPrime Factorization/Gcm/LcmThe Euclidean AlgorithmThe Euclidean AlgorithmThe Euclidean AlgorithmSome Useful FactsSome Useful FactsSome Usful FactsMathematical InductionIntro to Discrete StructuresLecture 12Pawel M. WocjanSchool of Electrical Engineering and Computer ScienceUniversity of Central [email protected] to Discrete StructuresLecture 12 – p. 1/39DivisionDefinition 1: If a, b ∈ Z with a 6= 0, we say that a divides b ifthere exists c ∈ Z such that b = ac.When a divides b we say that a is a factor of b and that b isa multiple of a.The notation a | b denotes that a divides b. We write a 6| b if adoes not divide b.a | b if and only if ∃c (ac = b)Intro to Discrete StructuresLecture 12 – p. 2/39Produced with a Trial Version of PDF Annotator - www.PDFAnnotator.comIntegers Divisible by dExample 2: Let n and d be positive integers. How manypositive integers not exceeding n are divisible by n?Intro to Discrete StructuresLecture 12 – p. 3/39Produced with a Trial Version of PDF Annotator - www.PDFAnnotator.comIntegers Divisible by dExample 2: Let n and d be positive integers. How manypositive integers not exceeding n are divisible by n?This equals the number of integers k with0 < dk ≤ n, or equivalently, with 0 < k ≤ n/d .Therefore, there are ⌊n/d⌋ positive integers not exceeding nthat are divisible by d.Intro to Discrete StructuresLecture 12 – p. 4/39Produced with a Trial Version of PDF Annotator - www.PDFAnnotator.comProperties of the Divides RelationTheorem 1: Let a, b, and c be integers. Thena | b ∧ a | c ⇒ a | b + ca | b ⇒ ∀c (a | bc)a | b ∧ b | c ⇒ a | cCorollary 1:a | b ∧ a | c ⇒ ∀m∀n (a | mb + nc)Intro to Discrete StructuresLecture 12 – p. 5/39Produced with a Trial Version of PDF Annotator - www.PDFAnnotator.comThe Division AlgorithmTheorem 2: Let a be an integer and d a positive integer.Then there are unique integers q and r, with 0 ≤ r < d, suchthat a = dq + r.Quotientq = a div d = ⌊a/d⌋Remainderr = a mod d = a − dqIntro to Discrete StructuresLecture 12 – p. 6/39Produced with a Trial Version of PDF Annotator - www.PDFAnnotator.comModular ArithmeticDefinition 3: If a and b are integers and m is a positiveinteger, then a is congruent b modulo m if m divides a − b.We use the notation a ≡ b (mod m) to indicate that a iscongruent 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 − bIntro to Discrete StructuresLecture 12 – p. 7/39Produced with a Trial Version of PDF Annotator - www.PDFAnnotator.comModular ArithmeticIntro to Discrete StructuresLecture 12 – p. 8/39Produced with a Trial Version of PDF Annotator - www.PDFAnnotator.comModular ArithmeticIntro to Discrete StructuresLecture 12 – p. 9/39Produced with a Trial Version of PDF Annotator - www.PDFAnnotator.comModular ArithmeticIntro to Discrete StructuresLecture 12 – p. 10/39Produced with a Trial Version of PDF Annotator - www.PDFAnnotator.comModular ArithmeticIntro to Discrete StructuresLecture 12 – p. 11/39Produced with a Trial Version of PDF Annotator - www.PDFAnnotator.comPrimesDefinition 1: A positive integer p greater than 1 is calledprime if the only positive integers of p are 1 and p.A positive integer p greater than 1 and is not prime is calledcoprime.http://en.wikipedia.org/wiki/Prime_numberIntro to Discrete StructuresLecture 12 – p. 12/39Produced with a Trial Version of PDF Annotator - www.PDFAnnotator.comThe Fundamental Theorem of ArithmeticTheorem 1: Every positive integer greater than 1 can bewritten uniquely as a prime or as the product of two or moreprimes where the prime factors are written in order ofnondecreasing size.Intro to Discrete StructuresLecture 12 – p. 13/39Produced with a Trial Version of PDF Annotator - www.PDFAnnotator.comBound on Largest Prime FactorTheorem 2: If n is a composite integer, then n has a primedivisor less than or equal to√n.Intro to Discrete StructuresLecture 12 – p. 14/39Produced with a Trial Version of PDF Annotator - www.PDFAnnotator.comThe Infinitude of PrimesTheorem 3: There are infinitely many primes.Intro to Discrete StructuresLecture 12 – p. 15/39Produced with a Trial Version of PDF Annotator - www.PDFAnnotator.comGreatest Common DivisorDefinition 2: Let a and b be integers, not both zero. Thelargest integer d such that d | a and d | b is called thegreatest common divisor of a and b.It is denoted by gcd(a, b).Intro to Discrete StructuresLecture 12 – p. 16/39Produced with a Trial Version of PDF Annotator - www.PDFAnnotator.comLeast Common MultipleDefinition 5: Let a and b be integers, not both zero. Thesmallest positive d such that a | d and b | d is called thesmallest common multiple of a and b.It is denoted by lcm(a, b).Intro to Discrete StructuresLecture 12 – p. 17/39Produced with a Trial Version of PDF Annotator - www.PDFAnnotator.comPrime Factorization/Gcm/LcmLet a and b be two positive integers anda = pe11pe22···penn=nYj=1pejjb = pf11pf22···pfnn=nYj=1pfjjtheir prime factorizations.Intro to Discrete StructuresLecture 12 – p. 18/39Produced with a Trial Version of PDF Annotator - www.PDFAnnotator.comPrime Factorization/Gcm/LcmThen, the greatest common divisor and the least commonmultiple are given bygcd(a, b) = pmin(e1,f1)1pmin(e2,f2)2···pmin(en,fn)n=nYj=1pmin(ej,fj)jlcm(a, b) = pmax(e1,f1)1pmax(e2,f2)2···pmax(en,fn)n=nYj=1pmax(ej,fj)jWe also have the identityab = gcd(a, b) · lcm(a, b) .Intro to Discrete StructuresLecture 12 – p. 19/39Produced with a Trial Version of PDF Annotator - www.PDFAnnotator.comThe Euclidean AlgorithmLemma 1: Leta = bq + rwhere a, b, q, and r are integers. Thengcd(a, b) = gcd(b, r) .Intro to Discrete StructuresLecture 12 – p. 20/39The Euclidean AlgorithmIntro to Discrete StructuresLecture 12 – p. 21/39The Euclidean AlgorithmExample 12: Find gcd(414, 662) using the EuclideanAlgorithm.Intro to Discrete StructuresLecture 12 – p. 22/39Some Useful FactsTheorem 1:∀a ∀b ∃s ∃t gcd(a, b) = sa + tb .The pair (s, t) can be efficiently computed with the extendedEuclidean algorithm.Intro to Discrete
View Full Document
Unlocking...