《离散数学英文课件：DM_lecture3_4_5 The Integers and Division》由会员分享，可在线阅读，更多相关《离散数学英文课件：DM_lecture3_4_5 The Integers and Division（15页珍藏版）》请在金锄头文库上搜索。
1、Discrete Mathematics 1Hui Gao3.4: The Integers and DivisionlOf course, you already know what the integers are, and what division islBut: There are some specific notations, terminology, and theorems associated with these concepts which you may not know.lThese form the basics of number theory.lVital i
2、n many important algorithms today (hash functions, cryptography, digital signatures).Discrete Mathematics 2Hui GaoDivides, Factor, MultiplelLet a,bZ with a0.lDef.: a|b “a divides b” : (cZ: b=ac)“There is an integer c such that c times a equals b.”lExample: 312 True, but 37 False.lIff a divides b, th
3、en we say a is a factor or a divisor of b, and b is a multiple of a.lEx.: “b is even” : 2|b. Discrete Mathematics 3Hui GaoFacts re: the Divides RelationlTheorem: a,b,c Z:1. a|02. (a|b a|c) a | (b + c)3. a|b a|bc4. (a|b b|c) a|clProof of (2): a|b means there is an s such that b=as, and a|c means that
4、 there is a t such that c=at, so b+c = as+at = a(s+t), so a|(b+c) also.Discrete Mathematics 4Hui GaoPrime NumberslAn integer p1 is prime iff it is not the product of two integers greater than 1:p1 a,bN: a1, b1, ab=p.lThe only positive factors of a prime p are 1 and p itself. Some primes: 2,3,5,7,11,
5、13.lNon-prime integers greater than 1 are called composite, because they can be composed by multiplying two integers greater than 1.Discrete Mathematics 5Hui GaoFundamental Theorem of ArithmeticlEvery positive integer has a unique representation as the product of a non-decreasing series of zero or m
6、ore primes.lSome examples:l1 = (product of empty series) = 1l2 = 2 (product of series with one element 2)l4 = 22 (product of series 2,2)l2000 = 2222555; 2001 = 32329;2002 = 271113; 2003 = 2003Discrete Mathematics 6Hui GaoAn Application of Primes!lWhen you visit a secure web site (https: address, ind
7、icated by padlock icon in IE), the browser and web site may be using a technology called RSA encryption.lThis public-key cryptography scheme involves exchanging public keys containing the product pq of two random large primes p and q, which must be kept secret by a given party.lSo, the security of y
8、our day-to-day web transactions depends critically on the fact that all known factoring algorithms are intractable!Discrete Mathematics 7Hui GaoThe Division “Algorithm”lIts really just a theorem, not an algorithm lOnly called an “algorithm” for historical reasons.lTheorem: For any integer dividend a
9、 and divisor d0, there is a unique integer quotient q and remainder rN such that a = dq + r and 0 r |d|. Formally, the theorem is: a,dZ, d0: !q,rZ: 0r 1, so their gcd = 1.lA set of integers a1,a2, is (pairwise) relatively prime if all pairs (ai, aj), for ij, are relatively prime.Discrete Mathematics
10、 11Hui GaoLeast Common Multiplellcm(a,b) of positive integers a, b, is the smallest positive integer that is a multiple both of a and of b. E.g. lcm(6,10)=30m = lcm(a,b) = min(m: a|m b|m) a|m b|m nZ: (a|n b|n) (m n)lIf the prime factorizations are written as and lthen the LCM is given byDiscrete Mat
11、hematics 12Hui GaoThe mod operatorlAn integer “division remainder” operator.lLet a,dZ with d1. Then a mod d denotes the remainder when a is divided by d.lUsing e.g. long division.lWe can compute (a mod d) by: a da/d.lIn C/C+/Java languages, “%” = mod.Discrete Mathematics 13Hui GaoModular Congruencel
12、Let a,bZ, mZ+.Where Z+=nZ | n0=N0 (the + integers).lThen a is congruent to b modulo m, written “a b (mod m)”, iff m | ab .lNote: this is a different use of “” than the meaning “is defined as” Ive used before.lIts also equivalent to: (ab) mod m = 0.Discrete Mathematics 14Hui GaoUseful Congruence Theo
13、remslTheorem: Let a,bZ, mZ+. Then:a b (mod m) kZ a=b+km.lTheorem: Let a,b,c,dZ, mZ+. Then if a b (mod m) and c d (mod m), then: a+c b+d (mod m), and ac bd (mod m)Discrete Mathematics 15Hui GaoApplications of Congruence Hashing function. E.g. let k be your id. no. Assume we have m locations and hashing function: h(k) = k mod m h(064212848) = 064212848 mod 111=14 h(037149212) = 037149212 mod 111=65 Pseudorandom Numbers. Let modulus m, multiplier a, increment c, seed x0.xn+1=(axn+c) mod m
