tailieunhanh - Lecture Discrete mathematics and its applications (7/e) – Chapter 4: Number theory and cryptography

Lecture Discrete mathematics and its applications (7/e) – Chapter 4: Number theory and cryptography. This chapter presents the following content: Divisibility and modular arithmetic, integer representations and algorithms, primes and greatest common divisors, solving congruences, applications of congruences, cryptography. | Number Theory and Cryptography Chapter 4 With Question/Answer Animations Copyright © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of McGraw-Hill Education. Chapter Motivation Number theory is the part of mathematics devoted to the study of the integers and their properties. Key ideas in number theory include divisibility and the primality of integers. Representations of integers, including binary and hexadecimal representations, are part of number theory. Number theory has long been studied because of the beauty of its ideas, its accessibility, and its wealth of open questions. We’ll use many ideas developed in Chapter 1 about proof methods and proof strategy in our exploration of number theory. Mathematicians have long considered number theory to be pure mathematics, but it has important applications to computer science and cryptography studied in Sections and . Chapter Summary Divisibility and Modular Arithmetic Integer Representations and Algorithms Primes and Greatest Common Divisors Solving Congruences Applications of Congruences Cryptography Divisibility and Modular Arithmetic Section Section Summary Division Division Algorithm Modular Arithmetic Division Definition: If a and b are integers with a ≠ 0, then a divides b if there exists an integer c such that b = ac. When a divides b we say that a is a factor or divisor of b and that b is a multiple of a. The notation a | b denotes that a divides b. If a | b, then b/a is an integer. If a does not divide b, we write a ∤ b. Example: Determine whether 3 | 7 and whether 3 | 12. 6 Properties of Divisibility Theorem 1: Let a, b, and c be integers, where a ≠0. If a | b and a | c, then a | (b + c); If a | b, then a | bc for all integers c; If a | b and b | c, then a | c. Proof: (i) Suppose a | b and a | c, then it follows that there are integers s and t with b = as and c = at. Hence, b + c = as + at = a(s + t). Hence, a | (b + c) (Exercises 3 . | Number Theory and Cryptography Chapter 4 With Question/Answer Animations Copyright © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of McGraw-Hill Education. Chapter Motivation Number theory is the part of mathematics devoted to the study of the integers and their properties. Key ideas in number theory include divisibility and the primality of integers. Representations of integers, including binary and hexadecimal representations, are part of number theory. Number theory has long been studied because of the beauty of its ideas, its accessibility, and its wealth of open questions. We’ll use many ideas developed in Chapter 1 about proof methods and proof strategy in our exploration of number theory. Mathematicians have long considered number theory to be pure mathematics, but it has important applications to computer science and cryptography studied in Sections and . Chapter Summary Divisibility and Modular Arithmetic