1M. HauskrechtCS 441 Discrete mathematics for CSCS 441 Discrete Mathematics for CSLecture 12Milos [email protected] Sennott SquareIntegers and division M. HauskrechtCS 441 Discrete mathematics for CSSymmetric matrixDefinition:• A square matrix A is called symmetric if A = AT. • Thus A =[aij] is symmetric if aij= ajifor i and j with 1≤ i≤ nand 1≤ j≤ n. • Example:1 1 0 01 0 1 00 1 1 10 0 1 0• Is it a symmetric matrix? yes2M. HauskrechtCS 441 Discrete mathematics for CSZero-one matrixDefinition:• A matrix with entries that are either 0 or 1 is called a zero-one matrix. • Algorithms operating on discrete structures represented by zero-one matrices are based on Boolean arithmetic defined by the Boolean operations and and or :andorM. HauskrechtCS 441 Discrete mathematics for CSJoin and meet of matricesDefinition: Let A and B be two matrices: • The join of A and B is:• The meet of A and B is3M. HauskrechtCS 441 Discrete mathematics for CSCS 441 Discrete Mathematics for CSLecture 12Milos [email protected] Sennott SquareIntegers and division M. HauskrechtCS 441 Discrete mathematics for CSIntegers and division• Number theory is a branch of mathematics that explores integers and their properties.• Integers:– Z integers {…, -2,-1, 0, 1, 2, …}– Z+positive integers {1, 2, …}• Number theory has many applications within computer science, including:– Indexing - Storage and organization of data– Encryption– Error correcting codes– Random numbers generators4M. HauskrechtCS 441 Discrete mathematics for CSDivisionDefinition: Assume 2 integers a and b, such that a =/ 0 (a is not equal 0). We say that a divides b if there is an integer c such that b = ac. If a divides b we say that a is a factor of b and that b is multiple of a. • The fact that a divides b is denoted as a | b.Examples:• 4 | 24 True or False ? True• 4 is a factor of 24• 24 is a multiple of 4• 3 | 7 True or False ? FalseM. HauskrechtCS 441 Discrete mathematics for CSDivisibilityAll integers divisible by d>0 can be enumerated as:– .., -kd, …, -2d, -d, 0, d, 2d, …, kd, …• Question:Let n and d be two positive integers. How many positive integers not exceeding n are divisible by d?• 0 < kd ≤ n• Answer:Count the number of integers kd that are less than n. What is the number of integers k such that 0 < kd ≤ n ?0 < kd ≤ n  0 < k ≤ n/d. Therefore, there are |_n/d _| positive integers not exceeding n that are divisible by d.5M. HauskrechtCS 441 Discrete mathematics for CSDivisibilityProperties:• Let a, b, c be integers. Then the following hold:1. if a | b and a | c then a | (b +c)2. if a | b then a | bc for all integers c3. if a | b and b | c then a | cProof of 1: if a | b and a | c then a | (b +c)• from the definition of divisibility we get:• b=au and c=av where u,v are two integers. Then• (b+c) = au +av = a(u+v) • Thus a divides b+c.M. HauskrechtCS 441 Discrete mathematics for CSDivisibilityProperties:• Let a, b, c be integers. Then the following hold:1. if a | b and a | c then a | (b +c)2. if a | b then a | bc for all integers c3. if a | b and b | c then a | cProof of 2: if a | b then a | bc for all integers c• If a | b, then there is some integer u such that b = au.• Multiplying both sides by c gives us bc = auc, so by definition, a | bc. • Thus a divides bc.6M. HauskrechtCS 441 Discrete mathematics for CSPrimesDefinition: A positive integer p that is greater than 1 and that is divisible only by 1 and by itself (p) is called a prime.Examples: 2, 3, 5, 7, …1 | 2 and 2 | 2, 1 |3 and 3 | 3, etcM. HauskrechtCS 441 Discrete mathematics for CSPrimesDefinition: A positive integer p that is greater than 1 and that is divisible only by 1 and by itself (p) is called a prime.Examples: 2, 3, 5, 7, …1 | 2 and 2 | 2, 1 |3 and 3 | 3, etcWhat is the next prime after 7? •11Next?•137M. HauskrechtCS 441 Discrete mathematics for CSPrimesDefinition: A positive integer that is greater than 1 and is not a prime is called a composite.Examples: 4, 6, 8, 9, …Why?2 | 4Why 6 is a composite?M. HauskrechtCS 441 Discrete mathematics for CSPrimesDefinition: A positive integer that is greater than 1 and is not a prime is called a composite.Examples: 4, 6, 8, 9, …Why?2 | 43 | 6 or 2 | 62 | 8 or 4 | 83 | 98M. HauskrechtCS 441 Discrete mathematics for CSThe Fundamental theorem of ArithmeticFundamental theorem of Arithmetic: • Any positive integer greater than 1 can be expressed as a product of prime numbers.Examples:• 12 = ?M. HauskrechtCS 441 Discrete mathematics for CSThe Fundamental theorem of ArithmeticFundamental theorem of Arithmetic: • Any positive integer greater than 1 can be expressed as a product of prime numbers.Examples:• 12 = 2*2*3• 21 = 3*7• Process of finding out factors of the product: factorization.9M. HauskrechtCS 441 Discrete mathematics for CSPrimes and compositesFactorization of composites to primes:• 100 = 2*2*5*5 = 22*52• 99 = 3*3*11 = 32*11Important question:• How to determine whether the number is a prime or a composite? M. HauskrechtCS 441 Discrete mathematics for CSPrimes and composites• How to determine whether the number is a prime or a composite? Simple approach (1):•Let n be a number. To determine whether it is a prime we can test if any number x < n divides it. If yes it is a composite. If we test all numbers x < n and do not find the proper divisor then nis a prime.10M. HauskrechtCS 441 Discrete mathematics for CSPrimes and composites• How to determine whether the number is a prime or a composite? Simple approach (1):•Let n be a number. To determine whether it is a prime we can test if any number x < n divides it. If yes it is a composite. If we test all numbers x < n and do not find the proper divisor then nis a prime. • Example:• Assume we want to check if 17 is a prime? • The approach would require us to check: • 2,3,4,5,6,7,8,9,10,11,12,13,14,15,16M. HauskrechtCS 441 Discrete mathematics for CSPrimes and composites• Example approach 1:• Assume we want to check if 17 is a prime? • The approach would require us to check: • 2,3,4,5,6,7,8,9,10,11,12,13,14,15,16• Is this the best we can do?• No. The problem here is that we try to test all the numbers. But this is not necessary. • Idea: Every composite factorizes to a product of primes. So it is