The tasksetters were considering requiring Fermat's little theorem was a bit too difficult for a regional contest 700 years before Fermat, but I'm glad they went with this problem.
You can also use the fact that: a^k+(n-a)^k==0 (mod n) [when k is odd] this can be proved by the binomial theorem. hence 1^965+...+2018^965 ==1+2^965 (mod 2021) then separate 2021 into 43×47 and continue using Fermat's Little Theorem and Chinese Remainder Theorem to find the answer (as shown in the video).
@@tretyakov3112 firstly it is due to Euler totient function (not FLT). The answer to your question is carmaicheal's lamda function. Here is the link for more information. brilliant.org/wiki/carmichaels-lambda-function/. for 2021 it is computed to be 966 so 2^966=1(mod2021) hence 1011 is correct
That's exactly what I wanted to suggest from last night that I saw this clip. I am happy that you brought it up. It makes the problem much simpler in a flash. Good observation. Cheers
OH WOW that first trick is brilliant, but you can prove it without the binomial theorem: (n-a)^k == (-a)^k == -a^k (mod n) the negative sign can be taken out of the power since k is odd. Cheers ^_^
This is how i solved it:- First add 2019⁹⁶⁵ and 2020⁹⁶⁵ in the series and subtract it.... Now 1⁹⁶⁵+......+2020⁹⁶⁵=0(mod 2021) And -2019⁹⁶⁵-2020⁹⁶⁵=2⁹⁶⁵+1(mod 2021) 2⁹⁶⁵=22(mod 43)=24(mod 47) By applying CRT , We get 2⁹⁶⁵=(-6×43+27×47)=1011(mod 2021) Hence 2⁹⁶⁵+1=1012(mod 2021).
Once you reduce to 1+2^(965), it's faster to use the Carmichael function. λ(2021) = lcm(phi(43),phi(47)) = lcm(42,46) = 966, hence 1+2^(965) = 1+2^(-1) = 1+1011 = 1012 mod 2021.
2^965 = 311850048364799970571308236412006025948039259443040240859773006630814358104525635278899682108224328295209757319405077381870693435686499009490495593482004909425000886398607136955865268975681716747289586991334988123957939133612635998263883635695006899610487641699336881506618514879741251551232 Who's up for 3^965 ? 😂
@@goodplacetostop2973 Well, a half decent algorithm will compute powers using only as many multiplications as twice the base 2 logarithm of the exponent.
3^965+2018^365 etc cancels out. So you are left with 1+2^965. If you double it you get 2+2^966, since 966 divides both 42 and 46, so 2^966 leaves remainder 1 when divided by 2021. So the double of your number leaves remainder 3, i.e., 2024 mod 2021. so your number leaves remainder 1012.
Since 2018 is congruent -3 (mod 2021) and there are an even number of numbers from 3 to 2018; pair up 2018 which is congruent with -3 wit 3 which is congruent 3. Pair up 2017 which is congruent -4 with 4 and so on. The exponents are odd, so all terms with a base larger than 2 will add to 0. Then simplify 2^965 with some easy tricks
horrible method here: first establish “[a+b] >= [a] + [b]” and “[a] + [-a] = -1 for a is in Z^c, if in Z then it’s 0” so [5x] + [5y] = [(3x+y) + (2x-y)] + [(3y+x) + (2y-x)] >= [3x+y] + [x+(x-y)] + [3y+x] + [y+(y-x)] >= [3x+y]+[3y+x] + [x] + [y] +([y-x] + [x-y]) >= [3x+y]+[3y+x] + [x] + [y] -1 from the inequality above we know that if x or y >= 1 then the given statement is true. (note : if (x-y) is in Z then the statement is true for any x,y) now we only need to prove 0 =< x, y
The reason the number 965 is special is because if you take the Carmichael function of 2021 you end up with 966, meaning that exponentiating by 965 is equivalent to taking the inverse over the finite field GF(2021), the problem could therefore also be expressed as 1 + 1/2 + 1/3 ... 1/2018 (mod 2021)
I noticed that! The other day I went too far the other way and people thought I had dyed my hair! If anyone out there wants to make me a nice LUT for my videos I will happily send over a clip of un-corrected footage.
From the German Math Olympiad 2020: Prove that the following equation: x(x+1)(x+2)...(x+2020)-1=0 only has one positive solution and prove that this solution satisfies the following inequality: 1/(2020! + 10) < x < 1/(2020! + 6)
This is similar to a problem in a 2019 olympiad, can't remember correctly which one it was, anyways the problem was, 1^2019 + 2^2019....2020^2019 is divided by 2019, find the remainder, so in both questions we can use the proof that, (a+b)^n/k is an integer if a+b/k is an integer, so in the same way that we solve the problem I mentioned, we can solve the problem mentioned in the video, but we need to be careful, as basically the way we would group terms would be by doing : 3+2018, 4+2017.... and so on, however, if you observe carefully, the middle term would be left out(aka 2018/2 = 1009), so 1009/2021 would give the remainder 1009, and remember how we started from 3? Well 1 and 2 is left out so that will also count to the remainder, and the final remainder is : 1009+1+2 = 1012. Hope this helps :)
@@md2perpe Well, I also want to learn Python . I know some little basics but not too much and I'm really interested in it So, can you guide me,how to lern it?
Thanks to bprp I like below method more than the Chinese remainders theorem N=23(mod 43) ----(1) N= 25 (mod 47)------(2) From 1 N=43k+23 ---(3) Sub in 2 43k+23 = 25 (mod 47) 43k=2 (mod 47) -4k = 2 (mod 47) -2k = 1 (mod 47) -2k = -46 (mod 47) k= 23 (mod 47) k = 47m+23 Sub in 3 N = 43(47m+23) + 23 N= 2021m + 1012 N = 1012 (mod 2021) The answer is 1012
I haven't looked at the video. 20 minutes for that? In short: 2021 = 43 × 47. Let p = 43 or 47. Values divisible by p can be ignored, and for a non divisible by p, one has a^(p−1) ≡ 1 (mod p). Since 965 ≡ −1 (mod p−1), one has a^965 ≡ 1/a (mod p). In (Z/pZ)*, 1/a is a bijection, so that the sum of the inverses of all the elements is equal to the sum of the elements, which is 0. Since 2019 = −2 and 2020 = −1 are missing in the sum up to the next multiple of p (2021), 1^965 + … + 2018^965 = −(1/(−2) + 1/(−1)) = 1/2 + 1 in Z/pZ, for p = 43 and p = 47, which remains valid in Z/2021Z since 2 is invertible. This gives (2021 + 1)/2 + 1 = 1012.
Ah yes, a classic from the 965 Lithuania Regional
The tasksetters were considering requiring Fermat's little theorem was a bit too difficult for a regional contest 700 years before Fermat, but I'm glad they went with this problem.
19:59 Good Place To-
Stop :)
@@ライサム-c7j you cannot order me
2018 is -3 (mod 2021), therefore 3^965 + 2018^965 = 0 (mod 2021), everything cancels except 1^965 + 2^965
This is actually the way students did it in the contest!
@@aleksmich8928I think you are right 👍
Since, I'm the author of this problem and I graded it, I know exactly, that's how they did it. :D
@@aleksmich8928 Oh, really? That’s awesome!
@@琥珀-u3o Prof. J Matulionio konkursas.
You can also use the fact that:
a^k+(n-a)^k==0 (mod n) [when k is odd]
this can be proved by the binomial theorem.
hence 1^965+...+2018^965
==1+2^965 (mod 2021)
then separate 2021 into 43×47 and continue using Fermat's Little Theorem and Chinese Remainder Theorem to find the answer (as shown in the video).
Same that's what I did
Using FLT we get 2^1932==1. It means that 2^966==+-1==2021+-1 and 2^965==1010 or 1011.
But how we can understand what answer is right?
@@tretyakov3112 firstly it is due to Euler totient function (not FLT). The answer to your question is carmaicheal's lamda function. Here is the link for more information. brilliant.org/wiki/carmichaels-lambda-function/. for 2021 it is computed to be 966 so 2^966=1(mod2021) hence 1011 is correct
That's exactly what I wanted to suggest from last night that I saw this clip. I am happy that you brought it up. It makes the problem much simpler in a flash. Good observation. Cheers
OH WOW that first trick is brilliant, but you can prove it without the binomial theorem:
(n-a)^k == (-a)^k == -a^k (mod n)
the negative sign can be taken out of the power since k is odd.
Cheers ^_^
This is how i solved it:-
First add 2019⁹⁶⁵ and 2020⁹⁶⁵ in the series and subtract it....
Now 1⁹⁶⁵+......+2020⁹⁶⁵=0(mod 2021)
And -2019⁹⁶⁵-2020⁹⁶⁵=2⁹⁶⁵+1(mod 2021)
2⁹⁶⁵=22(mod 43)=24(mod 47)
By applying CRT ,
We get 2⁹⁶⁵=(-6×43+27×47)=1011(mod 2021)
Hence 2⁹⁶⁵+1=1012(mod 2021).
Once you reduce to 1+2^(965), it's faster to use the Carmichael function. λ(2021) = lcm(phi(43),phi(47)) = lcm(42,46) = 966, hence 1+2^(965) = 1+2^(-1) = 1+1011 = 1012 mod 2021.
Sir, please make some videos on continued fractions, infinite series and telescopic series.
I make the start, calculatung 1 ^ 965 = 1.
Who continues, calculating 2 ^965?
2^965 = 311850048364799970571308236412006025948039259443040240859773006630814358104525635278899682108224328295209757319405077381870693435686499009490495593482004909425000886398607136955865268975681716747289586991334988123957939133612635998263883635695006899610487641699336881506618514879741251551232
Who's up for 3^965 ? 😂
3^965 =
26424744965696434674099773974032308092224573978040981257705289527267515760247906169164940953548135938843058101748405157163998359546478733932427934900204067659560449046569731146203500924987307254381570731322381698195357292126803075083822714110800246875776396709235176980353102012918790335125467548185110827828641207186699042986158369594578865223081557017824157853629901637871411153715235235503494661961510311461221222065488082922187004767870921451332157114681843
@@nzf-kx2qol1g12 Everything is easier with Python, right? I was surprised it computed big numbers like pow(2018,965) so fast
@@Tiessie OK , How much time did you take to write it 😅
@@goodplacetostop2973 Well, a half decent algorithm will compute powers using only as many multiplications as twice the base 2 logarithm of the exponent.
3^965+2018^365 etc cancels out. So you are left with 1+2^965. If you double it you get 2+2^966, since 966 divides both 42 and 46, so 2^966 leaves remainder 1 when divided by 2021. So the double of your number leaves remainder 3, i.e., 2024 mod 2021. so your number leaves remainder 1012.
Since 2018 is congruent -3 (mod 2021) and there are an even number of numbers from 3 to 2018; pair up 2018 which is congruent with -3 wit 3 which is congruent 3. Pair up 2017 which is congruent -4 with 4 and so on. The exponents are odd, so all terms with a base larger than 2 will add to 0. Then simplify 2^965 with some easy tricks
"Maybe even a math contest from 965" :)
A couple of months ago I couldn’t solve any of your number theory problems but now I solve every one and it is thanks to you
It's definitely a problem from 965.
3:07 Took me 5 min to understand that that "Fermaztltzeoreem" is Fermat's little theorem.
1975 USAMO problem :-
Prove that :
[5x]+[5y] >= [3x+y]+[3y+x]
where x,y>=0 and [u] denotes the greatest integer
horrible method here:
first establish “[a+b] >= [a] + [b]” and “[a] + [-a] = -1 for a is in Z^c, if in Z then it’s 0”
so [5x] + [5y] = [(3x+y) + (2x-y)] + [(3y+x) + (2y-x)]
>= [3x+y] + [x+(x-y)] + [3y+x] + [y+(y-x)]
>= [3x+y]+[3y+x] + [x] + [y] +([y-x] + [x-y])
>= [3x+y]+[3y+x] + [x] + [y] -1
from the inequality above we know that if x or y >= 1 then the given statement is true.
(note : if (x-y) is in Z then the statement is true for any x,y)
now we only need to prove 0 =< x, y
imo this was the most satisfying "good place to stop" so far
I stopped before then. I think pretty well every mod/remainder technique is in there somewhere
The reason the number 965 is special is because if you take the Carmichael function of 2021 you end up with 966, meaning that exponentiating by 965 is equivalent to taking the inverse over the finite field GF(2021), the problem could therefore also be expressed as 1 + 1/2 + 1/3 ... 1/2018 (mod 2021)
Ah, the math contest from 965…. Bathed in nostalgia am I…
I can remember this problem in 965.
This was in my final exam.
Time is passing so fast…. 😂
1:30 "I do not claim that this is the fastest method....."
Tiny nitpick that doesn’t effect the final result: The last block should actually start at 1979, because 46*43+1=1979
Even in 965 A. D. there were math contests 😅in Lithuania
Shouldn't M1 be -12 and M2 be 11? Then you wouldn't have to do a final modulo
Amazing video but i think you should check upon the color correction since the video looks a bit dull
I noticed that! The other day I went too far the other way and people thought I had dyed my hair! If anyone out there wants to make me a nice LUT for my videos I will happily send over a clip of un-corrected footage.
@@MichaelPennMath I can do that, sure :)
And do you know what you typically use for your camera's white balance and exposure settings?
@Seth Harwood Thank you so much!! I'll send you all of the settings in the email.
+1 Like for doing exactly 20 minutes.
From the German Math Olympiad 2020:
Prove that the following equation:
x(x+1)(x+2)...(x+2020)-1=0
only has one positive solution and prove that this solution satisfies the following inequality:
1/(2020! + 10) < x < 1/(2020! + 6)
This is similar to a problem in a 2019 olympiad, can't remember correctly which one it was, anyways the problem was, 1^2019 + 2^2019....2020^2019 is divided by 2019, find the remainder, so in both questions we can use the proof that, (a+b)^n/k is an integer if a+b/k is an integer, so in the same way that we solve the problem I mentioned, we can solve the problem mentioned in the video, but we need to be careful, as basically the way we would group terms would be by doing : 3+2018, 4+2017.... and so on, however, if you observe carefully, the middle term would be left out(aka 2018/2 = 1009), so 1009/2021 would give the remainder 1009, and remember how we started from 3? Well 1 and 2 is left out so that will also count to the remainder, and the final remainder is : 1009+1+2 = 1012.
Hope this helps :)
made a video about it using another approach :)
python dumb here again:
print(sum([i**965 for i in range(1,2019)]) % 2021)
The pow-function has a remainder optional parameter. Replacing i**965 with pow(i, 965, 2021) will probably make the code run faster.
@@pim4138 Thanks for your comment, I didn't know about this. This makes cryptography things easier. It's really a useful piece of info.
6:35 I think the last 40 terms are supposed to be 1979^965 + ... + 2018^965 . (In the video it has 1977, not 1979)
Yes. But not important for the argument as they are reduced mods starting from 1, which is = to 1979
@@MrGreyprof Sure, I didn't say it affected the solution.
Large but simple! 😁
What if I tell you that remainder is 9?
2:07 what is the symbol for and called??
I think it's just a quick way of writing & (or ampersand)
Ampersand
viewer suggestion
Lithuanian brothers unite!!
Hating these modular arithmetics :-) but loving your videos explaining it so well!
Python one-liner: sum([n**965 for n in range(1, 2019)]) % 2021
Looks like you are a Programmer
@@shivansh668 Yes, I work as programmer. But I've always also been interested in mathematics and physics and have studied those topics too.
@@md2perpe Ohh , that's great
@@md2perpe Well, I also want to learn Python . I know some little basics but not too much and I'm really interested in it
So, can you guide me,how to lern it?
Python is 👍
Thanks to bprp I like below method more than the Chinese remainders theorem
N=23(mod 43) ----(1)
N= 25 (mod 47)------(2)
From 1
N=43k+23 ---(3)
Sub in 2
43k+23 = 25 (mod 47)
43k=2 (mod 47)
-4k = 2 (mod 47)
-2k = 1 (mod 47)
-2k = -46 (mod 47)
k= 23 (mod 47)
k = 47m+23
Sub in 3
N = 43(47m+23) + 23
N= 2021m + 1012
N = 1012 (mod 2021)
The answer is 1012
Which bprp video are you referring to??
@@MrGreyprof long time. You have to search
@@skwbusaidi Ok. Thanks
@@MrGreyprof
Here is the link
ruclips.net/video/LInNgWMtFEs/видео.html
Too much for me! 🤪
I haven't looked at the video. 20 minutes for that? In short: 2021 = 43 × 47. Let p = 43 or 47. Values divisible by p can be ignored, and for a non divisible by p, one has a^(p−1) ≡ 1 (mod p). Since 965 ≡ −1 (mod p−1), one has a^965 ≡ 1/a (mod p). In (Z/pZ)*, 1/a is a bijection, so that the sum of the inverses of all the elements is equal to the sum of the elements, which is 0. Since 2019 = −2 and 2020 = −1 are missing in the sum up to the next multiple of p (2021), 1^965 + … + 2018^965 = −(1/(−2) + 1/(−1)) = 1/2 + 1 in Z/pZ, for p = 43 and p = 47, which remains valid in Z/2021Z since 2 is invertible. This gives (2021 + 1)/2 + 1 = 1012.
Though there is a faster solution (canceling terms), I like your approach of using 1/a as a bijection in z/nz*
Metais
Hello
אם אתם דוברי עברית, אתם כנראה תהנו מהערוץ שלי 'דף אחד על מתמטיקה'. בואו לבדוק :)
Hmm.. I need to review my modular arithmetic. I'm not following how he's using mod46 reduction and mod47 reduction at the same time.
Look up fermat's little theorem
"The math problems are hard, tricky, challenging, but you, you will be worse..... Solve and prove until it's a good place to stop"
Lithuanian brothers unite!
Siaip matematika darr neegzistavo 965