1、Chapter 4:Number TheoryElements of Discrete Structures1Intro to Integers and Division A branch of mathematics is called Number Theory It involves integers and their properties Basic concept of number theory is used through out computer science We 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 a When a divides b,we say a is a factor of b and that b is a multiple of a We use a|b to denote a divides bWe use a b to
3、 denote a does not divides b3Example Let 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 n So,from kd n,we know k n/d.We conclude that there are n/d positive integers n that are divisible by d When n=11,d=3,11/3=3.
4、The positive integers that are divisible by 3 are 3,6,and 94Theorem 1Theorem 1:Let a,b and c Z:1)If a|b and a|c,then a|(b+c)2)If a|b then a|bc for all c Z3)If 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+e is an integer.By definition,a divides b+c5The
5、 Division Algorithm Theorem 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 the quotient,and r the remainder.q=a div d r=a mod d(a modulo
6、 d)(Be used very often)6The Division Algorithm Division Algorithm Examples:1)11 div 3=3;11 mod 3=2;Or 11=33+22)-11 div 3=-4;-11 mod 3=1;Or-11=3(-4)+13)12 div 3=4;12 mod 3=0;Or 3 divides 12,or 3|124)“a divides b”is equivalent to“b mod a=0”7Modular Arithmetic Definition:Given two integers a and b,and
7、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 the Division Theorem,let a=mq1+r1 and b=mq2+r28Modular Arithmetic Proof of Theorem 3:IF:if(a mod m)=(b mod m
8、)(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 Arithmetic Proof of Theorem 3:ONLY-IF: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 pri
9、me if the only positive factors of p are 1 and p Definition:a positive integer 1 that is not prime is called composite Primes less than 100 are2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,71,73,79,83,89,9712The Fundamental Theorem of Arithmetic Every positive integer can be written uniquely as
10、a prime or the product of primes(in nondecreasing order)(Proof by Induction will be provided in Chapter 5)Examples100=2255=2252641=641(prime!)999=33337=33371024=2222222222=21013Prime Divisor Theorem If n is a composite integer,then n has a prime divisor n Proof:by definition of a composite integer,t
11、here are positive(1)integers a and b such that n=ab.Then a or b must be n because otherwise ab n.Lets assume a n.By the Fundamental Theorem of Arithmetic,a is either a prime or product of primes,and each such prime is n 14Example Show that 101 is a prime Solution:Using Prime Divisor Theorem:The only
12、 primes 101 are 2,3,5,7,but none of them divides 101.It follows that 101 is a prime Example:Find the 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 Theorem There are infinitely many primes By contradiction.Assume t
13、here are finite number of primes,p1,p2,pn.LetQ=p1 p2 pn+1First of all,pj(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 la
14、rger that any of p1,p2,pn.Its also a contradiction16The Largest Primes FoundPrimeNumber of decimal digitsTypeDateFound by257885161-1 17,425,170 Mersenne prime 2013Great Internet Mersenne Prime Search19,249 213,018,586+13,918,990Proth number2007Seventeen or Bust150209!+1712,355factorial prime2011Doma
15、nov,PrimeGrid3756801695685 2666669 1200,700twin primes2011Twin prime search17Greatest Common Divisors Definition: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|b Example:Find gcd(24,36)All divisors common
16、to 24 and 36 are1,2,3,4,6 and 12.Hence,gcd(24,36)=12 Example:gcd(17,22)=118Relative Primes Definition:Two integers a and b are relatively prime if gcd(a,b)=1 ExamplesAre 17 and 44 relatively prime?How about 17 and 51?19Least Common Multiplier Definition:Given positive integers a and b.The least comm
17、on multiple of a and b,denoted by lcm(a,b),is the smallest positive integer d such that a|d and b|d Examplesa=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 GCD To find gcd(91,287),divide 287(the larger)by 91(the smalle
18、r)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 14 So:(287,91)and(91,14)have the same common divisors Finding gcd(287,91)becomes finding gcd(91,14).91=146+7,finding gcd(14,7)=7=gcd(2
19、87,91)21Lemma 1 Given a=bq+r,where a,b,q,and r 0 are integers.Then gcd(a,b)=gcd(b,r)Example:find gcd(414,662)662=4141+248 414=2481+166 248=1661+82 166=822+2(last nonzero remainder=2)82=241+0 2 0 gcd(414,662)=gcd(82,2)=222Algorithm 6 Euclidean Algorithmprocedure gcd(a,b:positive integers)x:=ay:=bwhile y 0 begin r:=x mod y x:=y y:=rend gcd(a,b)is x when y=r=0(Try example gcd(9,6)=gcd(?,?)=)23Exercises#6 P229:2,4,8,13,34 P244:3,4,9a-d,15,16,20,29 P272:3d-f,25a-c,26(for 25a-c),33b-c,34 Finish before midterm exam.Come to my Q&A time for questions!Turn in the week after the midterm24
