Discrete Mathematics Chapter 3 Number Theory PDF

EMath 1105 DISCRETE MATHEMATICS FOR SE I Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department Number Theory  THE INTEGERS AND DIVISION...

EMath 1105 DISCRETE MATHEMATICS FOR SE I Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department Number Theory  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, on-line security). Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  New notation: 3 | 12 To specify when an integer THE DIVIDES evenly divides another integer Read as “3 divides 12” OPERATOR The not-divides operator: 𝟓 ∤ 𝟏𝟐 To specify when an integer does not evenly divide another integer Read as “5 does not divide 12” Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Divides, Factor, Multiple Let a,bZ with a0. Definition.: a|b  “a divides b” “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. Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  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 Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  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. Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  q is called the quotient r is called the remainder d is called the divisor a is called the dividend What are the quotient and remainder when 101 is divided by 11? a d q r 101 = 11  9 + 2 We write: q = 9 = 101 div 11 r = 2 = 101 mod 11 Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  More examples: 25 𝑚𝑜𝑑 7 = 4 25 𝑚𝑜𝑑 5 = 0 35 𝑚𝑜𝑑 11 = 2 Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  If a = 7 and d = 3, then q = 2 and r = 1 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. If a = −7 and d = 3, then q = −3 and r = 2 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. Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  PRACTICE! Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  REVIEW Find “a div m” and “a mod m” when a.) a = 228, m = 119 b.) a = 9009, m = 223 c.) a = - 10101, m = 333 d.) a = - 765432, m = 38271 Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department MODULAR ARITHMETIC  MODULAR 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 Notation: 𝒂 ≡ 𝒃 (𝒎𝒐𝒅 𝒎) Rephrased: 𝒎 | 𝒂 − 𝒃 Rephrased: 𝒂 𝒎𝒐𝒅 𝒎 = 𝒃 𝒎𝒐𝒅 𝒎 If they are not congruent: 𝒂 ≢ 𝒃 (𝒎𝒐𝒅 𝒎) Example: Is 17 congruent to 5 modulo 6? Rephrased: 17 ≡ 5 (mod 6) As 6 divides 17-5, they are congruent Example: Is 24 congruent to 14 modulo 6? Rephrased: 24 ≡ 14 (mod 6) As 6 does not divide 24-14, they are not congruent Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  EXERCISES: Identify if TRUE or FALSE (a) 7 ≡ 19 (mod 3) (b) 21 ≡ −8 (mod 6) (c) 53 ≡ 108 (mod 7) (d) −58 ≡ 14 (mod 8) Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department NUMBER SYSTEMS  Bases of Particular Interest Base b=10 (decimal): 10 digits: 0,1,2,3,4,5,6,7,8,9 Base b=2 (binary): 2 digits: 0,1. (“Bits”=“binary digits.”) Base b=8 (octal): 8 digits: 0,1,2,3,4,5,6,7 Base b=16 (hexadecimal): 16 digits: 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Converting to Base b (An algorithm, informally stated.) To convert any integer n to any base b>1: To find the value of the rightmost (lowest-order) digit, simply compute n mod b. Now, replace n with the quotient n/b. Repeat above two steps to find subsequent digits, until n is gone (n = 0). Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Convert 25 in binary? N = 25 a0 = 25 mod 2 = 1 N = 25 / 2 = 12 ∴ 2510 = 110012 a1 = 12 mod 2 = 0 N = 12 / 2 = 6 a2 = 6 mod 2 = 0 N = 6/2 = 3 a 3 = 3 mod 2 = 1 N = 3/ 2 =1 a4 = 1 mod 2 = 1 Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Convert 23670 in hexadecimal? ∴ 2367010 = 5𝐶7616 23670 mod 16 = 6; N=  23670/16  = 1479 mod 16 = 7 N=  1479/16  = 92 mod 16 = 12 N= 92/16  = 5 mod 16 = 5 Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Binary Expansions Most computers represent integers and do arithmetic with binary (base 2) expansions of integers. In these expansions, the only digits used are 0 and 1. Example: What is the decimal expansion of the integer that has (101011111)2 as its binary expansion? Solution: (1 0101 1111)2 = 1∙28 + 0∙27 + 1∙26 + 0∙25 + 1∙24 + 1∙23 + 1∙22 + 1∙21 + 1∙20 =351. Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Binary Expansions Example: What is the decimal expansion of the integer that has (11011)2 as its binary expansion? Solution: (11011)2 = 1 ∙24 + 1∙23 + 0∙22 + 1∙21 + 1∙20 =27. Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Octal Expansions The octal expansion (base 8) uses the digits {0,1, 2, 3, 4, 5, 6, 7}. Example: What is the decimal expansion of the number with octal expansion (7016) 8 ? Solution: 7∙83 + 0∙82 + 1∙81 + 6∙80 = 3598 Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Octal Expansions Example: What is the decimal expansion of the number with octal expansion (111)8 ? Solution: 1∙82 + 1∙81 + 1∙80 = 64 + 8 + 1 = 73 Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Hexadecimal Expansions The hexadecimal expansion needs 16 digits, but our decimal system provides only 10. So letters are used for the additional symbols. The hexadecimal system uses the digits {0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}. The letters A through F represent the decimal numbers 10 through 15. Example: What is the decimal expansion of the number with hexadecimal expansion (2AE0B)16 ? Solution: 2∙164 + 10∙163 + 14∙162 + 0∙161 + 11∙160 =175627 Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Hexadecimal Expansions Example: What is the decimal expansion of the number with hexadecimal expansion (1E5)16 ? Solution: 1∙162 + 14∙161 + 5∙160 = 256 + 224 + 5 = 485 Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Base Conversion To construct the base b expansion of an integer n:  Divide n by b to obtain a quotient and remainder.  The remainder, a0 , is the rightmost digit in the base b expansion of n. Next, divide q0 by b.  The remainder, a1, is the second digit from the right in the base b expansion of n.  Continue by successively dividing the quotients by b, obtaining the additional base b digits as the remainder. The process terminates when the quotient is 0. Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Base Conversion Example: Find the octal expansion of (12345)10 Solution: Successively dividing by 8 gives: 12345/8 = 1543 r. 1 1543/8 = 192 r. 7 192/8 = 24 r. 0 24/8 = 3 r. 0 3/8 = 0 r. 3 The remainders are the digits from right to left yielding (30071)8. Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Comparison of Hexadecimal, Octal, and Binary Representations Initial 0s are not shown Each octal digit corresponds to a block of 3 binary digits. Each hexadecimal digit corresponds to a block of 4 binary digits. So, conversion between binary, octal, and hexadecimal is easy. Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Conversion Between Binary, Octal, and Hexadecimal Expansions Example: Find the octal and hexadecimal expansions of (11 1110 1011 1100) 2. Solution:  To convert to octal, we group the digits into blocks of three (011 111 010 111 100)2, adding initial 0s as needed. The blocks from left to right correspond to the digits 3, 7, 2, 7, and 4. Hence, the solution is (37274)8.  To convert to hexadecimal, we group the digits into blocks of four (0011 1110 1011 1100)2, adding initial 0s as needed. The blocks from left to right correspond to the digits 3, E, B, and C. Hence, the solution is (3EBC)16. Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Exercises: 1. Convert the decimal expansion of each of these integers to a binary expansion. a) 231 b) 4532 c) 97644 2. Convert to binary expansion of each of these integers to a decimal expansion. a) (0001 1111)2 b) (0010 0000 0001)2 c) (0001 0101 0101)2 d) (0110 1001 0001 0000)2 Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Exercises: 3. Convert the octal expansion of each of these integers to a binary expansion. a) (572)8 c) (423)8 b) (1604)8 d) (2417)8 4. Convert the hexadecimal expansion of each of these integers to a binary expansion. a) (80𝐸)16 c) (𝐴𝐵𝐵𝐴)16 b) (135𝐴𝐵)16 d) (𝐷𝐸𝐹𝐴𝐶𝐸𝐷)16 Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Algorithms for Integer Operations ADDITION ALGORITHM Example: Add a = (1110)2 and b = (1011)2 1110 + 1011 ------------ 11001 Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Algorithms for Integer Operations MULTIPLICATION ALGORITHM Example: Find the product of a = (110)2 and b = (101)2. 110 x 101 ------------ 110 000 110 ------------ 11110 Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Algorithms for Integer Operations ALGORITHM FOR div AND mod Given integers a and d , d > 0 we can find q = a div d r = a mod d * Until such time what is left is less than d, that’s the remainder. Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Algorithms for Integer Operations MODULAR EXPONENTIATION It is important to be able to find 𝑏 𝑛 𝑚𝑜𝑑 𝑚 efficiently, where b, n, and m are large integers. Example: Use algorithm to find 3644 𝑚𝑜𝑑 645. Step 1: Initially, set x = 1 Step 2: power = 𝑏 𝑛 mod m (power = 32 mod 645) Step 3: Exponent n convert to binary. Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  Algorithms for Integer Operations Exercises: 1. Use algorithm to find 7644 𝑚𝑜𝑑 645. 2. Find the sum and product of each of these pairs of numbers. Express the answers in binary. a) (0100 0111)2 and (0111 0111)2 b) (1110 1111)2 and (1011 1101)2 Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department  REFERENCE: Rosen, K. H. (2012). Discrete Mathematics and Its Applications, 8th Edition: McGrawHill Prepared by: Engr. Alimo-ot and Engr. Sacramento, ECE Department