双语离散计算技术ch5-阅读版.pdfVIP

R. Johnsonbaugh, Discrete Mathematics 7th edition, 2009 Instructor Hui Tong Chapter 5 Introduction to Number Theory Introduction to Number Theory Number theory is about integers and their properties. We will start with the basic principles of  divisibility (整除性),  greatest common divisors,  least common multiples, and  modular arithmetic (模运算) and look at some relevant algorithms. 5.1 Divisors If a and b are integers with a  0, we say that a divides b if there is an integer c so that 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 means that a divides b. We write a  b when a does not divide b Divisibility Theorems For integers a, b, and c it is true that  if a | b and a | c, then a | (b + c)  Example: 3 | 6 and 3 | 9, so 3 | 15.  if a | b, then a | bc for all integers c  Example: 5 | 10, so 5 | 20, 5 | 30, 5 | 40, …  if a | b and b | c, then a | c  Example: 4 | 8 and 8 | 24, so 4 | 24.  Primes A positive integer p greater than 1 is called prime if the only positive factors of p are 1 and p. A positive integer that is greater than 1 and is not prime is called composite. The fundamental theorem of arithmetic: Every positive integer can be written uniquely as the product of primes, where the prime factors are written in order of increasing size. Primes Examples: 15 = 3·5 48 = 2·2·2·2·3 = 24·3 17 = 17 100 = 2·2·5·5 = 22·52 512 = 2·2·2·2·2·2·2·2·2 = 29 515 = 5·103 28 = 2·2·7 Primes Theorem: If n is a composite integer, then n has a prime divisor less than or equal n This is easy to see: if n is a co