A very insightful exercise. It's not only about number theory, but also about problem solving and the logic of this kind of contests to tackle the problems more efficiently
3:20 Writing out cubes mod 9 is slightly simpler if, instead of looking at 0 through 8, you consider that 5,6,7 and 8 are -4, -3, -2 and -1 respectively so their cubes are just negative the cubes of 4,3,2 and 1.
It has been proven that, for all integers n, n is the sum of not more than nine cubes. A proof similar to the one seen in the video showing that four is necessary for this value of n shows that infinitely many numbers require four cubes.
@@iang0th Yes. 23 and 239 are the only such numbers. See www.ams.org/journals/bull/1939-45-08/S0002-9904-1939-07041-9/S0002-9904-1939-07041-9.pdf for the first proof (Dickson, 1939).
Note that 23=2³+2³+1³+1³+1³+1³+1³+1³+1³. All of those are needed, since there is no integer between 1 and 2, and 2³+2³+2³=24 is too big. Note also that 2³+2³+2³+(-1)³=23, so it is strictly necessarily to ask for NON-NEGATIVE cubes (something omitted in Darrel Jones' comment above).
@@leif1075 Taking a modulo is a very common technique in these types of problems. The part I found random is, how do you know that mod 9 would yield something useful. I guess it's just a lot of practice and good intuition.
@@stewartzayat7526 but i don't think mod is common for everyone.well actuallyI know it'snit...why not factorize 2002..cant you solve like that? Breaking it into 2 times 7 times 11 times 13 and see what works??
@@leif1075 These IMO problems are "real" problems in the sense that they require a lot of exploration, you dont come up with a method just by looking, you have to try out several things before finding the right approach. Thats the nature of contest math, is not about knowing super technical stuff, it is about exploring possibilities and being imaginative. If you look at research math this feeling of "htf would anyone think of this" is quite common. The point is that, in the paper you see, all those failed attempts are cleaned up and you look only at the final product. The process of arriving at that involved a lot of trial and error attempting the problem from different angles and making small ajustments.
@Parthsarthi Singh hello sir, it’s easy… if the equality is div by 2, then u can let a=2m+n and b=n, and c=r-s and d=2s, then u can divide by 2 and get r^2+5s^2=2m^2+2mn+3n^2… Then we can repeat until it’s not div by 2… Then if the eq is div by 5, we can let a=5s and b=r, and (since 2c^2+2cd+3d^2=2(c-2d)^2 mod 5) let c=2n-m and d=n+2m, then u can divide by 5 and get r^2+5s^2=2m^2+2mn+3n^2… Then we can repeat until it’s not div by 5… But then u can show that the LHS is only 1 or 9 mod 20, while the RHS is only 3 or 7 mod 20… so the only possibility is a=b=c=d=0… correct…?
Actually the key is to find a number such that phi(n) = 6, then any number a**6 = 1, and a**3 = 1 or -1 mod n. Possible n = 7 or 9. But 2002**2002 = 0 mod 7 and 2002**2002 = 4 mod 9. So smallest solution is 4 = 1+1+1+1.
yes -- and even can skip the figuring out anything mod 6, because 4^3 is 1 mod 9, we immediately have that 4^2001 = (4^3)^667 is also 1 mod 9, so 4^2002 is 4 times that
Impressive, as usual. I really enjoy your videos. I know you like to send your videos with "and this is a good place to stop", but in many of your videos I would actually love to see a bit of discussion of the problem after that point. For example in this video: (1) why did you choose to work mod 9? What would have happened if you'd chosen to work mod some other number? What would have gone wrong? What is so special about 9 in this context? (2) Is the repetition of 0, 1, -1 in the cubes mod 9 a coincidence? Could be a homework question. (3) What would have happened if the question used 2001 or 2003 instead of 2002? Would the same technique work, or is there something special about the number 2002? (4) What would have happened if the question asked for squares or fourth powers instead of cubes? To what extent does the argument hinge on being asked for sums of cubes?
If the question asked for 2001^2001, the number would have been a cube (since the exponent, 2001 is obviously divisible by 3, since that's the sum of its digits), which immediately yields the simple solution 2001^2001 = (2001^667)^3 => m=1 (trivial)
without knowing the trick for reducing the exponent to phi, it's still not too bad! since we know 4^3~1 mod 9, so finding 2002=3*667+1 gets you 2002^2002~4^2002=4^(3*667+1)~4
An easier way to calculate 2002^2002 mod 9: it's 4^2002 mod 9, but that's 4*4^2001 mod 9, or 4*(4^3)^667 mod 9, but as already established, 4^3 is 1 mod 9, so we have 4*1^667 = 4 mod 9.
Almost surely. Deshouillers, Hennecart, & Landreau conjecture that every number greater than 7373170279850 can be written as the sum of four distinct cubes (the amusing title of their paper is 7373170279850).
@@CRGreathouse Are you sure they conjectured distinct cubes? There is no mention of this in their paper, compare citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.101.2850&rep=rep1&type=pdf
They also clearly don't make the distinction in the introduction, giving the example of 23 that requires 9 cubes (one of only two numbers that does, as shown in 1939). The representation is 23=2³+2³+1³+1³+1³+1³+1³+1³+1³. Note also they ask about non-negative cubes specifically, as 23=2³+2³+2³+(-1)³, which is more strict than what is asked in the video.
@@renerpho No, sorry, you're right. But you can still get the finiteness result (if not the explicit bound) from the general conjectures on the growth of the number of representations as the sum of four cubes.
@@CRGreathouse It is almost certainly possible to do it with distinct cubes, for all numbers above some point. Notice that the sum of all cubes up to a number n grows as a fourth power, while the number of subsets of a set with n elements is 2^n. 2^n grows much faster than n^4 even for small n, and n=2002^2002 is a very large number. That's not a proof, of course, and putting a bound on how many distinct primes you need is a different question. My guess is that it can probably be done with four.
My lucky guess: 2002^2002 = 2002 * 2002 ^ 2001 = 2002 * (2002 ^ 667) ^ 3 so if x1, x2, ... xn are all equal to 2002^667, then we have 2002 terms :) Looking at the video, I guess I only missed that 2002 can be split into 4 cubes. Nice problem anyway.
HOMEWORK : A certain high school has exactly 1000 lockers, numbered from 1 to 1000, all initially closed. Mark first opens every locker whose number has exactly 3 factors, starting with locker 4. Matt then opens every locker whose number is a power of 2, starting with locker 1. If Matt encounters a locker that Mark has already opened, he leaves it open. Compute the number of lockers that will be open when both Mark and Matt finish. SOURCE : Rice Math Tournament 2015
None of the powers of 2 except 4 has 3 factors, so only locker no 4 is the only common case between mark and matt. Numbers with 3 factors are perfect squares of a prime number.🙂
20 There are 10 powers of 2 less than a 1000 (including 1), so that's easy to check Next, if a number has exactly 3 factors, it must pe the square of a prime. The largest prime whose square is less than 1000 is 31 (32²=1024) and there are 11 such primes. Out of these, 2² has already been counted. So 20.
SOLUTION *20* Numbers with exactly three factors must be squares of primes (so the factors are 1, p, and p²). Between 1 and 1000 there are 11 such numbers: 2², 3², 5², 7², 11², 13², 17², 19², 23², 29², 31². Furthermore, there are 10 powers of 2 between 1 and 1000: 2^0, 2^1, ... 2^9. The number 4 is in each list, so there are a total of 20 distinct lockers that Mark and Matt will open.
I suppose if you had other equation with x^x = 5 mod 9, you would claim m >= 5, but it’s possible to use 4 cubes (= -1 mod 9) with the sum of them = 5 mod 9 However, that doesn’t matter for the original problem 2002^2002 :)
I would do something like this: Since 2002 = 4 mod 9, then 2002^2002 = 4^2002 mod 9 And since 4^3 = 1 mod 9 4^2002 = (4)(4^3)^667 = (4)(1) mod 9 = 4 mod 9
When you are looking at a^b (mod n), there's a theorem that it equals (a mod n) ^ (b mod φ(n)) (mod n) where φ is the Euler Totient Function which is the number of positive integers less than n which are relatively prime to it. So for instance, 1, 2, 4, 5, 7, and 8 are the positive integers less than 9 that are relatively prime to it, so φ(9) = 6. Therefore 2002^2002 (mod 9) = (2002 mod 9) ^ (2002 mod φ(9)) (mod 9) = (2002 mod 9) ^ (2002 mod 6) (mod 9) = 4 ^ 4 (mod 9) = 4 (mod 9)
For the 2002 in the base he used the curious fact (which I didn't realize until today) that n has the same residue mod 9 as the digit sum of n (i.e. 2564 (mod 9) = 2+5+6+4 (mod 9)). For the 2002 in the exponent he used Euler's generalization of the Fermat's Little Theorem, which states that a^b (mod n) = a^(b (mod phi(n))) (mod n), where phi is Euler's totient function.
@@stewartzayat7526 On a tangent an old accounting trick is "casting out nines", which is basically taking advantage of the fact that the sum of the digits of a number is its residue mod 9. When you want to quickly spot check adding or multiplying a bunch of numbers you can "cast out" all the 9s and any digits that sum to 9 and total up the rest. If the totals add up (mod 9) then that's a decent sanity check you got the right result (if there's an error it's only a 1/10 chance it'll slip through). en.wikipedia.org/wiki/Casting_out_nines
I would start with 2002^2002==2002*(2002^667^3) (last minute of the video) . Then to decompose 2002 into sum of cubes can be done by trial and error. One would obviously start with 10^3, the largest cube that fits into 2002. Now one just needs to prove that no 2 or 3 cubes sum up to 2002, minimum is 4. Proof for 2 is easy: cuberoot of 2002 is 12.6..., so one needs to only worry about 11 and 12. It can be easily checked that neither works. Proof for 3 is a little more work, but it can also be proven by listing and eliminating all the possible candidates. Since 2002/3=667.333..., at least one of members of the sum must be >=668 (otherwise we come up short). Only cubes of 9, 10, 11 and 12 are >=668. They can be all tried one at a time. A clever child with no knowledge of Euler or Fermat could solve this nice problem.
In your approach, you suggest that all number of the sum have a factor of 2002^(667*3), but nothing tell us that it has to be the case. So you still have to proof that the minimum is indeed 4. That being said, I think that the initial exploration of the problem would look like what you propose for many people. And after having found that a sum of 4 cubes works, the work with modulo start to proof that it is indeed the smallest number of cubes possible.
@@SylvainBerube I am saying that the cases 1, 2 and 3 can be proved as impossible by evaluating all possible combinations. There are not that many, it is doable, by hand.
@@cernejr Yes I understand that it is possible to prove "by hand" that 2002 cannot be expressed as the sum of 1, 2 or 3 cubes, I agree with you on that. But this is not the same thing as proving that 2002^2002 cannot be expressed as the sum of 1, 2 or 3 cubes. For example, 3 cannot be expressed as the sum of 1 or 2 cubes, but 3^3 clearly can. Something similar could occur for 2002^2002 (it turns out that it is not the case, but we have to prove it).
@@SylvainBerube I think the point made in the video is that no matter what number you cube mod 9 has only -1, 0, or 1 as residues . So adding these together you need at least 4 to get to 4.
If you have dealt with a lot of cubes in number theory problems, you'll almost certainly consider modulo 9. Similarly, for squares you think of modulo 8 and for fourth powers you think of modulo 16.
I think the key insight is that 2002 = 3 * 667 + 1 and thus 2002^2002 = (2002^667)^3 * (2002) which leads one to hope that one can express 2002 as a sum of a few cubes (in this case a sum of four cubes). Now that we have 2002^2002 expressed as a sum of 4 cubes, it is required only to show that it cannot be expressed with 3 or less cubes. Allowing 0^3 as a possibility, we want to rule out 2002^2002 = a^3 +b^3 + c^3. At this point, using mod is a standard technique to show that such an equation is impossible.
@@billh17 So are you agreeing mmy method of factoring 2002 works or not? I broke itndown into its prime factors none of which is 3..doesnt this way work.seeing if you cam break the terms into 2,7, 11,13, since those are the factors of 2002.i don't see why the fuck anyone would think of 3..unless because they are all cubed..
@@leif1075 I also wish to mention that there is no guarantee that considering 2002^2002 = 2002 * (2002^667)^3 will lead to the smallest value of m since this approach implies that all the x's are divisible by (2002^667)^3 which need not be true. However, it does lead to a significant decrease in the maximum value of m since we only need to consider how to express 2002 as a sum of m cubes (seeking m to be minimum). But that minimum may not be the minimum for the proposed question.
No, that's like saying "there are more than 10 people on the Earth (which is true), therefore there are 10 people on the Earth (which is false)". Your implication is incorrect.
It only shows that they are congruent mod 9, not that they are equal. 9 is congruent to 27 mod 9, but they aren’t equal. But to have equality, you have to have congruence. So he was just showing to have congruence you have to have m be at least 4. From there he had to prove equality.
We can stop to m>=4 if the question was : find a lower bound for m, but here we need the smallest m, in fact it's equivalent to find the highest lower bound. So when we have m>=4 we need to check if it is the highest lower bound by finding 4 numbers such that the sum of their cube is 2002^2002
Thank you all for the answers! What I was thinking is that, when you show that x1+x2...+xm must be congruent to 4 mod 9, and you show that x1,x2...,xm€{-1,0,1} mod9, doesn't that imply m=4? Because the smallest m such that if you add numbers in that set you get 4 is exactly 4.
Thumbnail: shorlist
Description: shotlist
Video: shortlist
At *list* one of them is correct (like my answers)
No misteak here, just happy little accidents
@@goodplacetostop2973 Black pen red pen
He’s a math professor not an English one.
A very insightful exercise. It's not only about number theory, but also about problem solving and the logic of this kind of contests to tackle the problems more efficiently
3:20 Writing out cubes mod 9 is slightly simpler if, instead of looking at 0 through 8, you consider that 5,6,7 and 8 are -4, -3, -2 and -1 respectively so their cubes are just negative the cubes of 4,3,2 and 1.
I noticed that, too. I've removed my original comment as redundant.
Even an easier method, from Euler-Fermat if gcd(x,3)=1 then x^6==1 mod 9 hence 9|x^6-1=(x^3-1)*(x^3+1) so x^3==+-1 mod 9.
It has been proven that, for all integers n, n is the sum of not more than nine cubes. A proof similar to the one seen in the video showing that four is necessary for this value of n shows that infinitely many numbers require four cubes.
Has an example of a number requiring nine cubes been found?
@@iang0th Yes. 23 and 239 are the only such numbers. See www.ams.org/journals/bull/1939-45-08/S0002-9904-1939-07041-9/S0002-9904-1939-07041-9.pdf for the first proof (Dickson, 1939).
Note that 23=2³+2³+1³+1³+1³+1³+1³+1³+1³. All of those are needed, since there is no integer between 1 and 2, and 2³+2³+2³=24 is too big.
Note also that 2³+2³+2³+(-1)³=23, so it is strictly necessarily to ask for NON-NEGATIVE cubes (something omitted in Darrel Jones' comment above).
Ok, this was impressive.
Why the fuck would anyone think of mod at all..how is it impressive..just random really to me..
@@leif1075 Taking a modulo is a very common technique in these types of problems. The part I found random is, how do you know that mod 9 would yield something useful. I guess it's just a lot of practice and good intuition.
@@stewartzayat7526 but i don't think mod is common for everyone.well actuallyI know it'snit...why not factorize 2002..cant you solve like that? Breaking it into 2 times 7 times 11 times 13 and see what works??
@everyone
squares -> take modulo 8
cubes -> take modulo 9
fourth powers -> take modulo 16
Yes, this is from experience.
@@leif1075 These IMO problems are "real" problems in the sense that they require a lot of exploration, you dont come up with a method just by looking, you have to try out several things before finding the right approach. Thats the nature of contest math, is not about knowing super technical stuff, it is about exploring possibilities and being imaginative.
If you look at research math this feeling of "htf would anyone think of this" is quite common. The point is that, in the paper you see, all those failed attempts are cleaned up and you look only at the final product. The process of arriving at that involved a lot of trial and error attempting the problem from different angles and making small ajustments.
That moment when you realise that 2020^2020 would have same remainder mod9
9:38 Happy July 4th to the people at The Overlook Hotel 😉
@Parthsarthi Singh I’m not Michael bro 😂 Use the form in the video description to submit the problem
@Parthsarthi Singh hello sir, it’s easy… if the equality is div by 2, then u can let a=2m+n and b=n, and c=r-s and d=2s, then u can divide by 2 and get r^2+5s^2=2m^2+2mn+3n^2… Then we can repeat until it’s not div by 2…
Then if the eq is div by 5, we can let a=5s and b=r, and (since 2c^2+2cd+3d^2=2(c-2d)^2 mod 5) let c=2n-m and d=n+2m, then u can divide by 5 and get r^2+5s^2=2m^2+2mn+3n^2… Then we can repeat until it’s not div by 5…
But then u can show that the LHS is only 1 or 9 mod 20, while the RHS is only 3 or 7 mod 20… so the only possibility is a=b=c=d=0… correct…?
@Parthsarthi Singh ok u knew the answer but u want Michael to answer? I understand
Actually the key is to find a number such that phi(n) = 6, then any number a**6 = 1, and a**3 = 1 or -1 mod n. Possible n = 7 or 9. But 2002**2002 = 0 mod 7 and 2002**2002 = 4 mod 9. So smallest solution is 4 = 1+1+1+1.
I'm not very well-versed when it comes to mod and whatnot but your explanations make it super easy to understand!
6:00 (ish) Wouldn't it be even quicker to consider 4⁴ = 4³∙4 ≡ 1∙4 (mod 9) ≡ 4 (mod 9)?
5:58: Even quicker: 4⁴ = 4³ 4¹ ≡ 1*4 = 4(mod 9), as we already have 4³ = 1(mod 9) on the board.
yes -- and even can skip the figuring out anything mod 6, because 4^3 is 1 mod 9, we immediately have that 4^2001 = (4^3)^667 is also 1 mod 9, so 4^2002 is 4 times that
Impressive, as usual. I really enjoy your videos. I know you like to send your videos with "and this is a good place to stop", but in many of your videos I would actually love to see a bit of discussion of the problem after that point. For example in this video: (1) why did you choose to work mod 9? What would have happened if you'd chosen to work mod some other number? What would have gone wrong? What is so special about 9 in this context? (2) Is the repetition of 0, 1, -1 in the cubes mod 9 a coincidence? Could be a homework question. (3) What would have happened if the question used 2001 or 2003 instead of 2002? Would the same technique work, or is there something special about the number 2002? (4) What would have happened if the question asked for squares or fourth powers instead of cubes? To what extent does the argument hinge on being asked for sums of cubes?
If the question asked for 2001^2001, the number would have been a cube (since the exponent, 2001 is obviously divisible by 3, since that's the sum of its digits), which immediately yields the simple solution 2001^2001 = (2001^667)^3 => m=1 (trivial)
How did you think it out to take the modulo of 9?
This problem definitely required some Olympic level leaps. Super cool though!
Wow, that's a real nice solution! :)
With 0, -1, and 1 we can also get 6, 7, and 8, if m is smaller than 4.
without knowing the trick for reducing the exponent to phi, it's still not too bad! since we know 4^3~1 mod 9, so finding 2002=3*667+1 gets you 2002^2002~4^2002=4^(3*667+1)~4
An easier way to calculate 2002^2002 mod 9: it's 4^2002 mod 9, but that's 4*4^2001 mod 9, or 4*(4^3)^667 mod 9, but as already established, 4^3 is 1 mod 9, so we have 4*1^667 = 4 mod 9.
That was another interesting problem. Thank you
Easy to understand solution, but how does one get there?
Can it be done with distinct cubes? How many of them are needed?
Almost surely. Deshouillers, Hennecart, & Landreau conjecture that every number greater than 7373170279850 can be written as the sum of four distinct cubes (the amusing title of their paper is 7373170279850).
@@CRGreathouse Are you sure they conjectured distinct cubes? There is no mention of this in their paper, compare citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.101.2850&rep=rep1&type=pdf
They also clearly don't make the distinction in the introduction, giving the example of 23 that requires 9 cubes (one of only two numbers that does, as shown in 1939). The representation is 23=2³+2³+1³+1³+1³+1³+1³+1³+1³. Note also they ask about non-negative cubes specifically, as 23=2³+2³+2³+(-1)³, which is more strict than what is asked in the video.
@@renerpho No, sorry, you're right. But you can still get the finiteness result (if not the explicit bound) from the general conjectures on the growth of the number of representations as the sum of four cubes.
@@CRGreathouse It is almost certainly possible to do it with distinct cubes, for all numbers above some point. Notice that the sum of all cubes up to a number n grows as a fourth power, while the number of subsets of a set with n elements is 2^n. 2^n grows much faster than n^4 even for small n, and n=2002^2002 is a very large number. That's not a proof, of course, and putting a bound on how many distinct primes you need is a different question. My guess is that it can probably be done with four.
My lucky guess:
2002^2002 = 2002 * 2002 ^ 2001 = 2002 * (2002 ^ 667) ^ 3 so if x1, x2, ... xn are all equal to 2002^667, then we have 2002 terms :)
Looking at the video, I guess I only missed that 2002 can be split into 4 cubes.
Nice problem anyway.
I could have jumped to the answer but love the proof that 4 was the least number.
2002 = 2*7*11*13 = a*b*c*d,say
So the given problem is reduced to partitioning (abcd)^(abcd) into smallest number of cubes
..u may add that x_i need not be distinct ..very impressive again..
You may, but there's nothing saying that they can't repeat, so it's redundant. Although, it would probably make it a little bit clearer.
impressive question
HOMEWORK : A certain high school has exactly 1000 lockers, numbered from 1 to 1000, all initially closed. Mark first opens every locker whose number has exactly 3 factors, starting with locker 4. Matt then opens every locker whose number is a power of 2, starting with locker 1. If Matt encounters a locker that Mark has already opened, he leaves it open. Compute the number of lockers that will be open when both Mark and Matt finish.
SOURCE : Rice Math Tournament 2015
20
20?
None of the powers of 2 except 4 has 3 factors, so only locker no 4 is the only common case between mark and matt. Numbers with 3 factors are perfect squares of a prime number.🙂
20
There are 10 powers of 2 less than a 1000 (including 1), so that's easy to check
Next, if a number has exactly 3 factors, it must pe the square of a prime. The largest prime whose square is less than 1000 is 31 (32²=1024) and there are 11 such primes. Out of these, 2² has already been counted. So 20.
SOLUTION
*20*
Numbers with exactly three factors must be squares of primes (so the factors are 1, p, and p²). Between 1 and 1000 there are 11 such numbers: 2², 3², 5², 7², 11², 13², 17², 19², 23², 29², 31². Furthermore, there are 10 powers of 2 between 1 and 1000: 2^0, 2^1, ... 2^9. The number 4 is in each list, so there are a total of 20 distinct lockers that Mark and Matt will open.
Isn't it strictly speaking the Carmichael totient function?
I suppose if you had other equation with x^x = 5 mod 9, you would claim m >= 5, but it’s possible to use 4 cubes (= -1 mod 9) with the sum of them = 5 mod 9
However, that doesn’t matter for the original problem 2002^2002 :)
What a great problem! A little off the beaten track because cubes so rarely feature in contest maths.
This video messed me up on Christmas night.
Why all the number theory problems always require working in mod N?..
How we ensure that there are no solution for m
If m < 4, the left hand side will never be congruent to 4 mod 9.
@@warmpianist thanks
@@warmpianist im kinda idiot, im always stucking in these easy things
@@kemalkayraergin5655 no worries. Anyone can encounter things like this at some point.
Quite elegant and beautiful. What is why I like arithmetics.
I solved this) damn, I'm so happy
Great!
Are you sure this wasn´t easier and faster using calculus?
Haha I understood but would never be able to come up with any of that
Very nice
That's a good place...
Doesn't Fermat's Last Theorem shows that m>=4?
no because 2002^2002 isnt a cube
How fermats last theorem can demonstrate it
@@bellumthirio139 that seems right
Well, Fermat only tells us n cannot be 7,13 or 11. Not 3 because 2002 is not multiple of 3.
....it should be mentioned not necessarily distinct cubes...
"Fee"? never in a million years. Nice video though, and instructive.
Could you explain the part 2002^2002≡4^4(mod 9) again? Thank you so much!
I would do something like this:
Since 2002 = 4 mod 9, then 2002^2002 = 4^2002 mod 9
And since 4^3 = 1 mod 9
4^2002 = (4)(4^3)^667
= (4)(1) mod 9
= 4 mod 9
When you are looking at a^b (mod n), there's a theorem that it equals (a mod n) ^ (b mod φ(n)) (mod n) where φ is the Euler Totient Function which is the number of positive integers less than n which are relatively prime to it. So for instance, 1, 2, 4, 5, 7, and 8 are the positive integers less than 9 that are relatively prime to it, so φ(9) = 6.
Therefore
2002^2002 (mod 9)
= (2002 mod 9) ^ (2002 mod φ(9)) (mod 9)
= (2002 mod 9) ^ (2002 mod 6) (mod 9)
= 4 ^ 4 (mod 9)
= 4 (mod 9)
For the 2002 in the base he used the curious fact (which I didn't realize until today) that n has the same residue mod 9 as the digit sum of n (i.e. 2564 (mod 9) = 2+5+6+4 (mod 9)).
For the 2002 in the exponent he used Euler's generalization of the Fermat's Little Theorem, which states that a^b (mod n) = a^(b (mod phi(n))) (mod n), where phi is Euler's totient function.
@@stewartzayat7526 On a tangent an old accounting trick is "casting out nines", which is basically taking advantage of the fact that the sum of the digits of a number is its residue mod 9. When you want to quickly spot check adding or multiplying a bunch of numbers you can "cast out" all the 9s and any digits that sum to 9 and total up the rest. If the totals add up (mod 9) then that's a decent sanity check you got the right result (if there's an error it's only a 1/10 chance it'll slip through).
en.wikipedia.org/wiki/Casting_out_nines
@@Bodyknock Does he prove/explain this theorem in one of his videos?
(ln(x)-ln(0.036))/(x-0.036)=5
Find x by two different solution
I would start with 2002^2002==2002*(2002^667^3) (last minute of the video) . Then to decompose 2002 into sum of cubes can be done by trial and error. One would obviously start with 10^3, the largest cube that fits into 2002. Now one just needs to prove that no 2 or 3 cubes sum up to 2002, minimum is 4. Proof for 2 is easy: cuberoot of 2002 is 12.6..., so one needs to only worry about 11 and 12. It can be easily checked that neither works. Proof for 3 is a little more work, but it can also be proven by listing and eliminating all the possible candidates. Since 2002/3=667.333..., at least one of members of the sum must be >=668 (otherwise we come up short). Only cubes of 9, 10, 11 and 12 are >=668. They can be all tried one at a time. A clever child with no knowledge of Euler or Fermat could solve this nice problem.
In your approach, you suggest that all number of the sum have a factor of 2002^(667*3), but nothing tell us that it has to be the case. So you still have to proof that the minimum is indeed 4.
That being said, I think that the initial exploration of the problem would look like what you propose for many people. And after having found that a sum of 4 cubes works, the work with modulo start to proof that it is indeed the smallest number of cubes possible.
@@SylvainBerube I am saying that the cases 1, 2 and 3 can be proved as impossible by evaluating all possible combinations. There are not that many, it is doable, by hand.
@@cernejr Yes I understand that it is possible to prove "by hand" that 2002 cannot be expressed as the sum of 1, 2 or 3 cubes, I agree with you on that. But this is not the same thing as proving that 2002^2002 cannot be expressed as the sum of 1, 2 or 3 cubes.
For example, 3 cannot be expressed as the sum of 1 or 2 cubes, but 3^3 clearly can. Something similar could occur for 2002^2002 (it turns out that it is not the case, but we have to prove it).
@@SylvainBerube Yes, you are correct. Now I got your point.
@@SylvainBerube I think the point made in the video is that no matter what number you cube mod 9 has only -1, 0, or 1 as residues . So adding these together you need at least 4 to get to 4.
Why would anyone think of using mod at all though? Surely you can solve it another way.
If you have dealt with a lot of cubes in number theory problems, you'll almost certainly consider modulo 9. Similarly, for squares you think of modulo 8 and for fourth powers you think of modulo 16.
I think the key insight is that 2002 = 3 * 667 + 1 and thus 2002^2002 = (2002^667)^3 * (2002) which leads one to hope that one can express 2002 as a sum of a few cubes (in this case a sum of four cubes). Now that we have 2002^2002 expressed as a sum of 4 cubes, it is required only to show that it cannot be expressed with 3 or less cubes. Allowing 0^3 as a possibility, we want to rule out 2002^2002 = a^3 +b^3 + c^3. At this point, using mod is a standard technique to show that such an equation is impossible.
@@billh17 So are you agreeing mmy method of factoring 2002 works or not? I broke itndown into its prime factors none of which is 3..doesnt this way work.seeing if you cam break the terms into 2,7, 11,13, since those are the factors of 2002.i don't see why the fuck anyone would think of 3..unless because they are all cubed..
@@leif1075 I don't think factoring of 2002 will lead to m
@@leif1075 I also wish to mention that there is no guarantee that considering 2002^2002 = 2002 * (2002^667)^3 will lead to the smallest value of m since this approach implies that all the x's are divisible by (2002^667)^3 which need not be true. However, it does lead to a significant decrease in the maximum value of m since we only need to consider how to express 2002 as a sum of m cubes (seeking m to be minimum). But that minimum may not be the minimum for the proposed question.
0:10
2002 was the year i was born
Wow man!
My Birthyear!!!
Maravilha
when i see the strategy based on 'because that's how math contests are set up,' i start to think math contests are kinda silly
Regardless, once you know m>=4 it's sensible to look for a solution where m=4 just because it's a high potential reward for little effort.
@@TJStellmach yes, this is true
but outside of math contests you don't reason that it'll pbl work
Wouldn't it be enough to show that, mod9, the smallest m is 4? I mean, you showed that m>/=4. But isn't that a proof that the shortest m=4?
Why would it be?
No, that's like saying "there are more than 10 people on the Earth (which is true), therefore there are 10 people on the Earth (which is false)". Your implication is incorrect.
It only shows that they are congruent mod 9, not that they are equal. 9 is congruent to 27 mod 9, but they aren’t equal. But to have equality, you have to have congruence. So he was just showing to have congruence you have to have m be at least 4. From there he had to prove equality.
We can stop to m>=4 if the question was : find a lower bound for m, but here we need the smallest m, in fact it's equivalent to find the highest lower bound. So when we have m>=4 we need to check if it is the highest lower bound by finding 4 numbers such that the sum of their cube is 2002^2002
Thank you all for the answers! What I was thinking is that, when you show that x1+x2...+xm must be congruent to 4 mod 9, and you show that x1,x2...,xm€{-1,0,1} mod9, doesn't that imply m=4? Because the smallest m such that if you add numbers in that set you get 4 is exactly 4.
Oh, another ridiculous number theory problem.
Ok, this was impressive.