You, Me and The Legend of Question 6

today it will be you me and the legend of question six and as you all know now the questions can be called the legend however this right here is the one and of course we are talking about in 1988 i am a question number six you should have seen a video by number five where they talk about this question and especially how difficult this is i've been trying to understand the proof of this for a while now unfortunately i couldn't but lucky recently i found a website in taiwan and they have a solution that i actually was able to follow so i wanted to demonstrate that for you guys as well so you can understand this too well before we get into the math let me just give a big birthday wish to y'all happy birthday and thank you so much for being a fan of my channel and your support thank you happy birthday all right let's go over this right here first right here it says let a and b be past the integers and that's the notation such that a squared plus b squared over a b plus one is equal to a positive integer right here so in another way you can say a b plus 1 divides a squared plus b squared right that's actually the original wording but we'll actually use this because it's easier to work our equations from here well if we end up with an integer we are going to show that the number k has to be a perfect square so let me give you guys an example right here let me just say if a is equal to 8 and b is equal to 2 plug in then you see that a squared plus 2 squared is equal to 8 times 2 plus 1 of course on the top is what 68 on the bottom is 17 when we divide do we end up with a whole number yes we do and the statement says whenever you end up with a whole number the number has to be a perfect square in our case we end up with four of course this is the same as two squared so it checks and let me give you guys another example if we end up with let's say a is equal to three b is equal to 2 then we are talking about 3 squared plus 2 squared over 3 times 2 plus 1. on the top we get 13 on the bottom we get 7. well guess what this does not even turn out to be an integer so that we don't care right so that this right here we don't care at all so let's go ahead and get started here is the most exciting thing i like to do whenever we're trying to do a proof namely writing down the pdf seriously every time it reminds me the google college days because sometimes that's the only thing i was able to do anyway how do we show the output is a perfect square well uh it might not be so easy if you do it directly so we'll try to do it by contradiction right so in the right proof right here so let me just tell you guys here we go by country diction we are going to assume that based on all this already we are going to assume that this term cell to be an integer but the integer k it's not a perfect square assume k is not a perfect square so i'll just write down ps for perfect square right and because we'll be referring to this equation quite often so i will actually just say this equation star so that it's easier to do so as well all right now here is the do have a look we have this equation now right it turns out to be integer by the integer we are assuming it's not perfect square well a b they are perf they are positive integers and whenever we have a set of positive integers we can assume that there is a smallest element well so here we go we are going to let a1 b1 be the smallest we can also say minimum be the smallest solution to star right so we can plug in a1 and b1 to here and then we end up with some k and we'll work with the k and we'll show that if k is a perfect square or not whatsoever right so we have that however another thing to notice that though if you look at this right here earlier i picked a to b8 and b to b2 now what if i do a is equal to 2 and b is equal to 8 what do we get well you see that it actually does not matter because if you just switch a and b the output will still be the same right because just look at if you swap a and b doesn't change anything so this is what we can do next we have a and a1 b1 be the smallest solution to this right here and i'm just going to assume that without loss of generality so wlog assume that a1 is less than well let's do the greater than let's say a1 it's a bigger number let's do it like this a1 is actually bigger than or maybe equal to b1 like this and of course you can have the other way wrong and then arguments you know identical so you can just say assume loss of generality put this down and we can continue if this gives us the result the other way will give us a result as well so now here we go we have a1 and b1 to work with we can put this into this right here of course right so we have a1 squared plus b1 squared over a1 b1 plus 1. this right here is equal to k now isn't it so that's what we have and then of course let me just go ahead and continue the map right here the best part right here is that we can do some algebra so i'm going to just multiply this on both sides and i will collect all the terms to the right hand side so this right here is going to give us so look here i will keep this right here namely we have a1 squared and next i would have to do this times k and it has a1 right and i will bring that to the left hand side so it becomes negative and then let me put on k b1 first and then i will have the a1 right here all right continue this well we still have the plus b1 squared and we will have to do k times one on the right hand side bring that to the other side so we get minus k and of course all this is equal to 0 so that's good now have a look here is a1 square here is a1 and the rest are just numbers so what's this yes it's a quadratic equation so we can say the following notice a1 is a solution to the quadratic equation x squared minus k b 1 x and then plus b 1 squared minus k equal to 0 right and now of course whenever we have a quadratic equation how many solutions do we have two right so a1 is one of them already let's say let a2 be the other solution well is a2 complex is a2 decimal numbers whatsoever we're going to investigate a2 now so because a2 is just another solution to this quadratic equation of course we're plugging a2 and this right here still works so we can say that a2 squared minus kb1 a2 plus b1 squared minus k this right here has to be equal to zero that's very nice well notice that here's the deal we have a1 and a2 being the solutions to a quadratic equation we can actually write the quadratic equation as follows we can also write we may write may write the quadratic equation perhaps i'll just put it down with double star in blue right we may write double star as x minus a one times x minus a two equals zero and that's very nice and again this is just the factory form and of course we can write this into this and of course we can also expand this a little bit to do so we see that we get x square and then this times this is just and this times this both of them have the negative factor that out and then we have the a1 plus a2 inside and that's the x term and then this times this is just plus a1 a2 equal to zero so in other words we can put this into this form and now what can we say well here is the coefficient of x likewise this is the same as well and here is the constant term and we can also say that's the same as well and this is where if you would like to be fancy you can say this is the fiat theorem and that's just pretty much a proof and of course it's just a quadratic situation so you can just do it like this right so here's the do we know now we have a1 plus a2 is equal to this and we can somehow of course we can isolate the a2 and we can somehow investigate how a2 should behave right so let me just go ahead and minus a1 on both sides so we get this right here says a2 is equal to this right here which is k b1 before they have the negative already don't worry and bring this to the other side so minus a1 right just solve for the a2 likewise i can just divide the a1 from here to here so we get a2 this is equal to we have this which is b1 squared minus k over a 1 and now we have this right so now we can do some investigation first can a2 be a decimal number no because notice a1 b1 and k they are all positive integers so right here we can say a2 has to be an integer right so that's pretty clear because everybody here is integer and integer is closed under subtraction and multiplication so that's good now you see a2 is equal to this on the top we have b1 squared minus k but what did we say about k well we said that k is not a perfect square it's not a perfect square so it can never be the same as some number square in another word on the top right here this is never the same as that so this can never be zero so from here we can say that a2 will never be equal to zero and perhaps you can say because k is not a perfect square so we did have to use our assumption from here right here right so that's great and that's good a2 is an integer but that's not zero cannot be negative though because you know sometimes uh you have some subtraction it's dangerous so how to do it carefully and now let me just come back here and um i don't really want to erase the question so i will actually just erase this right right so let's work out all right now let's see if a2 is positive or negative whatever right from here where did this equation come from here and just substitute the a2 into this equation right here right and where did this come from of course just from here so of course if you like you can put this equation into that form as well so i will just tell you from the equation a2 squared plus b1 squared over a2 b1 plus 1 equals k have a look here k is positive this is positive so i just say this is greater than zero and likewise this right here a2 squared plus b1 squared this right here is also positive because it's the sum of two squares plus one is positive for sure and notice b1 well it's a positive integer so that means b1 has to be greater than or equal to 1. now when we have all this condition here can a2 be negative can a2 be negative 1 no that will ruin everything no can a2 be negative two no we'll end up with a contradiction that the left hand side is being negative then and then the right hand side is still positive so from here we can say a2 has to be greater than 0 right so with all this now we see a2 is e the set of passing integers right because of this this and that are good now earlier we mentioned that a1 b1 they are the smallest solution to this right here and we somehow to use that as well and here we have this new guy which is a2 how is a2 compare with a1 well remember i have a assumption that so from the assumption from the assumption that a1 was greater than or equal to b1 have a look right here let's go ahead and square both sides and this of course they're parsley integers so we can square them and in that case the inequality will still hold from here we can say a1 is greater than or equal to b1 with the square right here and again because both of them are greater than zero so this inequality out now i will just keep the a1 square on the left hand side and then b1 squared right here except for i would like to minus k on the right hand side and we do that because k is a positive number this subtract positive number i can say a1 is bigger than this right so they cannot equal to each other anymore what does that do have a look i'm going to divide the a1 on both sides and i'm going to just keep this right here for you guys real quick right you'll see divide a1 on both sides so we get a1 normal square because this right here is i want to divide both sides and a1 is positive i can divide on both sides no big deal still greater than this is greater than b 1 squared minus k divided by a1 and what's this this right here is nicely equal to a2 so we can say this right here is nicely equal to a2 thus we see that a2 is actually smaller than a1 and this is strictly smaller than a1 hmm is this possible well earlier we have said that you know a2 is the solution to this and it fits all the conditions however a1 was supposed to be smallest and now we found one guy right here a2 that's actually smaller than a1 so what happens something must be wrong right thus a2 is less than a1 i will just tell you which contradicts countries our assumption that assumption i just spelled something yourself an assumption that a1 b1 were the smallest the smallest because now we see a2 b1 is smaller than this right so this right here is assumption that we can just say it contradicts so what's wrong though well this right here remember our original assumption is what let me just write this down for you guys let's see which constructed our assumption that a1b let me just write it down better again i'm sorry which contradict our contradicts the previous assumption that the a1 is the smallest right so again the wrong process is that now a2 b1 also solves that but a2 is smaller than b1 and that contradicts that a1 is being the smallest so let's see how we can finally write down the punchline right here smallest therefore our oops first assumption first assumption was wrong our first assumption about k remember the first line is that we assume for a contradiction that k is not perfect square so we are saying that our first assumption about k is wrong and finally ladies and gentlemen we conclude that k has oh my god two b a let me spell this out because this man this is the final line k has to be a perfect square oh my god and of course i will give you a perfect square right here at the end all right

Channel: blackpenredpen

Views: 311,244

Keywords: The Legend of Question 6, IMO 1988, number theory, hardest IMO problems, proof by contradiction, math for fun

Id: usEQRx4J_ew

Length: 19min 27sec (1167 seconds)

Published: Mon Apr 20 2020