For some reason I like number theory problems better when they involve brute force, it just seems more natural to me than a carefully fabricated problem
Not certain what you mean by "carefully fabricated problem". Noticed your channel has a video that eschews the brute force approach, but here you state you prefer brute force.
@@MyOneFiftiethOfADollar I think they mean that you can set up a problem so that you apply a few theorems and the answers emerge without you having to do much calculations. However, if you are working on math in the real world and a number theory problem pops up in whatever work you’re doing, the chances you’ll be able to find the solutions through a bunch of tricks avoiding brute force calculation is rare. That’s what I think the original commenter meant by “natural,” you’re more likely to need to employ some brute force than not when doing research. The other, rarer problems where you don’t need brute force need to be fabricated/created “carefully” because if you don’t set up everything perfectly, you’ll probs need brute force.
@@MyOneFiftiethOfADollar I'm not saying that I absolutely hate problems which can be solved using certain tricks. In fact, they can be quite interesting at times. In line with Myrus' reply, the problems involving brute force seem more natural because in solving actual problems whose answers are unknown, brute force often is one's only option. Of course, using tricks is really useful and convenient when you know they can be used, and should obviously be preferred. Regarding my channel, I only tend to upload about problems firstly whose solutions I find intriguing, and secondly find comprehendible, and I'm barely 15 so solving previously unsolved problems is quite new of a concept to me. I've been trying to upload about more "hardcore" stuff lately though.
@@HershO. Thanks to you and Myrus for the clarification. The term fabricated has a pejorative connotation legally, but I get your drift that some problems are designed to work out nicely by applying obscure results such as the totient function in this case. Totient is well known from number theory, but many may be a bit rusty knowing to apply it here.
for k=1, x^y = 3502^3 = 42948542008 terminating in 2008 just like you said it would! Did not take long to determine y=3, but the rest of it was hard. Would have to watch at least two more times before I could reproduce the proof without guidance and maybe not even then.....Lovely stuff! Wonder how many of the competitors figured it out back in 2008 under time constraints?! k=3, x^y = 8502^3 = 614558602008 CAN'T get enough of this!!
3:50 This one is fun -- with *y = 3* and *x = 2n* for some odd *n* you can also subtract 1 to factorize *n^3 = 1250a + 251 => 250 * (5a + 1) = n^3 - 1 = (n - 1) * (n^2 + n + 1)* The left-hand side (LHS) is divisible by *125.* Notice *(n^2 + n + 1)* is not divisible by *2* or *5:* *n mod 2 | 0 1 n mod 5 | 0 1 2 3 4* *n^2 + n + 1 mod 2 | 1 1 n^2 + n + 1 mod 5 | 1 3 2 3 1* Therefore *(n - 1)* must be divisible by *250,* i.e. *n = 250m + 1, m ∈ ℕ_0 (1)* Insert *n* into the factorized cubic. Divide by 250 and reduce *"mod 5"* to obtain *5a + 1 = m * (n^2 + n + 1) => 1 ≡ m * (1^2 + 1 + 1) = 3m mod 5* Multiply by *2* to solve for *m:* *2 ≡ 6m ≡ m mod 5 => m = 2 + 5k, k ∈ ℕ_0 (2)* Insert (1) and (2) into *x = 2n* to obtain the result from 10:50. A quick check *"mod 10^4"* shows all those possible solutions from 10:50 do indeed satisfy *"x^y ≡ 2008 mod 10^4"*
But 10^4 is arbeitrary..he doesn't know how many 10s there are so no reason to pick 4..coukdbe 8.could be 10^1111...see what I mean? Not justified at all
And y could be greater than. 3 though..if the first part of the right hand side the a(10^4) has some factors that divided 16 and then another part thst gives remainder 8you might get a multiple of 16..also again why am write as a(10^4) when it could have bigger factors than 10 000 is the a supposed supposed encompass that'? Since 10^4 would be the gcf of all terms bigger than that I guess is what he meant?
I'm new to number theory and I want to know whether my reasoning is correct. "To see why the implication 𝑦=2 →𝑛 𝑖𝑠 𝑒𝑣𝑒𝑛 holds, assume the negation is true. Then 𝑛=2𝑗+1 𝑓𝑜𝑟 𝑠𝑜𝑚𝑒 𝑗∈ℤ. Our exponential function then becomes 𝑥^2=2^2 (2𝑗+1)^2=2^4 𝑗^2+2^4 𝑗+2^2. But this is congruent to 4(𝑚𝑜𝑑 8) which contradicts our assumption that 𝑥^𝑦≡0(𝑚𝑜𝑑 8). Hence the implication holds."
Another (maybe more elegant) way is to split all powers of two at once: *x = 2^m * o, o odd integer* By comparing exponents of the powers of two, you get *my = 3.* Considering *y > 1* you are left with one choice *y = 3*
Somehow we "know" that once we have n=250m+1 we have to do further work to find appropriate values for m, but when we find m=5k+2 we "know" this is true for all k. It just isn't clear how we know that. I expect it is because Michael writes the whole thing out as "this implies that", but at some points the implications are actually equivalences. Thus you can then work backwards from m=5k+2 to find that this provides satisfactory x and y for all values of k, but you can't work back from n=250m+1 because some of the steps there were one-way implications. In particular you can work back from m=5k+2 to show (250m+1)^3=1250a+251 for some a, and from there back to x^y=10000a+2008. You can't work back from n=250m+1 because the implication on the second line is not reversible: Just because n^3≡1 (mod 250) does not imply that n^3=1250a+251 for some a, the most obvious counterexample being n=1.
Because you can easily find a counter-example for 500m + 2. And it is easy to prove that if m is restricted to 5k + 2, it is satisfied for all values of k: (2500k + 1002)^3 can be expanded to something of the form w*10^6 + 3*1002*(2500k)^2 + 3*(2500)*(1002)^2 + 1002^3 You can easily check that the first 3 terms are 0 mod (10^4) while the last term ends in 2008.
If I am fully understanding your question, he continues because we still need to find acceptable form for x(the base). He showed early in the video that y(the exponent) is equal to 3
Just did the same problem with 636 in place of 2008. Got congruences of mod 4 and 8, compared to 8 and 16 as seen it the video. Got y=2. as compared to y=3 in this video. Got two distinct forms for x versus the one form in this video(x==1 mod 250) One of the forms for x was 306+500m, so for m=4, we get (2306)^2 = 5,317,636 as desired! This video was looking for natural number possibilities for x and y, but I think it holds for all integers.
Hold on he made a mistake at 2:04 thst is 1 mod 16 not 8 mod 16..if you divided then8 and 26 reduce 10 1/2 and 251 divided by 2 gives a remainder of 1not 8 so that is 1 mod 16
You used that the Euler totient function of 250 is 100 but it is actually 80. It doesnt change anything but you wouldnt consider n to the 99th power but n to the 81st power if I am not mistaken.
A novel concept for you: Learn the Euler Totient function by reading any elementary number theory book. A lot more productive than blaming "they" , but I digress.
I think you are mistaking it for (250+m)³ which would look like that. Instead, the video has (250m+1)³. If you take s=250m, then that is (s+1)³ = s³+3s²+3s+1. Substituting back in, that gives us: (250m+1)³ = (250m)³+3(250m)²+3(250m)+1. Hopefully that helps!
Had the same doubt. But I suppose it is because we need to have the number being 0 mod 8. The 2^2 only contributes with a 4 in the factorization so the remaining two must come from the n bit
Why 10^4 thiugh it could be 10^ to any integers?? Is thst what the a is for? And can't you solve without mod at all? Why is no one else wondering why he picked 10^4..the 4 is totally arbitrary..cpuldve just as well been 8 or 111..didnt anyone else catch this..yes it is at least 10^4 times something but it could be a lot more than 4..
I'm really confused how did you conclude that congruence mod 5 defines R and m correctly.... What if there's no solutions of such a cubic equation? I mean, when we plug R = 5k+2 into the cubic equation with R and m
If there were no solutions to the cubic equation, then there would be no solutions to the original problem. But the final step (which he leaves as an exercise to the viewer), is checking that numbers of the form (2500k+1002)^3 do in fact end in 2008. Which is to say, the step you're asking about is only meant to _constrain_ the possible values of m. It's not important at that point whether any such values exist.
@@fartoxedm5638 I believe so. The cubic equation in m at 7:35 must be satisfied by any possible solutions. We don't know for which values of the parameter _a_ there exist any integer roots to the cubic. But reducing modulo 5 removes _a_ from consideration, leaving us a weaker statement that must still be true for any solutions that do exist. Which means that any possible solutions have to at least satisfy the congruence 3m ≡ 1 (mod 5), i.e. m≡2 (mod 5), i.e. m is of the form 5k+2. We _don't_ know at this point whether _all_ values of k will work, just that any value that does work must have this form. Finally (and this is the part that he left as an exercise) expanding (2500k+1002)^3 = 15625000000 k^3 + 18787500000 k^2 + 7530030000 k + 1006012008 shows that all values of k do indeed give solutions. (Note that you don't really need to calculate all of those coefficients, you just need to work out the last 4 digits of 1002^3 and check that all the other coefficients are multiples of 10000. And the last 4 digits of 1002^3 = (1000+2)^3 are the same as the last 4 digits of 3*2^2*1000+2^3, which is 12008, since the higher-order terms of the binomial expansion are all multiples of 1000000).
@@fartoxedm5638 I will say yes, clearly for integer solutions. If we take another route, for example using different modules we know that the result must satisfy our result or it will violate the logic. So it's possible to get a subset of this one but we can't get any solution that does not satisfy the closed form.
![ทุกครั้งที่หลับตา (Lucid Dream) - AYLA's [ Official MV ]](http://i.ytimg.com/vi/4i1OBAQyv58/mqdefault.jpg)
Sound dropped out but came back for your goodbye sentence.
That's a good place for sound to return
that really confused me lol I thought my device's speakers died
And that was not a good place to stop the sound 👂👀📵
For some reason I like number theory problems better when they involve brute force, it just seems more natural to me than a carefully fabricated problem
Not certain what you mean by "carefully fabricated problem". Noticed your channel has a video that eschews the brute force approach, but here you state you prefer brute force.
@@MyOneFiftiethOfADollar I think they mean that you can set up a problem so that you apply a few theorems and the answers emerge without you having to do much calculations. However, if you are working on math in the real world and a number theory problem pops up in whatever work you’re doing, the chances you’ll be able to find the solutions through a bunch of tricks avoiding brute force calculation is rare. That’s what I think the original commenter meant by “natural,” you’re more likely to need to employ some brute force than not when doing research. The other, rarer problems where you don’t need brute force need to be fabricated/created “carefully” because if you don’t set up everything perfectly, you’ll probs need brute force.
@@MyOneFiftiethOfADollar I'm not saying that I absolutely hate problems which can be solved using certain tricks. In fact, they can be quite interesting at times. In line with Myrus' reply, the problems involving brute force seem more natural because in solving actual problems whose answers are unknown, brute force often is one's only option. Of course, using tricks is really useful and convenient when you know they can be used, and should obviously be preferred. Regarding my channel, I only tend to upload about problems firstly whose solutions I find intriguing, and secondly find comprehendible, and I'm barely 15 so solving previously unsolved problems is quite new of a concept to me. I've been trying to upload about more "hardcore" stuff lately though.
@@HershO. Thanks to you and Myrus for the clarification. The term fabricated has a pejorative connotation legally, but I get your drift that some problems are designed to work out nicely by applying obscure results such as the totient function in this case. Totient is well known from number theory, but many may be a bit rusty knowing to apply it here.
for k=1, x^y = 3502^3 = 42948542008 terminating in 2008 just like you said it would! Did not take long to determine y=3, but the rest of it was hard. Would have to watch at least two more times before I could reproduce the proof without guidance and maybe not even then.....Lovely stuff! Wonder how many of the competitors figured it out back in 2008 under time constraints?!
k=3, x^y = 8502^3 = 614558602008 CAN'T get enough of this!!
3:50 This one is fun -- with *y = 3* and *x = 2n* for some odd *n* you can also subtract 1 to factorize
*n^3 = 1250a + 251 => 250 * (5a + 1) = n^3 - 1 = (n - 1) * (n^2 + n + 1)*
The left-hand side (LHS) is divisible by *125.* Notice *(n^2 + n + 1)* is not divisible by *2* or *5:*
*n mod 2 | 0 1 n mod 5 | 0 1 2 3 4*
*n^2 + n + 1 mod 2 | 1 1 n^2 + n + 1 mod 5 | 1 3 2 3 1*
Therefore *(n - 1)* must be divisible by *250,* i.e.
*n = 250m + 1, m ∈ ℕ_0 (1)*
Insert *n* into the factorized cubic. Divide by 250 and reduce *"mod 5"* to obtain
*5a + 1 = m * (n^2 + n + 1) => 1 ≡ m * (1^2 + 1 + 1) = 3m mod 5*
Multiply by *2* to solve for *m:*
*2 ≡ 6m ≡ m mod 5 => m = 2 + 5k, k ∈ ℕ_0 (2)*
Insert (1) and (2) into *x = 2n* to obtain the result from 10:50. A quick check *"mod 10^4"* shows all those possible solutions from 10:50 do indeed satisfy *"x^y ≡ 2008 mod 10^4"*
But 10^4 is arbeitrary..he doesn't know how many 10s there are so no reason to pick 4..coukdbe 8.could be 10^1111...see what I mean? Not justified at all
And y could be greater than. 3 though..if the first part of the right hand side the a(10^4) has some factors that divided 16 and then another part thst gives remainder 8you might get a multiple of 16..also again why am write as a(10^4) when it could have bigger factors than 10 000 is the a supposed supposed encompass that'? Since 10^4 would be the gcf of all terms bigger than that I guess is what he meant?
I love these problems don’t stop please!!!
I'm new to number theory and I want to know whether my reasoning is correct. "To see why the implication 𝑦=2 →𝑛 𝑖𝑠 𝑒𝑣𝑒𝑛 holds, assume the negation is true. Then 𝑛=2𝑗+1 𝑓𝑜𝑟 𝑠𝑜𝑚𝑒 𝑗∈ℤ. Our exponential function then becomes 𝑥^2=2^2 (2𝑗+1)^2=2^4 𝑗^2+2^4 𝑗+2^2. But this is congruent to 4(𝑚𝑜𝑑 8) which contradicts our assumption that 𝑥^𝑦≡0(𝑚𝑜𝑑 8). Hence the implication holds."
Another (maybe more elegant) way is to split all powers of two at once: *x = 2^m * o, o odd integer*
By comparing exponents of the powers of two, you get *my = 3.* Considering *y > 1* you are left with one choice *y = 3*
Nice problem and solution. I could only get as far as y=3. There's evidently more going on on the pampas than some of us would have suspected
10:51
No perfect square can end in 8. So why not rule out Y=2 (or any even number) straightaway?
Somehow we "know" that once we have n=250m+1 we have to do further work to find appropriate values for m, but when we find m=5k+2 we "know" this is true for all k. It just isn't clear how we know that. I expect it is because Michael writes the whole thing out as "this implies that", but at some points the implications are actually equivalences. Thus you can then work backwards from m=5k+2 to find that this provides satisfactory x and y for all values of k, but you can't work back from n=250m+1 because some of the steps there were one-way implications.
In particular you can work back from m=5k+2 to show (250m+1)^3=1250a+251 for some a, and from there back to x^y=10000a+2008.
You can't work back from n=250m+1 because the implication on the second line is not reversible: Just because n^3≡1 (mod 250) does not imply that n^3=1250a+251 for some a, the most obvious counterexample being n=1.
Because you can easily find a counter-example for 500m + 2. And it is easy to prove that if m is restricted to 5k + 2, it is satisfied for all values of k:
(2500k + 1002)^3 can be expanded to something of the form w*10^6 + 3*1002*(2500k)^2 + 3*(2500)*(1002)^2 + 1002^3
You can easily check that the first 3 terms are 0 mod (10^4) while the last term ends in 2008.
If I am fully understanding your question, he continues because we still need to find acceptable form for x(the base). He showed early in the video that y(the exponent) is equal to 3
Just did the same problem with 636 in place of 2008. Got congruences of mod 4 and 8, compared to 8 and 16 as seen it the video. Got y=2. as compared to y=3 in this video. Got two distinct forms for x versus the one form in this video(x==1 mod 250)
One of the forms for x was 306+500m, so for m=4, we get (2306)^2 = 5,317,636 as desired!
This video was looking for natural number possibilities for x and y, but I think it holds for all integers.
Hold on he made a mistake at 2:04 thst is 1 mod 16 not 8 mod 16..if you divided then8 and 26 reduce 10 1/2 and 251 divided by 2 gives a remainder of 1not 8 so that is 1 mod 16
As usual thank you for the video.
You used that the Euler totient function of 250 is 100 but it is actually 80. It doesnt change anything but you wouldnt consider n to the 99th power but n to the 81st power if I am not mistaken.
totient(250)=250*(1/2)*(4/5)=100, which plugging it into wolfram alpha verifies, not 80.
@@cyangupta2275 You are completely right, I forgot about the condition for multiplicability of the totient function.
What if they didn't bother to teach me the totient function in my number theory course? Not that I'd be able to solve this if they did, but I digress.
A novel concept for you: Learn the Euler Totient function by reading any elementary number theory book. A lot more productive than blaming "they" , but I digress.
I check k=0 and k=1. Works like a charm. Its a Very good. Amazing what math can do.
Hi Dr. Penn!
EEEE VAMOS ARGENTINAAAA
At 7:11 isn't there a mistake in the binomial development :" ... + 3.250².m² + 3.250.m + ..." shouldn't be instead "... + 3.250².m + 3.250.m² + ..." ?
I think you are mistaking it for (250+m)³ which would look like that. Instead, the video has (250m+1)³.
If you take s=250m, then that is (s+1)³ = s³+3s²+3s+1. Substituting back in, that gives us:
(250m+1)³ = (250m)³+3(250m)²+3(250m)+1.
Hopefully that helps!
@@ZedaZ80 😮 You are right ! I'm sorry, Michael ! Thank you Zeda !
3:20 why does "y is even" imply that "n is even"?
Had the same doubt. But I suppose it is because we need to have the number being 0 mod 8. The 2^2 only contributes with a 4 in the factorization so the remaining two must come from the n bit
@@ruilopes6638 Yep, that's it. Thanks!
It’s also because x was assumed to be even. Ergo the factorization must be even, otherwise it’d be odd.
@@NotoriousSRG 2*3 is also even but second factor is odd
Loved it.
Why 10^4 thiugh it could be 10^ to any integers?? Is thst what the a is for? And can't you solve without mod at all? Why is no one else wondering why he picked 10^4..the 4 is totally arbitrary..cpuldve just as well been 8 or 111..didnt anyone else catch this..yes it is at least 10^4 times something but it could be a lot more than 4..
I'm really confused how did you conclude that congruence mod 5 defines R and m correctly.... What if there's no solutions of such a cubic equation? I mean, when we plug R = 5k+2 into the cubic equation with R and m
I believe you have to use primitive root because you are doing modulo 5?
If there were no solutions to the cubic equation, then there would be no solutions to the original problem. But the final step (which he leaves as an exercise to the viewer), is checking that numbers of the form (2500k+1002)^3 do in fact end in 2008.
Which is to say, the step you're asking about is only meant to _constrain_ the possible values of m. It's not important at that point whether any such values exist.
@@TJStellmach does this imply that it's the only possible solution?
@@fartoxedm5638 I believe so. The cubic equation in m at 7:35 must be satisfied by any possible solutions. We don't know for which values of the parameter _a_ there exist any integer roots to the cubic. But reducing modulo 5 removes _a_ from consideration, leaving us a weaker statement that must still be true for any solutions that do exist.
Which means that any possible solutions have to at least satisfy the congruence 3m ≡ 1 (mod 5), i.e. m≡2 (mod 5), i.e. m is of the form 5k+2. We _don't_ know at this point whether _all_ values of k will work, just that any value that does work must have this form.
Finally (and this is the part that he left as an exercise) expanding (2500k+1002)^3 = 15625000000 k^3 + 18787500000 k^2 + 7530030000 k + 1006012008 shows that all values of k do indeed give solutions. (Note that you don't really need to calculate all of those coefficients, you just need to work out the last 4 digits of 1002^3 and check that all the other coefficients are multiples of 10000. And the last 4 digits of 1002^3 = (1000+2)^3 are the same as the last 4 digits of 3*2^2*1000+2^3, which is 12008, since the higher-order terms of the binomial expansion are all multiples of 1000000).
@@fartoxedm5638 I will say yes, clearly for integer solutions. If we take another route, for example using different modules we know that the result must satisfy our result or it will violate the logic. So it's possible to get a subset of this one but we can't get any solution that does not satisfy the closed form.
Your mic was not working ~10:43 until 10:51😱
I thought it was my laptop lol
3:39 if y=2 implies that n is even ?
Since x^y=(2^2)*n^2 is equivalent to 0 mod 8 we need to be able to factor out 2^3 from the right side
around 3:45 in, why does y=2 imply that n is even? I'm not sure I follow
Another factor of 2 besides 2^2 is required for the number to be a multiple of 8, so n has to be even
How was this conclude? That if y=2, then, n is even? Can someone help?
If n=2, not enough power of 2 to absorb 8=2^3, so n should be divisible by 2.
Why is n even when y=2? The two seem unrelated.
the number is divisible by 8, you can continue from then onward
Nice one
Vamos Messi!!!!!!!!!!!!!!!!! 🐐🐐