I saw somewhere that this problem is a particular case of the nice generalization (much harder to prove): Let a, b positive integers. Prove that if (ab)^(n-1) + 1 | a^n + b^n, then (a^n + b^n) / ((ab)^(n-1) + 1) is a perfect n-th power.
This solve is brilliant, always you assume there is a minimum (a,b) when the equation is not a perfect square, you'll always find out a smaller number than the minimum
Yes, sure. Well said. If you omit that detail, you may start the demonstration by stating °let's assume k is a perfect square°, and then conclude that by contradiction k must not be a perfect square.
This proves a stronger claim: Not only k is a square, it is the square of the smaller of A and B. Effectively, this proves that (a^2 + b^2)/(ab + 1) = b^2 if a>=b and a,b are both positive integers. Solving the above, we get that (b^3, b) are the only solutions to the above equation.
It can be solved with elementary number theory without Vieta jumping. If you modify the rest of the theorem a little bit. The size of b is between ak-a and ak. Set b = ak - r (0
5:47 I would like to add a few more steps here so that the jump may become clearer for those who didn't get it. A1B+1>0 => A1B > -1 As A1 was proved to be an integer and we know B is an integer as well (natural to be more specific), A1*B must also be integral. Hence A1B can be 0 at minimum as that is the next integer after 0 => A1B >= 0 A1 was shown not to be 0 and B is natural so it can't be 0. Hence since both A1 and B are non-zero, their product must also be non-zero and therefore it can only be >0 => A1*B > 0 Now since B is positive by virtue of being natural, A1 must also be positive. QED
@@lewischeung868 , I do not agree, that it saves the proof. The proof itselve is clean and safety. It was just a step so easy, that he did not waste time explaining. The proof it is so pretty, excellent. Nothing to repair.
@@pedrojose392 i am sorry to tell you that i don't agree with your point. The logic behind proof by infinite descent is to show "we can generate a smaller counter example from a given counter example". However, natural number has a lower bound, which is "1" accordingly. We can't accept an infinite descent algorithm for such problem. Then, a contradiction arises. Why this step is necessary? If we can't make sure A1 is positive, we cannot say (A1,B) is a possible candidate for a smaller counter example. Our infinite descent algorithm cannot bee carried out and eventually the proof is meaningless. I hope my terrible english can persuade you the reason behind. :)
Also remember that by today's standards, this is a relatively easy problem compared to then. Its about as standard as Vieta Jumping gets, but Vieta Jumping was nearly unheard of back then, which is why this problem is so famous
@@4ltrz555 I believe it was the coordinator that gave the question, so the funnier thing is that the teacher didn't know that this was an imo question either
This method is very interesting! I didn’t expect this setup could lead to a solution. I need to watch again to better evaluate what role “being a perfect square” plays in solving this problem.
I think I figured it out, basically if we twist the problem a bit and assume we are only given that “k is a natural number” and nothing is said about perfect square, we can still find that the solution is actually limited to a specific structure, i.e. k must be B^2 and A must be B^3, as this is the only way this whole thing can hold up.
@@unemployed5373doeesnt tbis sbow this method is CONTRIVED and not FAIR since no one will think of it..why not soove in qctual ontelligent way ppl will think of??
Thank you very much. this idea is very helpful for my problem that ask me to prove for positve x,y if (x²+y²+6)/xy integer then it must be perfect cubes
There's only one negative integer solution to the equation which is -5. The 8 non reducible sets of a and b are (-1,2) (-1,3) (2,-1) (3,-1) (1,-2) (1,-3) (-2,1) and (-3,1) and with these you can Vieta jump to larger absolute values. Like -5(3) - (-1) yields -14,3
@@anshumanagrawal346 if k not being a perfect square leads to a contradiction then k being a perfect square must not lead to a contradiction. The contradiction is a2
@@opusmagnum-u2p 4:50 from this term we can see if B^2-k = 0 then A1=0, which is not a natural number, which does not lead to a contradiction at the end since A1 is never valid as a solution, in the actual solution A1 leads to contradiction because A1 > 0, which contradicts to the assumption "(A+B) is minimal"
for those who totally confused: there is only two case where the divisibility is possible: 1. a or b is zero, but only one of them. 2. a=b^3 or symmetrically b=a^3. The solution in this video explains why these conditions must be. Although the conditions are not mentioned in the video, we can see that k must be equal to b^2. and the rest is the conditions...
The pairs of integers that fit the equation are x^(2n-1) - (n-2)x^(2n-5) + T(n-4)x^(2n-9) - TT(n-6)x^(2n-13) + TTT(n-8)x^(2n-17) - TTTT(n-10)x^(2n-21) + ... where T(n) is the triangle number TT(n) is the triangle number of the triangle numbers and TTT(n) is the triangle number of the triangle numbers of the triangle numbers and so on. If you substitute n = n - 1 you get the other pair and if the power becomes negative you stop the formula. So if n = 11 you get a=(x^21 - 9x^17 + 28x^13 - 35x^9+15x^5- x) b= (x^19 - 8x^15 + 21x^11 - 20x^7 + 5x^3) cause T(11-4)=28 TT(11-6) = 1+3+6+10+15 =35 TTT(11-8) = 1+1+3+1+3+6=15 TTTT(11-10) =1 and T(10-4)=21 TT(10-6)=1+3+6+10=20 TTT(10-8) = 1+1+3=5. All the coefficients add to either (1,1) (1,0) (0,1) (0,-1) (-1,0) or (-1,-1) so that x = 1 will result in 1.
By the same solution we can prove that the all couples (a,b) satisfaying this property are ( a , a^3 ) and ( a^3 , a ) for all integer a . It is more general solution, on particular when we calculate the ratio for this only case we find a^2 wich is perfect square.
A nice trick is to quickly abuse symmetry and transform this into symmetric polynomials form. Then it becomes a lot easier but still hard to solve without the hell a lot of ring theory
Surely a^2 is a square if u look st it geometry wise, and b^2 is a square. Ab+1 is a length of an+1. If you divide the square a length, your just scaling the square down .
How do we know that A, the root, is an Integer, i.e. a non floating point number in proof that A1 is in Z? Also, that A1 is >0 comes from A1B+1>0 A1>(-1)/B which gets us A1>(-1) since B is an Integer. Since we just showed that A1 is a whole number and we assumed for our proof by contradiction that A1 /= 0, otherwise k would be an Integer square, A1 has to be in IN/0. Therefore A1>0. Feel like you not only skipped a lot of steps there, but also presented them in a wrong order.
If ab+1 divides a^2+b^2 then b^2=a/b (it is simple: divide (a^2+b^2) by ab+1 and to make the rest=0 it is necessary b^2=a/b) Then b^2=a/b --> b^3=a. ----> substituting in (a^2+b^2)/(ab+1) --> (a^2+a^6)/(a^4+1)=(a^2(a^4+1))/(a^4+1)=a^2.
Also, don't you think it's a problem if you get a result like that since, by symmetry, you could conclude b=a^3 and so a=b=1 only solution? (btw you can easily see (2, 8) is another solution)
I am not able to find the condition b^2=a/b. By dividing a^b+b^2 by ab+1 the rest is a^2-a^2b-a+b^2. Now how do you elaborate on a^2-a^2b-a+b^2=0 to get that there must be b^2=a/b. Thanks
Just to express differently ... (a^2+b^2)/(ab+1)=k, where a,b,k all pos integers. So need k*(ab+1)=kab+k to equal a^2+b^2. Hence need (1) kab=a^2 i.e. kb=a and (2) k=b^2. Substituting in for k in eq1, then kb=(b^2)*b=b^3=a. With a=b^3 we substitute and simplify: a^2+b^2 =b^6+b^2 =(b^2)*(b^4+1) ab+1 = b^4+1 So ratio = b^2 = k. Done.
hey please check this solution a²+b² can be written as (a²+b²)(1+ab) - ab(a²+b²) and as (1+ab)|(a²+b²) then ab(a²+b²) should be equal to zero In case 1, when a² + b² = 0, the expression (a² + b²)/(1 + ab) simplifies to 0/(1 + ab) = 0, which is indeed a perfect square. In case 2, when ab = 0, the expression (a² + b²)/(1 + ab) simplifies to (a² + b²)/(1 + 0) = (a² + b²)/1 = a² + b². Since ab = 0, it follows that a² + b² = (a + b)², which is a perfect square. Therefore, based on these two cases, it can be concluded that for any values of a and b, the expression (a² + b²)/(1 + ab) is always a perfect square.
I enjoy your videos but I am very curious about seeing things in the flesh so I was curious as to what numbers actually satisfy this condition. It took me about 10 seconds to write a line of maple code to produce the results and it is interesting to see that any two numbers x and x cubed will satisfy the conditions for a and b The only pairs less than a thousand which also satisfy this condition are (30,8)...(112,30)...(240,27)...(418,112)
i dont know a lot on how to solve these type of questions or how these even work rather but heres how i solved,please just tell me if im wrong anywhere(i certainly will be) let us assume a^2+b^2/ab+1=p where p is a natural number is not a square ----(1) ab+1/a^2+b^2=y which is a natural number ab+1=(a^2+b^2)(y) (a^2+b^2)(y)/(a^2+b^2)=p 1/y=p y=1/p but according to (1) p is a natural number but i/natural number is not a natural number therefore our assumption is false and p is a square number
Sir my answer firstly distributed ab +1 in a^2+b^2 take a>=b so a^2 greater than ab +1 so if we divide than remainder will be -a/b and if we divide b^2/ab+1 remainder will be b^2 net remainder will be zero -a/b+b^2=0 so a=b^3 if we put this value in expression we got b^2 which is perfect square ... Thank you I am from india
I am reading comments that say, 'I couldn't solve this when I was 13', 'when I was 15' etc. I can proudly and truthfully say that I never failed to solve this problem ever ! ))
If we assume that A=B then we have k=(2A^2)/(A^2+1) this is less than 2, which forces our k to be a positive integer less than 2, this is k=1 which is a perfect square. So it is better to assume either A
This uses a proof by contradiction, where you assume that (a²+b²)/(ab+1) is not a perfect square, then you draw a contradiction from the initial assumption. In this case, we proved that there is no minimal solution that equals a non-square. Since a and b are in the natural numbers, this effectively proves that there are no solutions at all which equal a non-square. This doesn't only prove a minimal case, it proves that all the cases must lead to a perfect square.
We didn't _assume_ a+b was minimal. We chose se (A,B) such that it gave minimal A+B as we know _a_ pair giving minimal sum must exist because there is always a minimum value in a list of integers (the list of A+B here) Then we showed that there exists a pair that gives an even smaller sum which is impossible since we chose the pair which already had the lowest possible sum. Therefore a logical contradiction happened and so some assumption must have been wrong. There was only one that k wasn't a perfect square. So k must be a perfect square. The existence of a case where a+b is minimal isn't assumed as there always exist A,B satisfying that. Since only the existence of (A,B) is necessary here, we are fine
@@pbj4184 Really good explanation, the key here is that choosing the minimum solution is what leads to the contradiction later. The minimum solution isn't one case that was checked, but it proves every case.
@@kenthchen Something true must work for all cases. So if it doesn't work for the case where A+B is minimal, it isn't true. And since k can only either be perfect or non-perfect square and we showed it cannot be a non-perfect square (as that leads to a contradiction), it must be a perfect square.
Why does the proof by contradiction imply that the assumption about k not being a perfect square is false? It could also imply the assumption about k being a natural number is false. Why is the proof sound?
BTW contrary to the popular belief that nobody could solve it actually there were 2 or 3 students who got 7 and 8 out of 8. Numberphile had mentioned this.
k not square was used to deduce that A1 is not zero, and hence positive by a later argument. Minimality of roots is a fancy formulation of induction. Having (A,B) a solution, it is shown that (A1,B) is a smaller solution which is a contradiction assuming that (A,B) is a minimal solution. Here, positivity of A1 is needed so that (A1,B) is a proper solution. In other words, the Vieta jumping produces smaller and smaller roots, hitting zero at some point. But hitting zero is only possible if k is square.
The case of the repeated root would require A^2 = B^2 - k since it would be when A1 = A (the same equation used in the proof in the video), but k = B^2 - A^2 is only positive when b>a, which is false by assumption.
I found an easy solution, but of course there must be something wrong with my assumption. a^2+b^2 = k (ab+1) a^2+b^2 = kab + k Then I consider !!! a^2 = kab b^2 = k So k=a/b and k=b^2 and thus a = b^3 Substituting (b^6+b^2)/(b^4+1) = b^2 Which is a perfect square Hope that you can comment on this solution.
How is that possible as k cannot be equated to b^2 as we didnt prove k is a perfect square ,the main motive is to prove k is a perfect square so we cannot assume it
@@sinistergaming1418 it doesn't really assume that k is a perfect square a+b ------ = n c+d if a/c =n Then b/d also equal n 9+18 -------- = 3 3+6 9/3=3,18/6=3 27/9=3 This is how division and ratio works, since we have unknowns, it's safe to say a²/ab = k, and same with b²/1= k Although there will be times where the solution isn't like this, so i guess this is just possible answers
Would be sweet to proof this thing by showing, that these are the only solutions possible, because then it easily breaks down to k=b^2 (respectively k=a^2) There might be a way to show this in a way, that any prime factor that is in a must also be in b and vice versa and once you are there, then conclude that the exponent must be exactly 3.
I found this: Let (a, b) be any solution pair with a>b and let s = (a^2+b^2)/(ab+1). Then another solution can be derived by creating solution pair (s*a-b, a). So if we start with a trivial (a,0) solution then that generates (a^3, a). Then from (a^3,a) we can generate (a^5-a, a^3) as another solution. And of course we can keep going to generate larger solutions.
Why would we assume A+B is the minimum in the proof? Without the assumption that A+B is minimal, shouldn’t the Vieta formula still hold true? Then you just found another solution, A1, B to the original equation, but you have nothing to contradict with. (Just for my understanding)
It's not like that. The problem is claiming that ALL natural solutions also happen to produce a perfect square. So the guy says let's say we find a solution that meets all the criteria a,b are naturals and that those two expressions divide. Suppose we find a solution and not just any solution we find the smallest solution. Which of course there will be. Assume we have the smallest solution that is NOT a perfect square then this proofs shows if that were the case you could always make a smaller one..which is a contradiction. Therefore, it must be a perfect square.
Since A1 = kB - A, where k, B, and A are all integers, we know A1 is an integer. We know A1 = (B^2 - k) / A by Vieta's formulas. Since B is an integer, and we are supposing k is not a square, then B^2 - k ≠ 0, so A1 ≠ 0. Combining the above two results, we know that A1 is a non-zero integer. We know (A1^2 + B^2) / (A1 * B + 1) = k > 0. Since the numerator A1^2 + B^2 > 0, then this quotient is only positive if the denominator A1 * B + 1 is also positive. A1 * B + 1 > 0 implies A1 * B > -1. We know B > 0 since it was defined that way when setting up the problem. We know from above that A1 ≠ 0. Since A1 and B are integers, their product can't be between -1 and 0. So A1 * B can't be less than 0 (-1, -2, -3, ...) and it can't be 0, so it must be greater than 0.
Why people made this so complicated? Obvious (ab+1) must be greater or equal to (a^2+b^). If (a^2+b^2) is greater than (ab+1), the result of (ab+1)/(a^2+b^2) is less than one. (ab+1)>=(a^2+b^2), both side minus 2ab, then we have (1-ab)>=(a^+b^2-2ab)=(a-b)^2, which is greater or equal to zero. Then, we have (1-ab)>=0, it implies 1>=ab, since both a and b are positive integer, the only solution is a and b equal to 1. (a^2+b^2)/(ab+1)=(1+1)/(1+1)=2/2 = 1, which is perfect square. Is it a primary school mathematics?
@@alainsavard8147 if q | r, q & r are integer, then q >= r. according to wikepedia.org, "|" is divisible. If q is divisible by r, q should be greater than or equal to r. Otherwise, if q < r, q/r is a fractional number.
"(A + B) is minimal" is used in the very last part to create contradiction, in this solution whenever we assume a non-perfect square k which has a minimal solution (A + B), we can always find an even smaller pair (A1 + B), which is supposed to be invalid, which proves that the assumption was invalid at start, therefore proved the actual problem
I really like your accent, that stereotypical Asian accent (I mean it in a good way, I'm not being racist, I'm Asian too) makes me much more comfortable dunno, if I'm the only one
where is the fact that k is not perfect square be applied??? can also the proof in the video be applied when k is perfect square so that k cannot be an integer???
How did you assume that A1=(B^2-k)/A belongs to N (natural numbers)? Without proving any sort of relation between B^2 and k, we cannot plug in A1 in the original equation. Just because A1 is not 0 and it is an Integer, we cannot plug it into the original equation. We have to prove A1 is a natural number.
I must please ask for help on this problem ! the sequence a(n) is defined like this: a(n) = a(n-1) / 5 , if a(n-1) is divisible with 5 or a(n) = [a(n-1) * sqrt(5)] , otherwise. ( [x] is the floor function ) , with a(0) being a natural number , not equal with 0. Prove that this sequence contains only a finite number of terms divisible with 5 .
Can u prove that k=gcd(a,b)² pls. This one was given to us by teacher and till this day I still have no clue how to do it. Only thing I know is this use strong induction.
I have proved： Let a≤b a is any positive integer If ab+1 | a²+b² and a is not a perfect cube, then b＝a³. If ab+1 | a²+b² and a is a perfect cube, then b＝x⁵-x where a＝x³ and x is a positive integer.
@@dp121273 yes bro I just watched it a few days ago. Will edit the link here... Edit: ruclips.net/video/Y30VF3cSIYQ/видео.html Here's the question ruclips.net/video/L0Vj_7Y2-xY/видео.html Here's the answer.
a^2 + b^2 = d^2 is granted by pythagoras. P.S.: That, of course, is nonsense. But i have a biological brain, so this trigger went off, and the anti-trigger "but only if in a right triangle" didn't. Thus, the rest is sadly nonsense as well (but it looked so nice, you know :D)... d^2 = c^2 * f has to have both factors on the RHS to be either equal or each square (else the product ends up having one prime exponent uneven, thus being not square). Equal they cannot be, since f = (a*b + 1) is given, and its square is not equal to a^2 + b^2. Done.
Bro..i . Do all process same and assume that , k is a perfect square instead of assuming k is not a perfect square.. Still the contradiction occurs... Please explain this. Where do i make a mistake
A_1= (B^2-k)/A is not equal to 0 comes from the assumption that k is not perfect square. (b^2 is a perfect square, k is not hence k cannot equal to B^2 hence B^2-k is not equal to 0 hence the entire fraction is not equal to 0.) In contrast, if k is a perfect square, then you cannot proceed from here because there is always the possibility that k=B^2 and thus A_1=0 which makes (A_1,B) not a solution to the problem which does not lead to a contradiction.
I saw somewhere that this problem is a particular case of the nice generalization (much harder to prove):
Let a, b positive integers. Prove that
if (ab)^(n-1) + 1 | a^n + b^n, then
(a^n + b^n) / ((ab)^(n-1) + 1) is a perfect n-th power.
This looks interesting, where did you find it?
I have a wonderful proof of this, but I'm afraid it doesn't fit within the margin of this RUclips comment section...
@@mattiascardecchia799, quite interesting. could you give an indication for the starting direction of that proof.
@@mattiascardecchia799 lol
@keescanalfp5143 it’s a fermat reference
This solve is brilliant, always you assume there is a minimum (a,b) when the equation is not a perfect square, you'll always find out a smaller number than the minimum
The critical part is A1 is not 0 because B^2 - k can't vanish. Blink and you miss it, still a great job laying out the proof!
Yes, sure. Well said.
If you omit that detail, you may start the demonstration by stating °let's assume k is a perfect square°, and then conclude that by contradiction k must not be a perfect square.
ah yes thanks, i was wondering the link with the fact we forbid k to be a square
@@MarioRossi-sh4uk Probably both elegant, I wonder if that would complicate the proof or make it simpler
This proves a stronger claim: Not only k is a square, it is the square of the smaller of A and B. Effectively, this proves that (a^2 + b^2)/(ab + 1) = b^2 if a>=b and a,b are both positive integers. Solving the above, we get that (b^3, b) are the only solutions to the above equation.
@@GauravPandeyIISc thats actually not true. (a,b)=(30,8) would be a counterexample
It can be solved with elementary number theory without Vieta jumping. If you modify the rest of the theorem a little bit.
The size of b is between ak-a and ak.
Set b = ak - r (0
5:47 I would like to add a few more steps here so that the jump may become clearer for those who didn't get it. A1B+1>0
=> A1B > -1
As A1 was proved to be an integer and we know B is an integer as well (natural to be more specific), A1*B must also be integral. Hence A1B can be 0 at minimum as that is the next integer after 0
=> A1B >= 0
A1 was shown not to be 0 and B is natural so it can't be 0. Hence since both A1 and B are non-zero, their product must also be non-zero and therefore it can only be >0
=> A1*B > 0
Now since B is positive by virtue of being natural, A1 must also be positive. QED
Other viewers will appreciate this comment. Thank you
This comment clearly saves the proof :)
thanks
@@lewischeung868 , I do not agree, that it saves the proof. The proof itselve is clean and safety. It was just a step so easy, that he did not waste time explaining. The proof it is so pretty, excellent. Nothing to repair.
@@pedrojose392 i am sorry to tell you that i don't agree with your point. The logic behind proof by infinite descent is to show "we can generate a smaller counter example from a given counter example". However, natural number has a lower bound, which is "1" accordingly. We can't accept an infinite descent algorithm for such problem. Then, a contradiction arises.
Why this step is necessary? If we can't make sure A1 is positive, we cannot say (A1,B) is a possible candidate for a smaller counter example. Our infinite descent algorithm cannot bee carried out and eventually the proof is meaningless.
I hope my terrible english can persuade you the reason behind. :)
Remember: even Terry Tao did not find a complete proof to this question.
In the limited time of the exam though. Remember in that amount of time he had to do two other questions as well, which he did well.
and he was 12 or 13 years old
Also remember that by today's standards, this is a relatively easy problem compared to then. Its about as standard as Vieta Jumping gets, but Vieta Jumping was nearly unheard of back then, which is why this problem is so famous
@@kevinm1317 yeah today it would make a hard p1/easy p2
Terrance Tao won Bronze medal in IMO at age of 11
and I failed to even qualify for National team at age of 15
One of the students who solved the problem, is now the mayor of Bucharest, the city I’m living in
I remember seeing this problem in one of my math sessions disguised as a harmless question
And the whole class was struggling to solve it
Does your math teacher hate u guys lmao
@@4ltrz555 I believe it was the coordinator that gave the question, so the funnier thing is that the teacher didn't know that this was an imo question either
@@kayson971 haha
Same, lmao.
we do a little trolling
It's quite hard to find examples of a and b that satisfy this... One example is (1, 1)
If you take a=b³ those are all the soluzions i think
There are endless number of examples: 1,1;2,8;3,27;4,64;5,125......
Look at the thread I started a few weeks ago. People have posted a lot of insights.
other than setting a = b^3, another set of solutions can be found by setting a = n^2 and k = n^3 where k(ab+1) = a^2+b^2
@Luca Castenetto
Wrong, (0, k) or (k, 0) for all k != 0 is good, too.
Infinity of trivial examples, not following the a = b^3 or b = a^3 rule.
Elegance at its peak...... 🙏🙏🙏🙏🙏
The problem that you'll see in every NT book for math Olympiad.
struggled with the contradiction a bit in the end. the trick is in order for this not to contradict, B^2 must equal k. nice trick!
Me, a 14 years old, suck at math, watching this, having no idea what he's talking about, but its very interesting
This was the second video I watched from this channel and it was a good understandable solution. Just subscribed.
Thanks,author. Please make more content like that(I'm the Russian olympiad participant)
did you participate in imo?
Did you win any medals?
Amazing solution....Loved it..
This method is very interesting! I didn’t expect this setup could lead to a solution. I need to watch again to better evaluate what role “being a perfect square” plays in solving this problem.
I think I figured it out, basically if we twist the problem a bit and assume we are only given that “k is a natural number” and nothing is said about perfect square, we can still find that the solution is actually limited to a specific structure, i.e. k must be B^2 and A must be B^3, as this is the only way this whole thing can hold up.
Thank you for clearing things up, I had no idea how this solution explains k being a perfect square.
@@unemployed5373doeesnt tbis sbow this method is CONTRIVED and not FAIR since no one will think of it..why not soove in qctual ontelligent way ppl will think of??
Thank you very much. this idea is very helpful for my problem that ask me to prove for positve x,y if (x²+y²+6)/xy integer then it must be perfect cubes
There's only one negative integer solution to the equation which is -5. The 8 non reducible sets of a and b are (-1,2) (-1,3) (2,-1) (3,-1) (1,-2) (1,-3) (-2,1) and (-3,1) and with these you can Vieta jump to larger absolute values. Like -5(3) - (-1) yields -14,3
Very interesting number theory problem.
Excelente bro! me gusta que pongas los subtítulos en español! Ganaste un suscriptor :)
7:29
Why does this cobtradiction arises because of k not being perfectly squared?
If k was a perfect square then it would be
A1> or =0 so A1
Then B^2 - k =0
@@anshumanagrawal346 if k not being a perfect square leads to a contradiction then k being a perfect square must not lead to a contradiction. The contradiction is a2
@@opusmagnum-u2p 4:50 from this term we can see if B^2-k = 0 then A1=0, which is not a natural number, which does not lead to a contradiction at the end since A1 is never valid as a solution, in the actual solution A1 leads to contradiction because A1 > 0, which contradicts to the assumption "(A+B) is minimal"
Yaa man you can assume k as not a trangular number and with the contradiction you can prove that k is a trangula number.
for those who totally confused: there is only two case where the divisibility is possible: 1. a or b is zero, but only one of them. 2. a=b^3 or symmetrically b=a^3. The solution in this video explains why these conditions must be. Although the conditions are not mentioned in the video, we can see that k must be equal to b^2. and the rest is the conditions...
The pairs of integers that fit the equation are x^(2n-1) - (n-2)x^(2n-5) + T(n-4)x^(2n-9) - TT(n-6)x^(2n-13) + TTT(n-8)x^(2n-17) - TTTT(n-10)x^(2n-21) + ... where T(n) is the triangle number TT(n) is the triangle number of the triangle numbers and TTT(n) is the triangle number of the triangle numbers of the triangle numbers and so on. If you substitute n = n - 1 you get the other pair and if the power becomes negative you stop the formula. So if n = 11 you get a=(x^21 - 9x^17 + 28x^13 - 35x^9+15x^5- x) b= (x^19 - 8x^15 + 21x^11 - 20x^7 + 5x^3) cause T(11-4)=28 TT(11-6) = 1+3+6+10+15 =35 TTT(11-8) = 1+1+3+1+3+6=15 TTTT(11-10) =1 and T(10-4)=21 TT(10-6)=1+3+6+10=20 TTT(10-8) = 1+1+3=5. All the coefficients add to either (1,1) (1,0) (0,1) (0,-1) (-1,0) or (-1,-1) so that x = 1 will result in 1.
from where did u get all these?
@@spiderjerusalem4009 proof by intimidation, write a whole bunch of mathematical jargon no one can read, and no one will doubt your proof
@@victory6468 the jargons are comprehensible. It's just the derivations, where it came from were utter vague
By the same solution we can prove that the all couples (a,b) satisfaying this property are ( a , a^3 ) and ( a^3 , a ) for all integer a . It is more general solution, on particular when we calculate the ratio for this only case we find a^2 wich is perfect square.
Thank you for such a nice work , all my Support ❤️
Such a cool proof, thanks!
A nice trick is to quickly abuse symmetry and transform this into symmetric polynomials form. Then it becomes a lot easier but still hard to solve without the hell a lot of ring theory
Dude, my college professor posted on his facebook page your video here. Glad I was able to find a simpler proof of this problem
Surely a^2 is a square if u look st it geometry wise, and b^2 is a square. Ab+1 is a length of an+1. If you divide the square a length, your just scaling the square down .
A very clear explanation👍
How do we know that A, the root, is an Integer, i.e. a non floating point number in proof that A1 is in Z?
Also, that A1 is >0 comes from A1B+1>0 A1>(-1)/B which gets us A1>(-1) since B is an Integer. Since we just showed that A1 is a whole number and we assumed for our proof by contradiction that A1 /= 0, otherwise k would be an Integer square, A1 has to be in IN/0. Therefore A1>0.
Feel like you not only skipped a lot of steps there, but also presented them in a wrong order.
If ab+1 divides a^2+b^2 then b^2=a/b (it is simple: divide (a^2+b^2) by ab+1 and to make the rest=0 it is necessary b^2=a/b)
Then b^2=a/b --> b^3=a. ----> substituting in (a^2+b^2)/(ab+1) --> (a^2+a^6)/(a^4+1)=(a^2(a^4+1))/(a^4+1)=a^2.
Long division "divisibility" works on polynomials, you're confusing divisibility on every a, b and divisibility on specific a, b
Also, don't you think it's a problem if you get a result like that since, by symmetry, you could conclude b=a^3 and so a=b=1 only solution? (btw you can easily see (2, 8) is another solution)
I am not able to find the condition b^2=a/b. By dividing a^b+b^2 by ab+1 the rest is a^2-a^2b-a+b^2. Now how do you elaborate on a^2-a^2b-a+b^2=0 to get that there must be b^2=a/b. Thanks
Just to express differently ... (a^2+b^2)/(ab+1)=k, where a,b,k all pos integers.
So need k*(ab+1)=kab+k to equal a^2+b^2.
Hence need (1) kab=a^2 i.e. kb=a and (2) k=b^2.
Substituting in for k in eq1, then kb=(b^2)*b=b^3=a.
With a=b^3 we substitute and simplify:
a^2+b^2 =b^6+b^2 =(b^2)*(b^4+1)
ab+1 = b^4+1
So ratio = b^2 = k.
Done.
Perfectly done, thank you.
Sometimes I think it is even harder to come up with a theorem like this...
Yes. It is
From your proof, we can strengthen the statement by replacing a perfect square with b^2, right?
Edit: It also need to add an assumption b
No it’s not b^2. For example (8,30) is a solution which equals 4, which is not the square of either input
We only know that for sure if a+b is mimimal
if a+b is minimal then we can strengthen the statement by replacing a perfect square with b^2
hey please check this solution a²+b² can be written as (a²+b²)(1+ab) - ab(a²+b²) and as (1+ab)|(a²+b²) then ab(a²+b²) should be equal to zero In case 1, when a² + b² = 0, the expression (a² + b²)/(1 + ab) simplifies to 0/(1 + ab) = 0, which is indeed a perfect square.
In case 2, when ab = 0, the expression (a² + b²)/(1 + ab) simplifies to (a² + b²)/(1 + 0) = (a² + b²)/1 = a² + b². Since ab = 0, it follows that a² + b² = (a + b)², which is a perfect square.
Therefore, based on these two cases, it can be concluded that for any values of a and b, the expression (a² + b²)/(1 + ab) is always a perfect square.
you just showed that it works if a = 0 or b = 0, not for any case
Your first step is wrong. You can only say ab(a^2+b^2) is divisible by ab+1, not that it is zero. For example 2|8, but 8=(8)(2)-1(8), but 8isnt 0.
@@ostdog9385 i am already wrong just fun see the divisor must be greater then the remainder that is 1 + ab > -ab(a²+b²)
This equation satisfies only if A and B are perfect squares when substituting to that equation will result to a perfect solution😊
I enjoy your videos but I am very curious about seeing things in the flesh so I was curious as to what numbers actually satisfy this condition. It took me about 10 seconds to write a line of maple code to produce the results and it is interesting to see that any two numbers x and x cubed will satisfy the conditions for a and b
The only pairs less than a thousand which also satisfy this condition are
(30,8)...(112,30)...(240,27)...(418,112)
This channel will get 1 million by December 2021
i dont know a lot on how to solve these type of questions or how these even work rather but heres how i solved,please just tell me if im wrong anywhere(i certainly will be)
let us assume
a^2+b^2/ab+1=p where p is a natural number is not a square ----(1)
ab+1/a^2+b^2=y which is a natural number
ab+1=(a^2+b^2)(y)
(a^2+b^2)(y)/(a^2+b^2)=p
1/y=p
y=1/p
but according to (1) p is a natural number but i/natural number is not a natural number
therefore our assumption is false and p is a square number
Sir my answer firstly distributed ab +1 in a^2+b^2 take a>=b so a^2 greater than ab +1 so if we divide than remainder will be -a/b and if we divide b^2/ab+1 remainder will be b^2 net remainder will be zero -a/b+b^2=0 so a=b^3 if we put this value in expression we got b^2 which is perfect square ... Thank you I am from india
really...??
remainder is not -a/b......or how?
Your solution is not correct
I am reading comments that say, 'I couldn't solve this when I was 13', 'when I was 15' etc.
I can proudly and truthfully say that I never failed to solve this problem ever ! ))
That's soooo cool
Thank you!!
Hi prithuj :)
What does ab+1 | a²+b² mean ? Why we are using vertical line between two equations?
ab+1 divides a²+b²
What does that mean? Are you saying that the statement is postulating that you can evenly divide a^2 +b^2 by ab+1 with no remainder?
5:41 what if B was negative? Than if A1 is negative we're going to end up having positive denominator and, thus, k is positive as well
A and B are both natural numbers, so B can't be negative
The question states that a and b are strictly positive integers
If we assume that A=B then we have
k=(2A^2)/(A^2+1) this is less than 2, which forces our k to be a positive integer less than 2, this is k=1 which is a perfect square. So it is better to assume either A
The proof was based on the case where a + b is the minimal being assumed. What about the rest of the cases where a + b is not the minimal ?
This uses a proof by contradiction, where you assume that (a²+b²)/(ab+1) is not a perfect square, then you draw a contradiction from the initial assumption. In this case, we proved that there is no minimal solution that equals a non-square. Since a and b are in the natural numbers, this effectively proves that there are no solutions at all which equal a non-square. This doesn't only prove a minimal case, it proves that all the cases must lead to a perfect square.
We didn't _assume_ a+b was minimal. We chose se (A,B) such that it gave minimal A+B as we know _a_ pair giving minimal sum must exist because there is always a minimum value in a list of integers (the list of A+B here) Then we showed that there exists a pair that gives an even smaller sum which is impossible since we chose the pair which already
had the lowest possible sum. Therefore a logical contradiction happened and so some assumption must have been wrong. There was only one that k wasn't a perfect square. So k must be a perfect square.
The existence of a case where a+b is minimal isn't assumed as there always exist A,B satisfying that.
Since only the existence of (A,B) is necessary here, we are fine
@@pbj4184 Really good explanation, the key here is that choosing the minimum solution is what leads to the contradiction later. The minimum solution isn't one case that was checked, but it proves every case.
@@kenthchen Something true must work for all cases. So if it doesn't work for the case where A+B is minimal, it isn't true. And since k can only either be perfect or non-perfect square and we showed it cannot be a non-perfect square (as that leads to a contradiction), it must be a perfect square.
@@pbj4184 sir can you please explain me the basis of assumption @4:58
"That since k is not a perfect square
Surely A1 is not equal to 0
So yay we are done :D
Nice explaination!
Vieta jumping is the elegant solution, but the others guys who solved this problem with which solution did it? 🤔
most probably all of the people who got a 7 did vieta jump
@@prithujsarkar2010 nah, numberphile said only one solved that problem perfectly
@@wayneyam1262 I don't think so, if you search in the IMO web site, there were people who got 42 but only one guy got a special prize :p
@@Miguel-xd7xp And that guy did it this way :)
Why does the proof by contradiction imply that the assumption about k not being a perfect square is false? It could also imply the assumption about k being a natural number is false. Why is the proof sound?
BTW contrary to the popular belief that nobody could solve it actually there were 2 or 3 students who got 7 and 8 out of 8. Numberphile had mentioned this.
May I ask how to make sure A1 is a positive number?
I posted a comment about this. Hope it helps
Can anyone explain what is the relation between the assumption that k is not a perfect square and the minimality of the roots?
k not square was used to deduce that A1 is not zero, and hence positive by a later argument. Minimality of roots is a fancy formulation of induction. Having (A,B) a solution, it is shown that (A1,B) is a smaller solution which is a contradiction assuming that (A,B) is a minimal solution. Here, positivity of A1 is needed so that (A1,B) is a proper solution. In other words, the Vieta jumping produces smaller and smaller roots, hitting zero at some point. But hitting zero is only possible if k is square.
the root A_1 = (B²-k)/A. k not being square means that can't vanish
How can we know that A1 is an integer
why can you conclude k is a perfect square? you just proved that for every k there is only one satisfying set
The case of the repeated root would require A^2 = B^2 - k since it would be when A1 = A (the same equation used in the proof in the video), but k = B^2 - A^2 is only positive when b>a, which is false by assumption.
how do you know its an integer
I found an easy solution, but of course there must be something wrong with my assumption.
a^2+b^2 = k (ab+1)
a^2+b^2 = kab + k
Then I consider !!!
a^2 = kab
b^2 = k
So k=a/b and k=b^2 and thus a = b^3
Substituting (b^6+b^2)/(b^4+1) = b^2
Which is a perfect square
Hope that you can comment on this solution.
How is that possible as k cannot be equated to b^2 as we didnt prove k is a perfect square ,the main motive is to prove k is a perfect square so we cannot assume it
@@sinistergaming1418 it doesn't really assume that k is a perfect square
a+b
------ = n
c+d
if a/c =n
Then b/d also equal n
9+18
-------- = 3
3+6
9/3=3,18/6=3
27/9=3
This is how division and ratio works, since we have unknowns, it's safe to say a²/ab = k, and same with b²/1= k
Although there will be times where the solution isn't like this, so i guess this is just possible answers
What i find interesting are the answers I find: a and/or b = 0, or a = b^3, or a^3 = b, and that seems to be it.
Would be sweet to proof this thing by showing, that these are the only solutions possible, because then it easily breaks down to k=b^2 (respectively k=a^2)
There might be a way to show this in a way, that any prime factor that is in a must also be in b and vice versa and once you are there, then conclude that the exponent must be exactly 3.
Unfortunately only some of the solutions are of this form. Take for example a=30, b=8.
@@vindex7 thanks for pointing this out.
@@vindex7 Yep, I'm finding 30, 112 and 27, 240 as well. As 8 and 27 are both cubes I suspect 8, 30 and 27, 240 are related. But 30,112 is a mystery.
I found this: Let (a, b) be any solution pair with a>b and let s = (a^2+b^2)/(ab+1). Then another solution can be derived by creating solution pair (s*a-b, a). So if we start with a trivial (a,0) solution then that generates (a^3, a). Then from (a^3,a) we can generate (a^5-a, a^3) as another solution. And of course we can keep going to generate larger solutions.
Turn on postifications
Exelente razonamiento. Muchas Gracias.
Why would we assume A+B is the minimum in the proof? Without the assumption that A+B is minimal, shouldn’t the Vieta formula still hold true? Then you just found another solution, A1, B to the original equation, but you have nothing to contradict with. (Just for my understanding)
Exactly my doubt
In the end contradiction may not hav been due to taking k is not perfect square
It may have been due to A+B Not being minimal ....
Why can't the contradiction arise for perfect square k?
I'm sorry is this related to phytarean triples? It doesn't seemed to be.
why did not predict the that a perfect square is positive number like 0 greater rather than just tell it a perfect squareroot
Why the contradicción say that k has to be a perfect square?
4:36 How are A,B (the minimum roots of the equation) known to be integers?
It's not like that.
The problem is claiming that ALL natural solutions also happen to produce a perfect square.
So the guy says let's say we find a solution that meets all the criteria a,b are naturals and that those two expressions divide. Suppose we find a solution and not just any solution we find the smallest solution. Which of course there will be.
Assume we have the smallest solution that is NOT a perfect square then this proofs shows if that were the case you could always make a smaller one..which is a contradiction. Therefore, it must be a perfect square.
Thank you!!!!!!!!!!!!!!!!!!!!
6:01 im confused, what if A1 and B are both negative? also how does it being positive tell us its an integer?
not sure how you got A1+B > 0
Since A1 = kB - A, where k, B, and A are all integers, we know A1 is an integer.
We know A1 = (B^2 - k) / A by Vieta's formulas. Since B is an integer, and we are supposing k is not a square, then B^2 - k ≠ 0, so A1 ≠ 0.
Combining the above two results, we know that A1 is a non-zero integer.
We know (A1^2 + B^2) / (A1 * B + 1) = k > 0. Since the numerator A1^2 + B^2 > 0, then this quotient is only positive if the denominator A1 * B + 1 is also positive.
A1 * B + 1 > 0 implies A1 * B > -1. We know B > 0 since it was defined that way when setting up the problem. We know from above that A1 ≠ 0. Since A1 and B are integers, their product can't be between -1 and 0. So A1 * B can't be less than 0 (-1, -2, -3, ...) and it can't be 0, so it must be greater than 0.
Well I solved it in few minutes and astonishingly my solution was also correct...
Can I send it to someone to verify it????
Sir I don't understand any thing what should I do to understand this solution I mean any basic available
I did it(vieta jumping),Andromida and milkiway,cassiopeia
Why people made this so complicated?
Obvious (ab+1) must be greater or equal to (a^2+b^).
If (a^2+b^2) is greater than (ab+1), the result of (ab+1)/(a^2+b^2) is less than one.
(ab+1)>=(a^2+b^2), both side minus 2ab, then we have
(1-ab)>=(a^+b^2-2ab)=(a-b)^2, which is greater or equal to zero.
Then, we have (1-ab)>=0, it implies 1>=ab,
since both a and b are positive integer, the only solution is a and b equal to 1.
(a^2+b^2)/(ab+1)=(1+1)/(1+1)=2/2 = 1, which is perfect square.
Is it a primary school mathematics?
if q | r and q and r are integer, then q
@@alainsavard8147 if q | r, q & r are integer, then q >= r. according to wikepedia.org, "|" is divisible. If q is divisible by r, q should be greater than or equal to r. Otherwise, if q < r, q/r is a fractional number.
@@Alan-dg6io q | r means that "q divides r".
I wonder where the assumption "(A + B) is minimal" is used in the proof ? What if we did not assume (A + B) to be minimal ?
"(A + B) is minimal" is used in the very last part to create contradiction, in this solution whenever we assume a non-perfect square k which has a minimal solution (A + B), we can always find an even smaller pair (A1 + B), which is supposed to be invalid, which proves that the assumption was invalid at start, therefore proved the actual problem
I really like your accent, that stereotypical Asian accent (I mean it in a good way, I'm not being racist, I'm Asian too) makes me much more comfortable dunno, if I'm the only one
Why can he just state A,B are minimal, does he not gave to prove they exist with example?
Bro has proved hardest imo problem by contradiction
Can this be done via Mathematical Induction?
probably not
Wow nice one
Awesome😀
yo mendel
Yeah
Those 11 students , 🤯🤯
Wow so good teacher I will teach my students the same to you
Because your skill is very nice
Why you got that A >= B
I thought that the vertical line was the C computer language “or” operator 😅
where is the fact that k is not perfect square be applied??? can also the proof in the video be applied when k is perfect square so that k cannot be an integer???
*And I thought my handwriting was bad!*
really good
Thank you!!
Very nice. 👍
How did you assume that A1=(B^2-k)/A belongs to N (natural numbers)? Without proving any sort of relation between B^2 and k, we cannot plug in A1 in the original equation. Just because A1 is not 0 and it is an Integer, we cannot plug it into the original equation. We have to prove A1 is a natural number.
a²+b²=k(ab+1)
b²-k = a(bk-1)
I must please ask for help on this problem !
the sequence a(n) is defined like this:
a(n) = a(n-1) / 5 , if a(n-1) is divisible with 5 or
a(n) = [a(n-1) * sqrt(5)] , otherwise. ( [x] is the floor function ) , with a(0) being a natural number , not equal with 0.
Prove that this sequence contains only a finite number of terms divisible with 5 .
If both a(n) and a(n+1) are not divisible by 5, then a(n+2) is roughly 5a(n), but a little bit smaller. More precisely,
0
Okay, there must be some values of a and b when divides by ab+1 gives you a 0 remainder. Okay. Please provide some samples.
Can u prove that k=gcd(a,b)² pls. This one was given to us by teacher and till this day I still have no clue how to do it. Only thing I know is this use strong induction.
You can google "IMO 1988 Problem 6 Induction". The first or second result is a pdf containing the solution you're talking about
@@pbj4184 thx
This must be the case for special case of perfect numbers like phytagorean triples but I think k must be written as k^2.
And is it possible when this eq is a perfect square? I don't see we used that k is not a perfect square
we used it when we argued that B^2 - k can't be 0, and that is exactly because we assumed k is not a perfect square.
Couldn't A1 = B ? Because if it could, then we don't have a contradiction.
I have proved：
Let a≤b
a is any positive integer
If ab+1 | a²+b² and a is not a perfect cube, then b＝a³.
If ab+1 | a²+b² and a is a perfect cube, then b＝x⁵-x where a＝x³ and x is a positive integer.
How is this so easier than the Numberphile solution?
Do you have the link to the video?
It is less rigorous...
@@dp121273 yes bro I just watched it a few days ago. Will edit the link here...
Edit: ruclips.net/video/Y30VF3cSIYQ/видео.html
Here's the question
ruclips.net/video/L0Vj_7Y2-xY/видео.html
Here's the answer.
@@TtTt-ur5hd How so? It uses some facts he didn't prove but those facts are very easily provable themselves
You did not show that A1 is not negative and nowhere you used the assumption of ab+1|a^2+b^2
a^2 + b^2 = d^2 is granted by pythagoras.
P.S.: That, of course, is nonsense. But i have a biological brain, so this trigger went off, and the anti-trigger "but only if in a right triangle" didn't.
Thus, the rest is sadly nonsense as well (but it looked so nice, you know :D)...
d^2 = c^2 * f has to have both factors on the RHS to be either equal or each square (else the product ends up having one prime exponent uneven, thus being not square).
Equal they cannot be, since f = (a*b + 1) is given, and its square is not equal to a^2 + b^2.
Done.
Bro..i . Do all process same and assume that , k is a perfect square instead of assuming k is not a perfect square.. Still the contradiction occurs... Please explain this. Where do i make a mistake
4:50
A_1= (B^2-k)/A is not equal to 0 comes from the assumption that k is not perfect square. (b^2 is a perfect square, k is not hence k cannot equal to B^2 hence B^2-k is not equal to 0 hence the entire fraction is not equal to 0.) In contrast, if k is a perfect square, then you cannot proceed from here because there is always the possibility that k=B^2 and thus A_1=0 which makes (A_1,B) not a solution to the problem which does not lead to a contradiction.