CSE115/ENGR160 Discrete Mathematics 03/15/113.4 Integers and divisionExampleTheoremThe division algorithmModular arithmeticSlide 7Slide 8Slide 9Slide 10CorollaryApplications of congruencePseudorandom numbersSlide 14CryptologySlide 163.5 Primes and greatest common divisionsSlide 18Slide 19Slide 20Procedure for prime factorizationSlide 22Slide 23TheoremMersenne primesSlide 26Distribution of primesOpen problems about primesGreatest common divisorsPrime factorization and GCDLeast common multipleCSE115/ENGR160 Discrete Mathematics03/15/11Ming-Hsuan YangUC Merced13.4 Integers and division•Number theory: the branch of mathematics involves integers and their properties•If a and b are integers with a≠0, we say that a divides b if there is an integer c s.t. 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 a divides b. We write a ∤ b when does not divide b2Example•Let n and d be positive integers. How many positive integers not exceeding n are divisible by d?•The positive integers divisible by d are all integers of them form dk, where k is a positive integer•Thus, there are positive integers not exceeding n that are divisible by d3 dn /Theorem•Let a, b, and c be integers, then–If a | b and a| c, then a | (b+c)–If a | b, and a | bc for all integers c–If a | b and b | c, then a | c•If a, b, and c are integers s.t. a | b and a | c, then a | mb+nc whenever m and n are integers4The division algorithm•Let a be integer and d be a positive integer. Then there are unique integers q and r with 0 ≤ r < d, s.t. a=dq+r•In the equality, q is the quotient, r is the remainder q = a div d, r = a mod d•-11 divided by 3•-11=3(-4)+1, -4=-11 div 3, 1=-11 mod 3•-11=3(-3)-2, but remainder cannot be negative5Modular arithmetic•If a and b are integers and m is a positive integer, then a is congruent to 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 a and b are not congruent modulo m, we write a ≢b (mod m)•Let a and b be integers, m be a positive integer. Then a≡b (mod m) if and only if a mod m = b mod m6Example•Determine whether 17 is congruent to 5 modulo 6 and whether 24 and 14 are not congruent modulo 6–17-5=12, we see 17≡5 (mod 6)–24-14=10, and thus 24≢14 (mod 6)7Theorem•Karl Friedrich Gauss developed the concept of congruences at the end of 18th century•Let m be a positive integer. The integer a and b are congruent modulo m if and only if there is an integer k such that a=b+km–() If a=b+km, then km=a-b, and thus m divides a-b and so a≡b (mod m)–() if a≡b (mod m), then m | a-b. Thus, a-b=km, and so a=b+km8Theorem•Let m be a positive integer. If a ≡ b (mod m) and c ≡ d (mod m), then a+c=b+d (mod m) and ac ≡ bd (mod m)–Since a ≡ b (mod m) and c ≡ d (mod m), there are integers s.t. b=a+sm and d=c+tm–Hence, b+d=(a+c)+m(s+t), bd=(a+sm)(c+tm)=ac+m(at+cs+stm)–Hence a+c ≡ b+d (mod m), and ac ≡ bd (mod m)9Example•7 ≡ 2 (mod 5) and 11 ≡ 1 (mod 5), so–18=7+11 ≡ 2+1=3 (mod 5)–77=7 11 ≡2 1=2(mod 5)∙ ∙10Corollary•Let m be a positive integer and let a and b be integers, then (a+b) mod m=((a mod m) +(b mod m)) mod m ab mod m = ((a mod m)(b mod m)) mod m•By definitions mod m and congruence modulo m, we know that a≡(a mod m)(mod m) and b≡(b mod m)(mod m). Hence–(a+b) ≡((a mod m)+(b mod m)) (mod m)–ab ≡ (a mod m)(b mod m)(mod m)11Applications of congruence•Hashing function: h(k) where k is a key•One common function: h(k)=k mod m where m is the number of available memory location•For example, m=111, –h(064212848)=064212848 mod 111=14–h(037149212)=037149212 mod 111=65•Not one-to-one mapping, and thus needs to deal wit collision–h(107405723)=107405723 mod 111 = 14–Assign to the next available memory location12Pseudorandom numbers•Generate random numbers•The most commonly used procedure is the linear congruential method–Modulus m, multiple a, increment c, and seed x0, with 2≤a<m, 0 ≤c<m, and 0≤x0<m–Generate a sequence of pseudorandom numbers {xn} with 0 ≤ xn < m for all n, by xn+1=(axn+c) mod m13Example•Let m=9, a=7, c=4, x0=3–x1=7x0+4 mod 9=(21+4) mod 9=25 mod 9 = 7–x2=7x1+4 mod 9=(49+4) mod 9=53 mod 9 = 8–x3=7x2+4 mod 9=(56+4) mod 9=60 mod 9 = 6–x4=7x3+4 mod 9=(42+4) mod 9=46 mod 9 = 1–x5=7x4+4 mod 9=(7+4) mod 9=11 mod 9 = 2–x6=7x5+4 mod 9=(14+4) mod 9=18 mod 9 = 0–x7=7x6+4 mod 9=(0+4) mod 9=4 mod 9 = 4–x8=7x7+4 mod 9=(28+4) mod 9=32 mod 9 =5–x9=7x8+4 mod 9=(35+4) mod 9=11 mod 9 = 3•A sequence of 3, 7, 8, 6, 1, 2, 0, 4, 5, 3, 7, 8, 6, 1, 2, 0, 4, 5, 3, …•Contains 9 different numbers before repeating14Cryptology•One of the earliest known use is by Julius Caesar, shift each letter by 3 f(p)=(p+3) mod 26–Translate “meet you in the park”–12 4 4 19 24 14 20 8 13 19 7 4 15 0 17 10 –15 7 7 22 1 17 23 11 16 22 10 7 18 3 20 13–“phhw brx lq wkh sdun”–To decrypt, f-1(p)=(p-3) mod 2615Example•Other options: shift each letter by k–f(p)=(p+k) mod 26, with f-1(p)=(p-k) mod 26–f(p)=(ap+k) mod 26163.5 Primes and greatest common divisions•Prime: a positive integer p greater than 1 if the only positive factors of p are 1 and p•A positive integer greater than 1 that is not prime is called composite •Fundamental theorem of arithmetic: Every positive integer greater than 1 can be written uniquely as a prime or as the product of two or more primes when the prime factors are written in order of non-decreasing size17Example•Prime factorizations of integers–100=2 2 5 5=2∙ ∙ ∙25∙2–641=641–999=3 3 3 37=3∙ ∙ ∙337∙–1024=2 2 2 2 2 2 2 2 2 2=2∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙1018Theorem•Theorem: If n is a composite integer, then n has a prime division less than or equal to •As n is composite, n has a factor 1<a<n, and thus n=ab•We show that a≤ or b ≤ (by contraposition)•Thus n has a divisor not exceeding•This divisor is either prime or by the fundamental theorem of arithmetic, has a prime divisor less than itself , and thus a prime divisor less than less than 19nn nnnExample•Show that 101 is prime•The only primes not exceeding are 2, 3, 5, 7•As 101 is not divisible by 2, 3, 5, 7, it follows that 101 is prime 20101Procedure for prime factorization•Begin by diving n by successive primes, starting