ELEMENTARY STATISTICAL METHODS
ELEMENTARY STATISTICAL METHODS M 316
Popular in Course
verified elite notetaker
verified elite notetaker
verified elite notetaker
verified elite notetaker
verified elite notetaker
verified elite notetaker
Popular in Mathematics (M)
This 8 page Class Notes was uploaded by Reyes Glover on Sunday September 6, 2015. The Class Notes belongs to M 316 at University of Texas at Austin taught by Staff in Fall. Since its upload, it has received 16 views. For similar materials see /class/181491/m-316-university-of-texas-at-austin in Mathematics (M) at University of Texas at Austin.
Reviews for ELEMENTARY STATISTICAL METHODS
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: 09/06/15
M316K 7 Foundations of Arithmetic Spring 2009 Some Notes on Number Theory I Divisibility One of the main areas of study in number theory deals with divisibility that is the question of whether one integer is divisible by another For integers a and nonzero we say that a is divisible by d if dividing a by d yields an integer result For whole numbers a and d to say that a is divisible by d means that you can divide a things equally into d groups this is probably where the word divisible comes from We have several different ways of saying that a is divisible by d 0 We say that d is a divisor of a 1n the relationship between a and d the number a is being divided and the number d is doing the dividing 0 We say that d is a factor of a You7re familiar with the idea of factoring a number into primes in the equation 35 5 7 5 and 7 are factors of 35 0 We say that a is a multiple of d This is because we can obtain a by multiplying d by an integer m this relationship can be expressed with the equation a d in Note that this is equivalent to ad 0 We use the notation dla pronounced d divides a The order is very important here Remember in the relationship between a and d it is d that is doing the dividing and a that is being divided So it is correct to say that 3 divides 15 in other words you can divide 15 evenly by 3 but not that 15 divides 3 Usually the most straightforward way to determine whether a number a is divisible by a number d is to simply try dividing a by d and see whether you get a remainder If you get a remainder of zero then d is a divisor of a if your remainder is nonzero then d doesnlt divide a Some potential divisors have special divisibility tests 0 1 Every whole number is divisible by 1 o 2 A whole number is divisible by 2 if and only if its ones digit is divisible by 2 Example 4896 is divisible by 2 because its ones digit 6 is even 0 3 A whole number is divisible by 3 if and only if the sum of its digits is divisible by 3 Example 576 is divisible by 3 because the sum of its digits 5 7 6 18 is divisible by 3 If you re not convinced that 18 is divisible by 3 run the test on 18 18 is divisible by 3 because the sum of its digits 1 8 9 is divisible by 3 o 4 A whole number is divisible by 4 if and only if the twodigit number consisting of its tens and ones digits is divisible by 4 Example 824 is divisible by 4 because 24 is divisible by 4 o 5 A whole number is divisible by 5 if and only if its ones digit is divisible by 5 o 6 A whole number is divisible by 6 if and only if it is divisible by both 2 and 3 o 8 A whole number is divisible by 8 if and only if the threedigit number consisting of its last three digits is divisible by 8 o 9 A whole number is divisible by 9 if and only if the sum of its digits is divisible by 9 o 10 A whole number is divisible by 10 if and only if its ones digit is 0 o 11 A whole number is divisible by 11 if and only if its alternating digit sum is divisible by 11 Example 4917 is divisible by 11 because its alternating digit sum 4 7 9 1 7 7 711 is divisible by 11 Each of these divisibility tests comes as a result of our working in a baseten system Note that divisibility tests where you knock off all but the last few digits 2 4 5 8 all bear a special relationship to the number 10 PH leave you to think about how that relationship can be summed up Divisibility tests where you add up the digits 3 9 all bear a special relationship to the number 10 7 1 or 9 Divisibility tests where you take the alternating digit sum 11 all bear a special relationship to the number 10 1 or 11 Based on this information can you guess what the divisibility tests would be in base 16 How about base 20 Can you think of a base in which there is a divisibility test for 7 Prime numbers A prime number is a number that has exactly two divisors 1 and itself Note that the exactly two divisors part is important it means that 1 is not a prime number even though it is divisible only by 1 and itself The reason we don7t consider the number 1 a prime that is the reason we insist that the de nition of prime should include the exactly two divisors clause is structural not historic in other words it s not a matter of conventioni To give you an idea of the reason we tend to classify numbers as prime composite or other 1 is other based on their multiplicative properties The prime numbers and composite numbers all integers greater than 1 don7t have multiplicative inverses in the set of integers but the number 1 does its inverse is 1 So rather than calling 1 a prime or a composite number we call it a unit A composite number is a number that has more than two divisors that is that has divisors other than 1 and itself Put differently a counting number n is composite if and only if it can be expressed in the form n a b where both a and b are less than n How do we tell whether a number is prime or composite Depending on how you look at this question it can be either ridiculously easy or ridiculously hard The easy answer is that you can determine whether a number is prime this process is called primality testing by checking all the counting numbers between 1 and the number and seeing if any of them are divisorsi However this process takes an excruciatingly long time and that s the hard part of the question 7 how do we perform this task more ef ciently Believe it or not this question is still of great interest to mathematicians and computer scientists who rely on primality testing 7 and on the dif culty of primality testing 7 to send information securely over computer networks 1 Much progress has been made on this question including some very signi cant progress that has been made in the last ten years but for purposes of this class welll just focus on one algorithm that is still fairly inef cient To determine whether a number n is prime check n for divisibility by prime numbers less than or equal to If n is divisible by any of these prime numbers then n is composite as you should know from the de nition If n isn7t divisible by any of these primes then n itself is prime Example Suppose we want to determine whether 233 is prime you found out that it is on a re cent problem set We know that m m 16 so its enough for us to check whether 233 is divisible by any prime number less than or equal to 16 We can use divisibility tests to see easily that 233 isn7t divisible by 2 3 or 5 If we try dividing 233 by 7 we get a remainder of 2 so 7 isn7t a divisori Neither is 11 the remainder is also 2 or 13 the remainder is 12 These are all of the primes less than 16 so we can now say with complete con dence that 233 is prime Example Many of you incorrectly said on the problem set that 817 is prime because you checked for divisiblity by 2 3 5 and 7 or you checked for divisibility by any number less than 10 That s a good start but since m m 29 we need to check for prime factors up to and including 29 If we keep testing we7ll see that 11 13 and 17 are not divisors but 19 is By dividing 817 by 19 we see that 817 19 43 How is it that we can know so much about n just by checking potential divisors up to 5 We can demonstrate or prove this using the following argument Suppose that n is compositei Then n must factor as a product of two smaller numbers a and b We can assume that a is less than or equal to b by switching the roles of a and b if necessary Then we must have a S 5 because otherwise we would have 5 lt a S b and this would mean that n a b gt 5 n Compressing that last inequality we get n gt n which is plainly ridiculousi So we must have a S 5 and a has a prime factor p because a isn7t 1 and every natural number greater than 1 has a prime factor That prime factor p must be less than or equal to a So p is a factor of a and a is a factor of n this means that p is a factor of n and because p S a S 5 we have p S So if n is composite then n must have a prime factor less than or equal to This means that if there is no such prime factor n must be primer Don7t feel bad if you didn t follow the above argument students typically learn to follow arguments like these when they train to be mathematicians The key to following an argument like this is to try to link it to something that you know in your case the best thing to use is concrete numerical examples So consider the number 73 We know that m is between 8 whose square is 64 and 9 whose square is 81 So if 73 factors as a product of two smaller numbers then one of those numbers must be less than 9 After all the alternative is for both numbers to be 9 or greater in which case their product will be at least 9 9 or 81 which is bigger than 73 So if 73 is composite it has to have a factor that is greater than 1 but less than 9 But if there is such a factor then we can also nd a prime factor If 73 were divisible by a composite number like 6 obviously 73 isn7t divisible by 6 but play along for the moment then we could observe that 6 has a prime 2 as a factor and so 2 is also a factor of 73 So if we just look for prime factors we re doing enough work to detect any proper divisors 73 might have At this point 1 would ask How many of you now understand this argument better than when 1 used variables77 And about ve of you would raise your hands and 1 would ask if there are any questions and there wouldnlt be any So the rest of you if you want to understand this argument better can talk to me after class or during of ce hours Its not essential for you to be able to write a mathematical proof like the one above the one with variables but 17d like for you to understand the ideas If you don7t understand them then when you do the squareroot trick to check for primality you re just doing what everybody else does which is the sort of behavior that keeps math from making sense If you want to nd a lot of prime numbers 7 say all of them 7 one trick you can use is the sieve 0f Emtosthenesi Bassarear explains the process pretty well so I won t say much about it here but the idea is that you write down all the numbers from 1 to N you pick the value of N depending on how many prime numbers you want to nd and identify the number 2 as prime You then eliminate all the multiples of that prime greater than 2 because those multiples are composite You then identify the rst number that hasn7t been eliminated 7 name y 3 7 and observe that it is prime because if it were composite it would have had a prime factor by our argument above and thus would have been eliminated at a previous stage of the process We then identify 3 as prime and eliminate all other multiples of 3 We continue this process at each step identifying the rst noneliminated number as prime because if it were composite it would have been eliminated already and eliminating all other multiples of that primer See the visual in the book which is much better for most of you at least than a wordy explanation The ancient Greek mathematician Euclid proved that there are in nitely many prime numbers in other words if you were to write all the prime numbers in a list the list would go on forever The proof is wonderfully clever the idea is to assume the opposite 7 that the list would end somewhere giving you a nite list of prime numbers 7 and multiply all of those prime numbers and add one to the product This gives you a number that isn7t divisible by any of the prime numbers in your list because the remainder when you divide your new number by any of those primes would be 1 But your number has to have a prime factor which wouldnlt be on the list or be prime itself and certainly not on the list because we got it by multiplying everything on the list and adding one Thatls a contradiction and when we get a contradiction in mathematics it means we7ve assumed something that is wrong Here the wrong assumption we made is that the list of primes doesn7t go on forever As simple as prime numbers seem to be we don7t know nearly as much as weld like to know about III them and by we I don7t mean our class I mean mankindi Here are some things we donlt know about prime numbers 0 Is there a largest pair of twin primes or do pairs of twin primes go on forever Twin primes are pairs of primes that are 2 apart such as 3 and 5 5 and 7 11 and 13 and 17 and 19 Is there an even number greater than 4 that cannot be written as a sum of two prime numbers Try this for any even number less than 200 or so for example 152 7379i Mathematicians have computertested approximately 1018 even numbers and every single one so far has been expressible as a sum of two primesi And yet we don7t know of a really good reason why it should always be possible to do this When you look at the integers as a whole prime numbers are relatively scarce so there isn7t any immediate way to see that every even number can be expressed as a sum of two primesi Prime factorization Prime factorization is the most important topic in this chapter because of the immense power that comes from knowing a number7s prime factorization But before we explore that power let s recall what a prime factorization is A prime factorization of an integer n is a way of writing n as a prod uct of prime numbers some of which may be repeated For example a prime factorization of 78 is 78 2 3 13 A prime factorization of 300 is 300 22 35 5 which we often write as 300 22 35 You may nd it strange that I used the phrase a prime factorization when I and most other people usually say the prime factorization The reason I used the phrase a prime factorization is that for all we know before we learn number theory a number could have several different prime factorizationsi Perhaps there is a number out there that has 3 72 13 as a prime factorization but also has 5 112 as a prime factorizationi You should be able to tell without much work that those aren7t the same number and I7m just making things up It turns out that you don7t have to worry about this sort of thing One of the greatest things about prime factorizations is that the prime factorization of a number is unique that is if Sakeenah and Tina both nd prime factorizations of the same number they should get the same prime factorization assuming that both factorizations are correct Sakeenah7s primes might be in a different order than Tina7s but there shouldnlt be any essential difference between the two factorizationsi This fact is called the Fundamental Theorem of Arithmetic In practice we nd the prime factorization of a number using a factor tree I won7t do any ex amples of that here because you can nd them in the book and the vast majority of you can already do them quite well anywayi Divisor counting Now that we have prime factorizations in our toolbox let s take a look at some of the wondrous things we can do with themi Welll start with the task of counting the divisors of a positive integer In this chapter and in these notes when we say divisor we mean positive divisori In number theory negative numbers are allowed to be divisors as well because after all one can certainly get an integer by dividing an integer by a negative integer i Example Suppose we want to nd out how many divisors the number 72 23 32 has There are several ways to do this from completely unsophisticated to slicker than a used car salesmani The completely unsophisticated approach is to haphazardly guess numbers and hope that in the process you nd all the divisorsi Once you get tired of doing that which hopefully doesnlt take too long you start to notice that the divisors of 72 come in pairs 72172 72236 72324 72418 72612 7289 This pairing allows us to count the divisors of 72 more quickly If we start at 1 and identify the divisors in increasing order once we reach a divisor that is the partner of a divisor we7ve already found we can count all the divisors we7ve already found prior to discovering the partner and multiply that count by 2 In this case weld keep going until we found 9 which is the partner of 8 By this time we7ve found six divisors between 1 and 8 inclusive so 72 has twice this many twelve divisors A word of caution though some numbers have divisors which are their own partners which numbers are these and in these cases you won7t be able to get the number of divisors by multiplying your count by two Once you get tired of doing that it s time to nd a much better way to handle problems like these One useful thing to do is to think about the divisors of 72 and their prime factorizations Each divisor of 72 is a combination via multiplication of 27s and 37s 7 the same numbers that appear in the prime factorization of 72 itself We can arrange the divisors of 72 in a table according to how many 27s and how many 37s each divisor has This table gives us much more insight about relationships between the divisors of 72 than a simple list would For example we notice that in many cases we can obtain a divisor of 72 by multiplying another divisor by 2 or 3 You may also nd it useful to try answering the following questions 0 Which divisors of 72 are odd Where are they in the table 0 Which divisors of 72 are not divisible by 3 o For a given divisor of 72 in the table where can you nd its partner 0 Which divisors of 72 are perfect squares Where are they in the table But the question we7re most interested in right now is How many divisors does 72 have From the table it is readily apparent that there are 12 but notice that this 12 arises in a nice natural way The table has four columns because there are four different powers of 2 we can use 20 21 22 and 23 and three rows because there are three different powers of 3 we can use 30 31 and 32 Because we need to choose a power of two and a power of three we have a total of 4 X 3 l2 choices Which model of multiplication are we using here Example Letls suppose we want to count the divisors of a much larger number such as 513 114 17 Good luck calculating this by hand let alone counting the divisors using the huntand peck methodl Then we know that there are 0 l4 powers of 5 we can use 50 51 52 512 513 notice that the 50 is important because we can choose divisors that are not divisible by 5 o 5 powers of 11 we can use 110111112113 and 114 o 2 powers of 17 we can use 170 171 Since we must choose one of each the number of divisors of 513 114 17 is 14 X 5 X 2 140 Again not something you would have been likely to nd by simply making a list Here are some questions you d do well to try to answer 0 How many divisors of 513 114 17 are less than 100 o How many divisors of 513 114 17 are perfect squares o How many divisors of 513 114 17 have ones digit 5 V Greatest common factors Least common multiples One reason we cover the basic principles of number theory in this course is that we use the ideas of GCF greatest common factor and LCM least common multiple when performing operations with fractions Of course even if these ideas weren t useful when we deal with fractions they d still be worth learning in their own right obviously but the fact that fraction operations rely on these ideas makes this discussion even more worthw i e First let s de ne the GCF and LCM of two numbers For two whole numbers a and b not both zero the greatest common factor or GCF of a and b is the greatest whole number d such that dla and dlbi For those of you who don7t like symbols so much another way to say this is that the GCF is the largest number that is a factor of both a and 121 Note Every mathematician I know of calls this the GCD l don7t know why Bassarear sticks with the name GCF unless maybe the word factor is more popular than the word divisor in mathematics education For two positive integers a and b the least common multiple or LCM of a and b is the smallest positive integer m such that alm and blmi Again to recast it for those who are allergic to symbols m is the smallest positive integer that is divisible by both a and 121 Note the contrast with the de nition of GCFi Notice that l7m requiring m to be a positive integer this is important If you were just looking for any old common multiple of a and b the number 0 would always work because 0 is a multiple of everything But we don7t consider that the least common multiple because for the tasks we use the LCM for an answer of 0 while not necessarily wrong typically isn7t that useful Think back to the Exploration in which you used the LCM to determine the next time two people on different ferris wheels would both meet at the bottom it would be silly though not really incorrect to say that the two people would meet again 0 seconds from nowi And besides that it wouldn7t give you the next time Again there are several methods for nding the GCF and LCM of two numbers at varying levels of sophistication We7ll illustrate these with an example Example Suppose we want to nd the GCF and LCM of 24 and 401 Welll start with the GCF Since we re looking for the greatest common factor of 24 and 40 one way to get at this is to list all the divisors of 24 and 40 and identify those that are common to bot Divisors of 24 1 2 3 4 6 8 12 24 Divisors of 40 1 2 4 5 8 10 20 40 I identi ed the common factors by bolding them you ll probably want to use a convention that is easier to do with paper and pencil such as circlingi Anyway you can easily see here that the greatest common factor or GCF is 81 What about the LCM We can try using the same sort of technique to nd the LCM but its a bit tricky since we can7t list all the multiples of 24 or 40 these go on forever Still since we7re just looking for the rst positive common multiple on our list we can try listing a few multiples of each and hope we nd a common one Multiples of 24 24 48 72 96 120144 168 192 216 240 Multiples of 40 40 80 120 160 200 240 280 320 360 400 Ahal We nd that the number 120 is the rst number to appear on both lists so 120 is the LCM1 Notice that l bolded 360 a multiple of 40 even though it doesn7t appear to be on the rst list If we continued the rst list far enough we7d see that 360 actually is on the list Of course even if we hadn t caught this we still would have correctly identi ed 120 as the LCMi The problem with these methods is that listing things out in this way is a tedious timeconsuming process Furthermore if you make an error say in calculating multiples of a number which I did by counting up by the appropriate amount you may end up never nding a common multiplei So lets see if we can use prime factorizations to make our job easier We have 24 23 3 and 40 23 5 so keep that in mind as we procee Lets start by nding the GCF of 24 and 40 We know that if d is a common factor of 24 and 40 then d can t have a 3 in its prime factorization because 40 is not divisible by 3 Also d can7t have a 5 in its prime factorization because 24 is not divisible by 5 Of course d can7t have any larger primes like 7 11 or 13 in its prime factorization because neither 24 nor 40 is divisible by any of these So the only prime number d can have in its prime factorization is 2 But we do know that d can have up to three copies of the number 2 in its prime factorization because both 24 and 40 have three copies of 2 in their prime factorizations So the largest common divisor we can come up with is the product of three copies of 2 and no other primes Thatls 23 or 8 What about the LCM If m is to be a multiple of both 24 and 40 then m must have the prime factors 2 3 and 5 in its prime factorization This is because in order for m to be divisible by 24 it must be divisible by 2 and 3 and for it to be divisible by 40 it must be divisible by 2 and 5 But we have to do a bit better notice that if we want m to be divisible by 24 we actually need the prime factorization of m to contain three copies of 2 not just one The same goes for 40 which also contains three copies of 2 in its prime factorization So m needs to have three copies of 2 a 3 and a 5 So m must be at least 23 3 5 120 We can check that 120 is indeed divisible by both 24 and 40 we7ve already done this using our lists above this means that 120 is the least common multiple This method of using prime factorizations is so powerful that it s worth trying out on a couple more examples Example Let7s nd the GCF and LCM of 900 and 750 If we nd the prime factorizations of 900 and 750 you should do this on your ownl we get 900 22 32 52 and 750 2 3 53 If d is a number that divides both 900 and 750 then d must contain only the primes 2 3 and 5 which are common to 900 and 750 How many copies of each prime factor can d contain lf d has more than one 2 then it won t be a factor of 750 which has only one copy of 2 in its prime factorization So d can only have one 2 For the same reason d can only have one 3 However d can have two 57s since both 900 and 750 have at least this many lt can7t have three though because 900 only has two So the GCF of 900 and 750 is 2 3 52 150i What about the LCM If m is to be divisible by both 900 and 750 then m needs to have at least two 27s since 900 has this many at least two 37s since 900 has this many and at least three 57s since 750 has this many So the LCM of 900 and 750 is 22 32 53 4500 Example Lets do one more example and nd the GCF and LCM of 33 and 35 The prime fac torizations of these numbers are 33 3 11 and 35 5 7 First we7ll nd the GCFi lf d divides both 33 and 35 then d can only have HiHey wait a minute There isn7t a single prime that d can have in its prime factorization because there are no prime factors common to 33 and 35 This means that d must have no factors in its prime factorizationl If a positive integer doesn7t have any prime factors that means its the number 1 you can see for yourself that 1 has no prime factors So the GCF of 33 and 35 is 1 You can see this in this particular example by just listing divisors aka the brute force method but make sure you understand what it means when the prime factorizations have nothing in common this is important Now lets nd the LCM If m is divisible by both 33 and 35 then m must have a 3 an 11 a 5 and a 7 in its prime factorization it only needs one of each So the least common multiple of 33 and 35is357111155i There is one more method for nding the GCF of two numbers and it s called the Euclidean algo rithmi It was discovered along with most basic results in number theory by Euclid and what is really remarkable about this method is that it remains the most ef cient way within classical number theory at least to nd the GCF of two numbers The great strength of this method is that you don7t have to know the prime factorizations of your two numbers in order to use it This is especially important with larger numbers because we 7 and again 1 mean mankind not this class 7 dont ave an ef cient way to nd prime factorizations of very large numbers 17m not going to give a stepbystep explanation of the method because 1 think the better way to show you how to use it is to do an example llll use the algorithm to nd the GCF of 374 and 527 PH start by dividing the larger number by the smaller watch what 1 do after that 527 7 374 is 1 with a remainder of 153 374 7153 is 2 with a remainder of 68 153 7 68 is 2 with a remainder of 17 68 7 17 is 4 with a remainder of 0 At this point since 1 have a remainder of zero 1 stop the process The last nonzero remainder 1 get 7 17 in this case 7 is the GCF of the two numbers Pretty cool huh In case you re wondering what 1 did with the quotients 1 got 7 1 2 2 4 7 the answer is Nothing They don7t matter here We can also use the GCF of two numbers to nd the LCM using the following theorem Theorem For two positive integers a and b we have a b GCFa b LCMabi Example The LCM of 527 and 374 satis es the equation 527 374 GCF527 374 LCM527374i We know that the GCF is 17 so we have 527 374 17 LCM527374i Notice 17m hesitant to multiply the numbers on the left that s because 1 don7t have to So the LCM is 527 37417 115941 Donlt worry the numbers on the test won t be that big If you want to know why this theorem works think about the prime factorizations of a and I looking at the examples we did might be helpful and the prime factorizations of the GCF and LCMi Compare the rst pair of prime factorizations a and b with the second pair the GCF and LCM And if you want to know more as always come visit me in my of ce 17d love to talk to you about it if you don7t show up llll probably just be sitting around looking at lolcats or something 1 can haz of ce hrz
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'