Note 3 for MATH 300 at UMass
Note 3 for MATH 300 at UMass
Popular in Course
Popular in Department
This 6 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 15 views.
Reviews for Note 3 for MATH 300 at UMass
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
Math 300 Fall 2008 Note 3 Zhigang Han7 Umass at Amherst 1 Basic Number Theory 11 The Division Algorithm Def 1 Let 011 6 Z We say a divides I write alb7 if there exists q E Z such that b aq Rmk If no such q E Z exists7 we say a does not divide b7 and write a l b Rmk If a divides b7 we also say a is a factor of b7 or b is a multiple of a Eg 1 3 6 75 20 4 0 0 0 but 0l3 Eg 2 TRUE or FALSE 1 Vb e Z 3a 6 Z all ii 3b 6 Z Va 6 Z all iii Va 6 Z31 e Z all iv 3a 6 Z Vb e Z all Prop 1 Let a7 90 E Z i If all and blc7 then ale ii If all and ale then albm 0y for all 71 6 Z iii If all and bla7 then a ib iv lfalb and b 7 07 then lal Division Algorithm Let 011 6 Z and b 7 0 There exist unique q7 r E Z such that a qbr7 where 0g r lt Rmk q is called the quotient7 and r is called the remainder The re mainder r is always nonnegative Rink We often use the notation 3 for there exist unique The Division Algorithm can be written as Vab ZAb70 qu7T Z7 a qbrA0 rltlbl Rink We used in our proof the wellordering principle which states that any nonempty subset of N always contains a smallest element Eg 3 i If a 7401 12 then 740 74 12 8 with q 74 r 8 ii1fa 7751 711 then 775 7 711 2 with q 7 r 2 12 The Euclidean Algorithm Def 2 Let 071 E Z not both zero The greatest common divisor of a and b is the largest positive integer that divides both a and b It is denoted by gcdab We say 071 are relatively prime if gcda7 b 1 Rmk We de ne gcd07 0 0 Thus gcda7 0 lal for all a E Z Prop 2 If a qb r then gcda7 b gcdb7 r Euclidean Algorithm Let a and b be two nonzero integers7 and lal 2 If I f a7 then gcda7 b is the last nonzero remainder m in the following list of equations obtained from the Division Algorithm If b a7 then gcda7 b a q1br1 where 0ltr1lt b b q2T1r2 where Oltr2ltr1 T1 Q3T2 73 Where 0 lt r3 lt r2 m4 qnnkl m where 0 lt m lt m4 Tn71 qn1rn Rmk If a 07 then gcd0b Eg 4 Find gcd408187 GCD Characterization Theorem Let 1 be a nonnegative common di visor of a and I Then 1 gcda7 b if and only if there exist my 6 Z such that am by d Corollary gcdab 1 if and only if there exist my 6 Z such that am by 1 ii If d gcda b 7g 0 then gedg g 1 Prop 3 Let 11 0 E Z If 0 01 and gcdc7 a 17 then c b Extended Euclidean Algorithm Set the rst two rows as 10 a and 01b Think of a as T1 and b as r2 For i 2 3 Rowi Rowi72 7 qiRowi71 Here qi is the quotient when 3972 is divided by 3971 The algorithm stops when Tn1 0 Equation am 1 by r Row 1 1 0 a Row 2 0 1 b Row 3 x3 y3 T3 ROW 4 2 4 344 T4 Row 71 mn yn Tn Row 71 1 mn yn1 0 Conclusions i gcda b m ii Each row is a triple z y r satisfying the equation am 1 by r iii One integer solution to am 1 by gcda b is z zn y yn Eg 5 Use the Extended Euclidean Algorithm to nd gcd408 187 and to nd z y e Z such that 408x 187y gcd408 187 13 Prime Numbers Def 3 An integer 19 gt 1 is called a prime if its only positive factors are 1 and 19 otherwise it s called composite Rmk 1 is neither prime nor composite Prop 4 lf19 is prime and 19W7 then 19la or 19lb Unique Factorization Theorem Every integer larger than 1 can be expressed as a product of primes7 and the expression is unique up to the order of the factors Rmk This theorem is often referred to as the Fundamental Theorem of Arithmetic Rmk One can use strong mathematical induction or the method of con tradiction to prove the existence Euclid7s Theorem There are in nitely many primes Eg 6 Construct 100 consecutive composite numbers Prop 5 lfa 19111192 19 is the prime factorization of 017 then the positive divisors of a are those integers of form d 19 111193219ik7WhereOgdigaifori127k Corollary The number of positive divisors of a 19 11119219Zk is N 1 a11 a2 1 ak Theorem 1 If a 19311192 19 and b 191171191272 19 are prime factoriza tions of a and 197 where some exponents may be zero7 then 1 d d nga7b P111922 Pkkv where 11 mina1b1 for i 17 27 7k Corollary The number of positive common divisors of a 19111192 19 and b 1911711932ka is N 1 d11 d21 1k where d mina1 191 for i 1 2 k as above Rink Here and in the previous corollary we have used Multiplication Counting Principle Eg 5 How many positive divisors do 1000 and 420 have respectively How many positive common divisors do 1000 and 420 have Def 4 The least common multiple of two positive integers a and b is the smallest positive integer that is divisible by both a and b It is denoted by lcma 19 Theorem 2 If a 19311192 19 and b 191171191272 19 are prime factoriza tions of a and b where some exponents may be zero then lcma b 1911932 19k where 51 maxab for i 1 2 k Theorem 3 For any positive integers a and b we have gcdab lcmab ab Eg 7 a36 22x32 andb 24 23x31 Thengcdab 22x31 12 and lcmab 23 x 32 72 so gcdab lcmab 12 x 72 864 and ab 36 X 24 864
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'