Discrete Mathematics Lecture 5 PDF

Discrete Mathematics Lecture 05 Dr. Ahmed Hagag Faculty of Computers and Artificial Intelligence Benha University Fall 2025  Chapter 4: Number Theory The Integers and Division. Integer Representations. Primes...

Discrete Mathematics Lecture 05 Dr. Ahmed Hagag Faculty of Computers and Artificial Intelligence Benha University Fall 2025  Chapter 4: Number Theory The Integers and Division. Integer Representations. Primes. Greatest Common Divisors. Least Common Multiple. ©Ahmed Hagag Discrete Mathematics 2  Division (1/15) DEFINITION 𝑏 (or equivalently, if is an integer) 𝑎 ©Ahmed Hagag Discrete Mathematics 3  Division (1/15) DEFINITION Remark: We can express 𝑎 ∣ 𝑏 using quantifiers as ∃𝑐(𝑎𝑐 = 𝑏), where the universe of discourse is the set of integers. ©Ahmed Hagag Discrete Mathematics 4  Division (2/15) Example 1 ©Ahmed Hagag Discrete Mathematics 5  Division (2/15) Example 1 – Solution ©Ahmed Hagag Discrete Mathematics 6  Division (3/15) Example 2 A number line indicates which integers are divisible by the positive integer 𝑑. which integers are divisible by the positive integer 𝒅. ©Ahmed Hagag Discrete Mathematics 7  Division (4/15) Example 3 Let 𝑛 and 𝑑 be positive integers. How many positive integers not exceeding 𝑛 are divisible by 𝑑? The positive integers divisible by 𝑑 are all the integers of the form 𝑑𝑘, where 𝑘 is a positive integer. Hence, the number of positive integers divisible by 𝑑 that do not exceed 𝑛 equals the number of integers 𝑘 with 0 < 𝑑𝑘 ≤ 𝑛, or with 0 < 𝑘 ≤ 𝑛/𝑑. Therefore, there are 𝒏/𝒅 positive integers not exceeding 𝑛 that are divisible by 𝑑. ©Ahmed Hagag Discrete Mathematics 8  Division (5/15) THEOREM 𝐋𝐞𝐭 𝒂, 𝒃, 𝐚𝐧𝐝 𝒄 𝐛𝐞 𝐢𝐧𝐭𝐞𝐠𝐞𝐫𝐬, 𝐰𝐡𝐞𝐫𝐞 𝒂 ≠ 𝟎. 𝐓𝐡𝐞𝐧 𝑖 if 𝑎 𝑏 and 𝑎 𝑐, then 𝑎 | 𝑏 + 𝑐 𝑖𝑖 if 𝑎 𝑏, then 𝑎 𝑏𝑐 for all integers 𝑐 𝑖𝑖𝑖 if 𝑎 𝑏 and 𝑏 𝑐, then 𝑎 | 𝑐 𝐀𝐬 𝐚 𝐫𝐞𝐬𝐮𝐥𝐭: If 𝑎 𝑏 and 𝑎 𝑐, then 𝑎 | 𝒎𝑏 + 𝒏𝑐 whenever 𝒎 and 𝒏 are integers ©Ahmed Hagag Discrete Mathematics 9  Division (6/15) Examples 1) Does 2 divdes 4? 2) Does 2 divdes 8? 3) 2 divdes 4 + 8 ? 4) Does 2 divdes 4? 5) Does 2 divdes 4 ∗ 5? 6) Does 2 divdes 4 ∗ 4? 7) Does 2 divdes 4? 8) Does 4 divdes 16? 9) Does 2 divdes 16? ©Ahmed Hagag Discrete Mathematics 10  Division (7/15) The Division Algorithm Let 𝒂 be an integer and 𝒅 a positive integer. Then dividend 𝑎 = 𝑞𝑢𝑜𝑡𝑖𝑒𝑛𝑡 𝑞 , 𝑟𝑒𝑚𝑎𝑖𝑛𝑑𝑒𝑟 𝑟 𝑑 divisor 𝑤𝑖𝑡ℎ , 0≤𝑟 1, we see that 10, 19, and 24 are not pairwise relatively prime. ©Ahmed Hagag Discrete Mathematics 61  Least Common Multiple (1/5) DEFINITION “𝐥𝐜𝐦” ©Ahmed Hagag Discrete Mathematics 62  Least Common Multiple (2/5) Example 1 What is the lcm 24, 36 ? 24 are 2, 3 36 are 2, 3, 5 24 2 36 2 12 2 18 2 6 2 9 3 3 = 23 ∙ 3 3 = 22 ∙ 32 3 3 1 1 lcm 24,36 = 23 ∙ 32 = 72 ©Ahmed Hagag Discrete Mathematics 63  Least Common Multiple (3/5) Example 2 What is the lcm 120, 500 ? 120 are 2, 3,5,7 500 are 2, 3, 5,7,11,13,17,19 120 2 500 2 60 2 250 2 30 2 125 5 15 3 = 23 ∙ 3 ∙ 5 25 5 = 22 ∙ 53 5 5 5 1 5 1 lcm 120, 500 = 23 ∙ 31 ∙ 53 = 3000 ©Ahmed Hagag Discrete Mathematics 64  Least Common Multiple (4/5) THEOREM Let 𝑎 and 𝑏 be positive integers. Then 𝑎𝑏 = gcd(𝑎, 𝑏) ⋅ lcm(𝑎, 𝑏) ©Ahmed Hagag Discrete Mathematics 65  Least Common Multiple (5/5) Example 3 What are the 𝐠𝐜𝐝 𝟏𝟐𝟎, 𝟓𝟎𝟎 and 𝐥𝐜𝐦 𝟏𝟐𝟎, 𝟓𝟎𝟎 ? 120 are 2, 3,5,7 500 are 2, 3, 5,7,11,13,17,19 120 2 500 2 60 2 250 2 30 2 125 5 15 3 = 23 ∙ 3 ∙ 5 25 5 = 22 ∙ 53 5 5 5 1 5 1 lcm 120, 500 = 23 ∙ 31 ∙ 53 = 3000 120 ∗ 500 gcd 120, 500 = = 20 3000 ©Ahmed Hagag Discrete Mathematics 66  Applications (1/4) 1. Hashing Functions 2. Pseudorandom Numbers 3. Cryptography … ©Ahmed Hagag Discrete Mathematics 67  Applications (2/4) 1. Hashing Functions ©Ahmed Hagag Discrete Mathematics 68  Applications (3/4) 2. Pseudorandom Numbers linear congruential method ©Ahmed Hagag Discrete Mathematics 69  Applications (4/4) 𝑚 is the number Classical Cryptography of elements in the 3. Cryptography language used. Encryption 𝑘 is called a key Decryption ©Ahmed Hagag Discrete Mathematics 70  Video Lectures All Lectures: https://www.youtube.com/playlist?list=PLxIvc-MGOs6gZlMVYOOEtUHJmfUquCjwz Lectures #5: https://www.youtube.com/watch?v=Q-zLpSW3oSU&list=PLxIvc- MGOs6gZlMVYOOEtUHJmfUquCjwz&index=31 https://www.youtube.com/watch?v=3IXniblNWdo&list=PLxIvc- Up to time 00:21:34 MGOs6gZlMVYOOEtUHJmfUquCjwz&index=32 https://www.youtube.com/watch?v=1AZzb2FAVc4&list=PLxIvc- MGOs6gZlMVYOOEtUHJmfUquCjwz&index=34 ©Ahmed Hagag Discrete Mathematics 71 Thank You Dr. Ahmed Hagag [email protected]