Joe Fields (disambiguation)

Transcription

How did you get on with assignment eight? Though the focus of this course is a particular kind of thinking, rather than any specific mathematics. The integers and the real numbers provide convenient mathematical domains to illustrate mathematical proofs. Those domains are number theory and elementary real analysis. The principle advantage is example domains is that everyone has some familiarity with both systems. Yet, very likely, you won't have been exposed to their mathematical theories. I'll take the integers first. Most people's experience with the whole numbers is by elementary arithmetic. Yet the mathematical study of the integers, looking beyond mere calculation to the abstract properties those numbers exhibit goes back to the very beginnings of recognizable modern mathematics around 700 B.C.E. That study has gone into one of the most important branches of pure mathematics, number theory. Most college mathematics majors find that number theory is one of the most fascinating courses they take. Not only is the subject full of tantalizing problems that are easy to state, but require great ingenuity to solve, if indeed they have been solved, and many haven't, but some of the results turn out to have applications crucial to modern life, internet security being, arguably, one of the most important. Unfortunately we'll barely scratch the surface of number theory in this course. But if anything you see in this lecture arouses your curiosity. I would recommend that you look further. You're unlikely to be disappointed. The mathematical interest in the integers lies not in their use in counting but in their arithmetical system. Given any two integers, you can add them, subtract one from the other, or multiply them together, and the result will always be another integer. Division's not so straightforward, and that's where things get particularly interesting. For some pairs of integers, say five and fifteen, division is possible. Fifteen divides by five to give the integer result three. For other pairs, say seve n and fifteen, division is not possible, unless you're prepared to allow fractional results, which takes you outside the integers. Is you restrict arithmetic to the integers, division actually leads to two numbers, a quotient and a remainder. For example, if you divide nine by four, you get a quotient of two, and a remainder of one. Nine equal four times two plus one. This is a special case of our first formal theorem concerning integers, the division theorem. The division theorem says the following. That ABB integers with B greater than zero. Then of our unique integers Q and R. So it's that A equals Q, B, plus R, and zero less than or equal to R, less than B. Well there are two parts to this theorem. As an existence path there are integers with this property. And there's a uniqueness part. Those integers are unique with this property. In proving the theorem, we're going to take those one at a time. I'll first prove existence and then I'll prove uniqueness. So the proof as always, it's a good idea to begin a proof by stating the method you are going to adopt. In this case, what I'll say is I am going to prove existence first. Then uniqueness. I'm not using any standard method, so I'm not able to state that I'm using something like induction or whatever. But it will orientate the reader to say that the first part of the proof will deal with existence and the second part will deal with uniqueness. Okay so we're going to handle existence. Well, look at all non-negative integers of the form a minus kb, where k is an integer, and ensure that one of them is less than b. What the theorem says. Is that among the integers A minus QB, namely the integers R, there is one with R between zero and B. So I'm going to look at all possible candidates for A minus KB, or A minus QB, if you like and I am going to show that among those candidates one of them satisfies that condition. And the k for which it satisfies that condition will be the q that I'll take for the third. Well first of all, I need to show that there are suc h integers . For example take k = negative absolute value of a then, since B is greater than or equal to one. A-kb= A + absolute value of A B, which is greater than or = to A + absolute value of A. Which, in turn, is greater than or = to zero. Well, having shown that there are such integers, by producing a K that gives me such an integer I can choose the smallest one. Let R be the smallest such integer and let Q be the value of K for which it occurs i.e. We'll have R equals A minus QB. So with R and Q divided in this way, I will indeed have a equals q b plus r. If I can show that R lies between zero and B in this fashion, then I'll have proved existence. So to complete the proof we show that r is less than b. Well, suppose, on the contrary, that R is greater than or equal to B. In other words I'm now going to use proof by contradiction to show that R is less than B. Well if r is greater than or equal to b, then A minus Q plus one B, equals A minus Q B minus B, which equals R minus B, which is greater or equal to zero by virtue of this assumption. Thus A-Q+1B is a non negative integer of the form A-KB. But R is the smallest such. And yet A-Q+1B is less than A-QB which is R and that's a contradiction. If r is the smallest such we can't find a smaller one. There's a contradiction. Hence R is less than B because we obtain that contradiction on the assumption that R is greater or equal to B. And that proves existence. If you haven't seen a proof like this before, it almost certainly looks very complicated. It's actually not complicated or deep, it's just intricate in its structure. The idea is to look at all, at all of the possible candidates, to make this true. Well first of all, we have to show there is a possible candidate. And we actually do that by exhibiting one. And then, to get a candidate which satisfies these, these additional requirements, we pick the one where the R is the smallest, it's the minimal value of R that gives us one of these things. And then we use the fact that it's minimal in order to show that it has to swa-, has to satisfy this requirement. Each individual step is just elementary algebra, it's just somewhat intricate to push the argument through. There's a lot of arguments in mathematics like this. There's no deep mathematics involved, there's nothing more than elementary arithmetic and a little bit of algebra but there's a bit of intricate structure, to make the proof work. So if you haven't seen this kind of argument before it'll probably take you several reads through, you, you'll need to look at it several times before it begins to make sense. Okay? Well that proves existence. Then we need to turn to uniqueness. To prove uniqueness, we assure that if there are two representations of A, A equals QB plus R, and A equals Q prime B plus R prime, with zero less than or equal to R, and R prime less than B, then R equals R prime and Q equals Q prime. So, the first part of the division theorem, the existence part that we've already proved, shows that there are representations of this form. What we now are doing is showing that if there were two such representations, then, in fact, they're identical. The, the R is the same and the Q is the same. Incidentally you probably realize by now that the, the letter Q is going to denote quotient and the letter R is going to denote remainder. We haven't officially defined quotient and remainder yet, so I haven't written anything like that down, but I'm using the, the familiar notation because what we're doing is we're giving the mathematical underpinnings of the familiar knowledge that you probably have about, about arithmetic, dividing one until you buy another. Okay, so we have an equation here. Q B plus R equals Q prime B plus R prime. Let's rearrange it, rearranging, I get R prime minus R equals B into Q minus Q prime. And I've labeled that equation one for later reference. Now, I'm going to take absolute values in this equation, and when I do that, I get absolute value R prime minus R, equals B, times absolute value of Q minus Q prime. Which I've l abeled equation tw o. B is positive, remember. So when you take absolute values, B remains the same. But negative B is less than negative R which is less than or equal to zero. And zero is less than or equal to R prime which is less than B so negative B is less than R prime minus R, is less than B. Well, if R prime minus R is between negative B and plus B, that means, that the absolute value of R prime minus R, is less than B. So by 2B times absolute value of Q minus Q prime is less than B. I can divide by B now to give me absolute value of Q minus Q prime is less than one. But everything here is an integer, and the only way you can have a pair of integers. The absolute value of the difference between them being less than one, is that their absolute value is zero. Which means Q has to equal Q prime. And then by equation one. After we've got r prime. Then that proves uniqueness. And with it, we've proved the division theorem. Again, if you haven't seen arguments like this before, it's going to seem, pretty daunting, but when you go through it step by step, this is really just very basic arithmetic, arguments with inequalities. Take it step by step and you should be able to follow the arguments through, right through to the end. Okay, good luck with that. If this is the first full blown rigorous proof of a theorem like this that you have encountered, you probably need to spend some time going over it. The result itself isn't deep. It's something we're all familiar with. Our focus here is on the method we use to prove conclusively that the division property is true for all pairs of integers. Time spent now making sure you understand how this proof works, why every step was critical will pay dividends later on when you encounter more difficult proofs. By gaining experience with mathematical proofs of simple results like this one, which is obvious, mathematicians become confident in the method of proof, and can accept results that are not at all obvious. For an example of a result that's not obvious, in the late nineteenth century, the famous German mathematician David Hilbert, described a hypothetical hotel, that has a strange property. Hilbert's Hotel as it's become known is the ultimate hotel. And it has infinitely many rooms. As in most hotels the rooms are numbered using the natural numbers. One two three etcetera. One night all rooms are occupied when an additional guest turns up. I'm sorry, says the desk clerk, all our rooms are occupied. You'll have to go somewhere else. The guest, a mathematician, thinks for a while before saying, there is a way you can give me a room, without having to eject any of your existing guests. Before I proceed with the story. You might like to stop the video for a moment and see if you can see the solution the mathematician guest has seen. The clerk is skeptical, but he asks the mathematician to explain, how he can free up a room, without ejecting anybody already in the hotel. Right? Simple, the mathematician begins. You move everybody into the next room. So the occupants of room one moves into room two, the occupant of room two moves into room three, and so on throughout the hotel. In general the occupants of room N moves into room N+1. When you have done that room one is empty. You put me in that room. The clerk thinks about it for a moment and then has to agree that the method will work. It is indeed possible to accommodate an additional guest in a completely full hotel without having to eject anyone. The mathematician's reasoning is totally sound, and so the mathematician gets a room for the night. The key to the Hilbert Hotel argument is that the hotel has infinitely many rooms. Indeed, Hilbert formulated the story to illustrate one of the several surprising properties of infinity. You should think about the above argument for a while. You won't learn anything new about real world hotels, but you will come to understand infinity a bit better. And the significance of understanding infinity, is that it's the key to calculus, the bedrock of modern science and engineering. And when you're satisfied you un derstand Hilbert's solution, try the following variants. First variant, the Hilbert Hotel scenario is as before but this time two guests arrive at the already full hotel. How can they be accommodated? In seperate rooms I should add, without anyone having to be ejected. Second variant. This time the desk clerk faces an even worse headache. The hotel is full, but an infinite tour group arrives, each group member wearing a badge that says, hello, I am n. For each of the natural numbers, n equals one, two, three, et cetera. Can the clerk find a way to give all the new guests a room to themselves, without having to eject any of the existing guests? And if so, how? Examples like the Hillburt Hotel demonstrate the importance of rigorous proofs in mathematics. When used to verify obvious results like the division theorem, they may seem frivolous. But when the same method is applied to issues we are not familiar with, such as questions that involve infinity, rigorous proofs are the only thing we can rely on. Now back to the division theorem. Well, the way I've stated the division theorem, it only applies to division by a positive integer B. There's a more general version that I'll give you now. So, theorem, general division theorem, let ABB integers with B non zero. Then there are unique integers Q and R. So it's, so it's A= Q B+R and zero, less than or equal to R, less than absolute value of B. So the general division theorem is almost exactly the same as the previous division theorem we proved, except that instead of demanding that B is strictly positive, we're saying that B is nonzero, and then here, we have the absolute value of B. And the proof follows fairly straight forwardly from the previous result. We've proved the results in the case b greater than zero, so assume b is less than zero. Then, since the absolute value of b is greater than zero, the previous theorem tells us there are unique integers q prime and r prime such that a equals q prime times the absolute value of b pl us r prime and zero less than or eq ual to r prime, less than the absolute value of b. Well now we simply let q equal negative q prime and r equal r prime. Then since absolute value of B in this case, would be negative, is negative b we get a is qb plus R, zero has to be equal to R that's an absolute value of B, and that's this theorem. So we simply threw it back to the previous result. And with the general division theorem now established, we can formally give names to the, the two numbers Q and R. Okay and officially, we say, the number Q is called the quotient of A by B and R is called the remainder. And so we've now cycled right back to something that you learned in elementary school about dividing numbers, and that there were sometimes remainders, there were quotients and remainders. Okay? Only now we've done it with some sophistication, and we've shown that everything is well defined. Well, how about that? Well, now that we have the division theorem available, we can look at the important mathematical property of divisibility. If division of A by B produces a remainder R equal to zero, we say A is divisible by B. Hence, A is divisible by B if and only if there's an integer, Q, such that A equals BQ. For example, 45 is divisible by nine, but 44 is not divisible by nine. The notation that we use for divisibility, is this. B vertical line a denotes a is divisible by b. And let me give you a warning at this point. B divides into a or a is divisible by b is not the same as B, divided by A with a slanted line. This guy. There's a relationship between A and B. It's true or false? This guy, you know, it's a rational number. The result of dividing b by a, into rational numbers. So we have a property relationship which is either true or false and we have a notation for a rational number. Now these are quite distinct concepts. This is something to do with two integers, tells you whether two integers are in a certain relationship. This is a notation for a specific number. The reason I'm, excuse me, this is a warnin g is that beginners in particular ofte n confuse these two things. They both after all do have to do with division but in this case it's a property, has nothing to do with, with fractions, with rational numbers. This, it's a specific number. It's a specific rational number that we're referring to. Now, there wouldn't be as much of a problem if the notation wasn't very similar. And it gets worse when people with sloppy handwriting, and you've probably noticed that I'm one of them, often don't distinguish clearly between a vertical line and a slanted line. In fact, this one is already almost vertical. Maybe it would have been better if I'd written it like that. Okay, that's better. But because the notation is similar, it's often very easy to get confused between these two things. The context does disambiguate, if you understand what, what's being discussed, you shouldn't have any problems. But bear in mind, especially when you're meeting this material for the first time, that there is an important distinction here, and in fact, I've got a quiz coming up in a moment which I hope is going to help cement your understanding of this notion, so that you'll be able to distinguish it from this one. Okay, and once we've got divisibility lined up we can define the all important notion of a prime number. A prime number is an integer P greater than one, that is divisible only by one and P. Notice that we explicitly exclude one. From the prime numbers. So the first prime's two. The next one is three, then five, then seven and eleven and so forth. Now for that quiz about divisibility. Okay. How did you do? Well, remember the condition we have to check is this one: B divides A if and only if, there is a Q such that A equals BQ. Well, let's see what we have. The correct ones. B. D. F. G. And H. Why don't I have A? Well remember the whole definition of divisibility was under the assumption that B is non-0. We can't consider the visibility by a zero number. So if that one doesn't work, and likewise, that one doesn't work, and, of course, the reason this one doesn't work , is because seven simply doesn't divide into 44. Okay? Do be careful about this though. Division by zero, is problematic under any circumstances. And so we, we root it out. In this case it was ruled out in the very statements of the divisibility theorem. Okay? How about this one? Well again, the condition that we have to check, is that B divides A, if and only if, there's a Q, such that A equals BQ. And again, this is under the assumption that, B is non-zero, everything is an integer here. The correct ones, that, that, and that. So why are the others false? Well this one is false because. That simply doesn't divide that. However if you sort of got out a calculator and actually try to divide it. Then you were missing the obvious point. This is an even number, and that's an odd number. And we cannot have an even number dividing an odd number. So if you had to do any arithmetic for this then you are making the mistake that I've been warning you against of acting as if you were in high school. This is a course about mathematical thinking, and what I hoped you would have done is to think about this mathematically and realize that you can't have an even number divided into an odd number. So this is a cautionary reminder that this is not about jumping into calculations and applying procedures. This is all about thinking about a problem. Okay? So that's false. Well I would hope that you would recognize that it's false without doing any work whatsoever other than a little bit of thinking, okay? I occasionally like to slip things like that into, into quizzes just to keep people on their toes. Well, this all is, is false of course because that's simply not the case, that 2N / N squared. The reason the others are false, well, this is false for various reasons. I mean, it's the same. I mean, 2N simply doesn't divide M squared for various reasons. The reason this is false is because if N can vary over Z then that will include N equals zero and so we can't have this because we can get a zero coming in that includes N equals zer o. Likewise for this one. Okay? Same thing. So this one fails, because zero was included. If I excluded zero, it would be fine. And, the only difference between these two is that this is the non negative integers one, two and three and so on so forth. This one because it's all of the integers includes zero. Okay, well, let's move on now. I want to prove a theorem now that gives the basic properties of divisibility. So theorem, let A, B, C and D be integers, with A non-zero. Then, the following all hold. One: A divides zero, and a divides a. Two: A divides one, if and only if, A equals plus or minus one. Three: If A divides B and C divides D, then A C divided by A D. This is under the assumption C is non zero. Because we can't have divisibility by zero the division theorem itself excludes the division by zero. Four: If A divides B and B divides C, then A divides C and this is under the assumption B nonzero. Again, we have to exclude the possibility of division by zero. Five: A divides B and B divides A, those two hold if and only if A equals plus or minus B. Six: If A divides B and if b is not zero, then absolute value of A, less than or equal to absolute value of B. You can only divide smaller numbers into bigger numbers or at least numbers that are a little bigger than. You can't divide a number bigger by something that's bigger than it in absolute value. One more. Seven: If A divides B, and A divides C then A divides BX plus CY for any integers XY. Okay, you prove all of these by going back to the definition of divisibility. What, what I'm going to do is just I'll give you, I'll prove two of them, as examples. Let me just pick number four. Let's prove four that's this one here. All the proofs are essentially the same idea, if A divides B and B divides C, then that means there are integers, D and E, such that B equals DA and C equals EB.That's the definition of divisibility, in which case, C equal D times E times A, whi ch again by the definition of divisibility, means A divides C. Let me do one more, let me do , six. Okay. So A divides B so that means since A divides B, D. So it's that B equals D A. In which case, taking absolute values, absolute value of B equals absolute value D, times absolute value A. And since B is non zero, we know that the absolute value of our D will have to be greater than or equal to one. So the absolute value of A is to the absolute value of B. See B is non-zero so D can't be zero. So its absolute value is greater or equal to one. And if the absolute value of D is greater than or equal to one. Then A has to be less than or equal to B. The other statements in the theorem, approved similarly. You just take it back to the definition of divisibility and, when you, you know, that's, remember the definition is, B divides A, if, and only if, there is a Q such that A equals BQ and in all cases, you go back to the definition, and then, the thing drops out at a couple of lines. Okay, well that's the, that lists all of the basic properties of divisibility. Okay, it's time to prove the fundamental theorem of arithmetic. Theorem. Every natural number greater than one is either prime or can be expressed as a product of primes in a way that's unique, except for the order in which they are written. For example, four is two times two or two squared. Six is two times three. Eight is two cubed. Nine is three squared. Ten is two times five, twelve is two squared times three, and so on, and so on. 3366 equals two times three squared times eleven times seventeen, and so forth. I worked that one out in advance by the way. Okay. So two itself is prime, three is prime, four is a product of primes, five is prime, six is a product of primes, seven is prime, eight is a product of primes, nine is a product of primes, ten is a product of primes, eleven is a prime, twelve is a product of primes, and so on and so on and so forth. The expression of a numbers of positive primes is called it's prime decomposition, and when you know the prime decomposition of a number, you know an awful lot of information about that number an d how it behaves with, with relation to other numbers. Well we've proofed part of this a little while ago. Proofed the existence part. Though I'm gonna give you another proof of existence in a moment. But the new part is to prove uniqueness. The uniqueness proof will require Euclid's lemma. That says if a prime P divides a product AB, then P divides at least one of AB. The proof of Euclid's lemma is not particularly difficult, but it would take me outside the scope of this course. Remember, the, the focus of this course isn't to, isn't to teach you number theory and number theoretic techniques. It's to develop mathematical thinking and it would be too much of a detour from that, that goal in order to prove Euclid's lemma. But if you just Google Euclid's lemma, you should be able to find some references, that would lead you to a proof. Let me give you the existence proof. More precisely, let me give you a new proof of existence. Remember this is the statement of the theorem. Any natural number greater than one, is are the prime or can be expressed as a product of primes in a way that's unique accept to their order. Then we're going to prove existence. The previous proof of existence that I gave you used a method of mathematical induction and I gave it as an illustration of the method of induction, but I'll give you a different proof now. I'll prove it by contradiction. Suppose there were a composite number that's a non-prime, that could not be written as a product of primes. Then there must be a smallest such number. Call it N. Since N is not prime, there are numbers AB, strictly between one and N, so it's just n equals AB. If A and B are primes, then N equals A of B is a prime decomposition of N, and we have a contradiction. Because N was chosen. So as not to have, a prime D composition. It was actually the smallest number that didn't have a prime decomposition. Well, if it's not th e case that A and B are primes, at least one of them must be composite. But if either of AB is composite, then because it's less th an N, it must be a product of primes. So by replacing one or both of AB by its prime decomposition in N=AB, we get a prime decomposition of N, and again we have a contradiction. That proves existence. That's the first part of the proof of the fundamental theorem of arithmetic. Now let me prove the uniqueness. So what I have to prove, is that the prime decomposition of any natural number N greater than one, is unique, up to the ordering of the primes, and I'll prove it by contradiction. So, assume there is a number N greater than one, that has two or more in fact different prime decompositions. Let N be the smallest such number. Let N equal P1 times P2 times da-da-da times PR equals Q1 times Q2 times da-da-da QS be two different prime decompositions of N. So we have N as a product of R primes, and we also have N as a product of S primes some of the primes being different. Well, P1 is a prime factor of N, so P1 divides N, so P1 divides this product. Since P1 divides Q one times Q two through Q S, and let me stop at this moment and see what I've done? I've said P1 divides N, so P1 divides this, and I'll split that into two that way, and notice that P1 divides Q1 times that. And I've done that in order to apply Euclid's lemma. So now let me continue that sentence. By Euclid's lemma either P1 divides Q1 or P1 divides the product Q2 through QS. Remember, Euclid's lemma says that if I have a prime number P and if P divides a product A B, then P divides at least one of AB. So Euclid's lemma was that if P divides a product, A or B, it divides at least one of those two numbers. So if I'm here, P1 divides this product. I've now written that as a product of two numbers and I can now apply Euclid's lemma and so, that if P1 divides that times that number, it must divide at least one of them. Either P1 divides Q1, or it divides the other parts, or maybe both of them. Okay. Hence, either P1 equals Q one, or else P1 equals QI, for some I between two and S. Okay, if P1 divides Q1, then they're both prime, so the only possibility is P1 equals Q1 or else P1 divides this product of primes, which means that P1 actually is one of those primes. So first case, I know that P1 equals Q1. Second case, I know that P1 equals QI, for one of the I's between two and S, but then, we can delete P1 and QI from the two decompositions in star, which gives us a number smaller than N. That's just two different prime decompositions. Contrary to the choice of N as the smallest . Okay, having established that P1 is equal to one of these Q's, we don't know which one but it's going to be one of them, I can delete the P1 from here. I can delete the appropriate Q from there, and when I delete P1 from there and some Q from there. I still have a quality. I still have a prime decomposition of a number, but having deleted that common prime, the number that I get is smaller than N. So I get a number smaller than N, which has two different prime decompositions. The number smaller than N will be P2 da-da-da PR, that will be a number smaller than N and I've deleted a number from here and what's left is a, is a prime decomposition here. So the proof involves simply identifying the fact that, or recognizing the fact, this uses Euclid's Lemma. That you're gonna have the same prime on both sides. You can delete it, and get two different decompositions of a smaller number, and that proves uniqueness. Okay? Well, now we've proved the fundamental theorem of arithmetic. Cool, huh? So, did that make sense? Chances are you're going to have to spend some time coming trying to grips with this. Though I know you're familiar with arithmetic, especially whole number arithmetic, this is probably the first time you've tried to really analyze numbers. See how you get on with assignment nine.