1、Chapter 4: Number TheoryElements of Discrete Structures1Intro to Integers and DivisionA branch of mathematics is called Number TheoryIt involves integers and their propertiesBasic concept of number theory is used through out computer scienceWe will study: integer division, modular arithmetic, primes

2、(素數), greatest common divisors and some algorithms in number theory2DivisionDefinition: If aZ and bZ with a 0, we say that a divides b if c Z, b = ac. It is also called b is divisible by aWhen a divides b, we say a is a factor of b and that b is a multiple of aWe use a | b to denote a divides bWe us

3、e a b to denote a does not divides b3ExampleLet n and d be positive integers. Question: How many positive integers n are divisible by d?Those numbers are 1d, 2d, , kd, where kd n and (k+1)d nSo, from kd n, we know k n/d. We conclude that there are n/d positive integers n that are divisible by dWhen

4、n = 11, d = 3, 11/3 = 3. The positive integers that are divisible by 3 are 3, 6, and 94Theorem 1Theorem 1: Let a, b and c Z :If a|b and a|c, then a|(b + c)If a|b then a|bc for all c ZIf a|b and b|c, then a|cProof of 1): by definition, d Z e Z and b = ad and c = ae. So b + c = ad + ae = a(d + e), d +

5、 e is an integer. By definition, a divides b + c5The Division AlgorithmTheorem 2: (Proof will be given later)Every integer a, when divided by a positive integer d, can be expressed uniquely in terms of a quotient q Z and a remainder r N as a = dq + r (0 r d) We call d the divisor, a the dividend, q

6、the quotient, and r the remainder.q = a div d r = a mod d (a modulo d) (Be used very often)6The Division AlgorithmDivision Algorithm Examples: 11 div 3 = 3; 11 mod 3 = 2; Or 11 = 33 + 2-11 div 3 = -4; -11 mod 3 = 1; Or -11 = 3(-4) + 112 div 3 = 4; 12 mod 3 = 0; Or 3 divides 12, or 3 | 12“a divides b

7、” is equivalent to “b mod a = 0”7Modular ArithmeticDefinition: Given two integers a and b, and a positive integer m. Then a is congruent(同余) to b modulo m, denoted by a b (mod m), if m | (a b)Theorem 3: Let a and b be integers and m a positive integer. Then a b (mod m) iff (a mod m) = (b mod m)By th

8、e Division Theorem, let a = mq1 + r1 and b = mq2 + r28Modular ArithmeticProof of Theorem 3:IF: if (a mod m) = (b mod m) (remainders are the same: r1 = r2), then a b = mq1 + r1 (mq2 + r2)= m(q1 q2) or m | (a b). By definition, a is congruent to b modulo m9Modular ArithmeticProof of Theorem 3:ONLY-IF:

9、 by definition of congruence, there exists k Z, a b = km, or a = b + km (i)From the Division Algorithm, for some q, r Zb = qm + r, (0 r 1 is called prime if the only positive factors of p are 1 and pDefinition: a positive integer 1 that is not prime is called compositePrimes less than 100 are2, 3, 5

10、, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 71, 73, 79, 83, 89, 9712The Fundamental Theorem of ArithmeticEvery positive integer can be written uniquely as a prime or the product of primes (in nondecreasing order)(Proof by Induction will be provided in Chapter 5)Examples100 = 2255 =

11、2252641 = 641 (prime!)999 = 33337 = 33371024 = 2222222222 = 21013Prime Divisor TheoremIf n is a composite integer, then n has a prime divisor nProof: by definition of a composite integer, there are positive (1) integers a and b such that n = ab. Then a or b must be n because otherwise ab n. Lets ass

12、ume a n .By the Fundamental Theorem of Arithmetic, a is either a prime or product of primes, and each such prime is n 14ExampleShow that 101 is a primeSolution: Using Prime Divisor Theorem:The only primes 101 are 2, 3, 5, 7, but none of them divides 101. It follows that 101 is a primeExample: Find t

13、he prime factorization of 7007. Try 2, 3, 5, 7, (worst case 7007 83). But 7007/7 = 1001, 1001/7 =143 and 143/13. So, 7007 = 72 11 1315Infinite Primes TheoremThere are infinitely many primesBy contradiction. Assume there are finite number of primes, p1, p2, , pn. LetQ = p1 p2 pn + 1First of all, pj (

14、j = 1, , n) is not a factor of Q. Otherwise, pj can divide 1 = Q p1 p2 pn. By the Fundamental Theorem of Arithmetic, Q is a prime or product of primes. If Q is a prime, it is a contradiction. If it is a product of primes, the primes must be larger that any of p1, p2, , pn. Its also a contradiction16

15、The Largest Primes FoundPrimeNumber of decimal digitsTypeDateFound by257885161-1 17,425,170 Mersenne prime2013Great Internet Mersenne Prime Search19,249 213,018,586+ 13,918,990Proth number2007Seventeen or Bust150209!+1712,355factorial prime2011Domanov,PrimeGrid3756801695685 2666669 1200,700twin prim

16、es2011Twin prime search17Greatest Common DivisorsDefinition: Given integers a and b (not both zero). The greatest common divisor of a and b, denoted by gcd(a,b), is the largest integer d such that d | a and d | bExample: Find gcd(24,36)All divisors common to 24 and 36 are1, 2, 3 ,4 ,6 and 12. Hence,

17、 gcd(24,36) = 12Example: gcd(17,22) = 118Relative PrimesDefinition: Two integers a and b are relatively prime if gcd(a, b) = 1ExamplesAre 17 and 44 relatively prime?How about 17 and 51 ?19Least Common MultiplierDefinition: Given positive integers a and b. The least common multiple of a and b, denote

18、d by lcm(a, b), is the smallest positive integer d such that a | d and b | dExamplesa = 12, b = 8, lcm(12, 8) = 24a = 30, b = 15, lcm(30, 15) = 30a = 233572, b = 2433, lcm(a, b) = 243572a = 12, b = 7, lcm(12, 7) = 127 = 8420The Euclidean Algorithm for GCDTo find gcd(91, 287), divide 287 (the larger)

19、 by 91 (the smaller) to obtain the quotient and the remainder: 287 = 913 + 14 (i), or 287 913 = 14 (ii)Based on Theorem 1 of 4.1 (a | b a | c a | b + c)(ii): any divisor of 287 and 91 must be a divisor of 14So: (287, 91) and (91, 14) have the same common divisorsFinding gcd(287, 91) becomes finding gcd(91, 14).91 = 146 + 7 , finding gcd(14, 7) = 7 = gcd(287,91)21Lemma 1Given a =