Discrete Math CS 2800The Integers and DivisionThe divides operatorDivides, Factor, MultipleResults on the divides operatorDivides RelationProof of (2)Slide 8The Division “Algorithm”Slide 10Slide 11Theorem: Division “Algorithm” --- 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.Slide 13Slide 14Modular arithmeticSlide 16Spiral Visualization of modMore on congruencesEven even more on congruenceApplications of CongruencesHashing FunctionsHash FunctionsHash Function RequirementsWhy are these important?Slide 25A Simple Hash Using modSlide 27CollisionDigital Signature ApplicationPseudorandom numbersSlide 31Slide 32Slide 33Slide 34Cryptology (secret messages)The Caesar cipherSlide 37Rot13 encodingPrimes and Greatest Common DivisorPrime numbersFundamental theorem of arithmeticFundamental theorem of arithmetic: Strong Induction [from before]Composite factorsShowing a number is primeShowing a number is compositeSlide 46Slide 47Slide 48Mersenne numbersSlide 50Slide 52Slide 53Slide 54Slide 55Slide 56Slide 57The prime number theoremSlide 59Slide 60Slide 61Greatest common divisorRelative primesPairwise relative primeMore on gcd’sLeast common multiplelcm and gcd theoremEuclid’s Algorithm for GCDSlide 69Euclidean AlgorithmEuclid’s Algorithm ExampleIntegers and AlgorithmsBase-b number systemsBase SystemsBases of Particular InterestSlide 76Converting to Base bConstructing Base b ExpansionsSlide 79Slide 80Addition of Integers in Binary NotationMultiplying IntegersModular ExponentiationModular Exponentiation: Using Binary Expansion of exponent nSlide 85Slide 86Slide 87Two Additional Applications: 1 - Performing arithmetic with large numbers 2 - Public Key System  require additional key results in Number TheoryAdditional Number Theory ResultsProof of Theorem 1Slide 91Proof of Lemma 1Proof of Lemma 2Uniqueness of Prime FactorizationsProof of Theorem 2An Application of Theorem 2Linear Congruences, InversesSlide 98Slide 99Slide 100Chinese Remainder TheoremSlide 102Computer Arithmetic with Large IntsSlide 104Slide 105Slide 106Slide 107“Bigger” ExamplePseudoprimesSlide 110Fermat’s Little TheoremSlide 112Carmichael numbersSlide 114Slide 115Number Theory: RSA and Public-key CryptographyNumber Theory: Public Key EncryptionPublic Key CryptographyRivest-Shamir-Adleman (RSA)RSA ApproachSlide 121Slide 122Why RSA WorksProof cont.Slide 125Slide 1261Discrete MathCS 2800Prof. Bart [email protected] Number TheoryRosen, Sections 3-4 to 3-7.2The Integers and DivisionOf course, you already know what the integers are, and what division is…However: There are some specific notations, terminology, and theorems associated with these concepts which you may not know.These form the basics of number theory.–Vital in many important algorithms today (hash functions, cryptography, digital signatures; in general, on-line security).3The divides operatorNew notation: 3 | 12–To specify when an integer evenly divides another integer–Read as “3 divides 12”The not-divides operator: 5 | 12–To specify when an integer does not evenly divide another integer–Read as “5 does not divide 12”4Divides, Factor, MultipleLet a,bZ with a0.Defn.: a|b  “a divides b” : ( cZ: b=ac)“There is an integer c such that c times a equals b.”–Example: 312  True, but 37  False.Iff a divides b, then we say a is a factor or a divisor of b, and b is a multiple of a.Ex.: “b is even” :≡ 2|b. Is 0 even? Is −4?5Results on the divides operatorIf a | b and a | c, then a | (b+c)–Example: if 5 | 25 and 5 | 30, then 5 | (25+30)If a | b, then a | bc for all integers c–Example: if 5 | 25, then 5 | 25*c for all ints cIf a | b and b | c, then a | c–Example: if 5 | 25 and 25 | 100, then 5 | 100(“common facts” but good to repeat for background)6Divides RelationTheorem: a,b,c  Z:1. a|02. (a|b  a|c)  a | (b + c)3. a|b  a|bc4. (a|b  b|c)  a|cCorollary: If a, b, c are integers, such that a | b and a | c, then a | mb + nc whenever m and n are integers.7Proof of (2) Show a,b,c  Z: (a|b  a|c)  a | (b + c).Let a, b, c be any integers such that a|b and a|c, and show that a | (b + c).By defn. of | , we know s: b=as, and t: c=at. Let s, t, be such integers.Then b+c = as + at = a(s+t). So, u: b+c=au, namely u=s+t. Thus a|(b+c). QEDDivides RelationCorollary: If a, b, c are integers, such that a | b and a | c, then a | mb + nc whenever m and n are integers.Proof: From previous theorem part 3 (i.e., a|b  a|be) it follows that a | mb and a | nc ; again, from previous theorem part 2 (i.e., (a|b  a|c)  a | (b + c)) it follows that a | mb + nc9The Division “Algorithm”Theorem:Division Algorithm --- 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.It’s really a theorem, not an algorithm… Only called an “algorithm” for historical reasons.• q is called the quotient • r is called the remainder • d is called the divisor • a is called the dividend10What are the quotient and remainder when 101 is divided by 11?•q is called the quotient •r is called the remainder •d is called the divisor •a is called the dividend 101 = 11  9 + 2We write:q = 9 = 101 div 11r = 2 = 101 mod 11a d q r11If a = 7 and d = 3, then q = 2 and r = 1, since 7 = (2)(3) + 1. If a = −7 and d = 3, then q = −3 and r = 2, since −7 = (−3)(3) + 2. So: given positive a and (positive) d, in order to get r we repeatedly subtract d from a, as many times as needed so that what remains, r, is less than d.Given negative a and (positive) d, in order to get r we repeatedly add d to a, as many times as needed so that what remains, r, is positive (or zero) and less than d.Theorem:Division “Algorithm” --- 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.Proof: We’ll use the well-ordering property directly that states that every set of nonnegative integers has a least element.a) Existence We want to show the existence of q and r, with the property that a = dq+r, 0 ≤r <d Note: this set is non empty since q can be a negative integer with large absolute value.Consider the set of non-negative numbers of the form a - dq, where q is an integer. Hmm. Can this set be empty?By the