【正文】 1 Discrete Math CS 2800 Prof. Bart Selman Module Number Theory Rosen, Sections 34 to 37. 2 The Integers and Division Of 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, online security). 3 The divides operator New notation: 3 | 12 – To specify when an integer evenly divides another integer – Read as “3 divides 12” The notdivides operator: 5 | 12 – To specify when an integer does not evenly divide another integer – Read as “5 does not divide 12” 4 Divides, Factor, Multiple Let 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? 5 Results on the divides operator If 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 c If a | b and b | c, then a | c – Example: if 5 | 25 and 25 | 100, then 5 | 100 (“mon facts” but good to repeat for background) 6 Divides Relation Theorem: ?a,b,c ? Z: 1. a|0 2. (a|b ? a|c) ? a | (b + c) 3. a|b ? a|bc 4. (a|b ? b|c) ? a|c Corollary: If a, b, c are integers, such that a | b and a | c, then a | mb + nc whenever m and n are integers. 7 Proof 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). QED Divides Relation Corollary: 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 (., a|b ? a|be) it follows that a | mb and a | nc 。 again, from previous theorem part 2 (., (a|b ? a|c) ? a | (b + c)) it follows that a | mb + nc 9 The 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 dividend 10 What 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 + 2 We write: q = 9 = 101 div 11 r = 2 = 101 mod 11 a d q r 11 If 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 ≤rd, such that a=dq+r. Proof: We’ll use the wellordering 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 nonnegative numbers of the form a dq, where q is an integer. Hmm. Can this set be empty? By the wellordering property, S has a least element, r = a d q0. (Existence, cont.) r is nonnegative。 also, r d. otherwise if r≥ d, there would be a smaller nonnegative element in S, namely a d(q0+1) ≥ 0. But then ad(q0+1), which is smaller than adq0, is an element of S, contradicting that adq0 was the smallest element of S. So, it cannot be the case that r ≥ d, proving the existence of 0 ≤ r d and q. ? q is called the quotient ? r is called the remainder ? d is called the divisor ? a is called the dividend b) Uniqueness Suppose .,0, RdQaa n drdqat h a ts u c hdRrRrQq ???????Without loss of generality we may assume that q ≤ Q. Subtracting both equations we have: d (qQ) = (R – r) (*) So, d divides (Rr)。 so, either |d| ≤ |(R –r)| or (R – r) = 0. Since –d R r d (because ) ., |Rr| d, we must have R – r = 0. So, R = r. Substituting into the original two equations, we have dq = d Q (note d≠0) and thus q=Q, proving uniqueness. (or directly from (*)) QED dRr ?? ,0Modular arithmetic If a and b are integers and m is a positive integer, then “a is congruent to b modulo m” if m divides ab – Notation: a ≡ b (mod m) – Rephrased: m | ab – Rephrased: a mod m = b mod m – If they are not congruent: a ≡ b (mod m) Example: Is 17 congruent to 5 modulo 6? – Rephrased: 17 ≡ 5 (mod 6) – As 6 divides 175, they are congruent Example: Is 24 congruent to 14 modulo 6? – Rephrased: 24 ≡ 14 (mod 6) – As 6 does not divide 2414 = 10, they are not congruent Note: this is a different use of