Brush up on Number Theory tricks!

Рет қаралды 19,663

3 жыл бұрын

We look at a nice viewer suggested number theory problem.
Suggest a problem: forms.gle/ea7Pw7HcKePGB4my5
Please Subscribe: kzfaq.info...
Merch: teespring.com/stores/michael-...
Personal Website: www.michael-penn.net
Randolph College Math: www.randolphcollege.edu/mathem...
Randolph College Math and Science on Facebook: / randolph.science
Research Gate profile: www.researchgate.net/profile/...
Google Scholar profile: scholar.google.com/citations?...
If you are going to use an ad-blocker, considering using brave and tipping me BAT!
brave.com/sdp793
Buy textbooks here and help me out: amzn.to/31Bj9ye
Buy an amazon gift card and help me out: amzn.to/2PComAf
Books I like:
Sacred Mathematics: Japanese Temple Geometry: amzn.to/2ZIadH9
Electricity and Magnetism for Mathematicians: amzn.to/2H8ePzL
Abstract Algebra:
Judson(online): abstract.ups.edu/
Judson(print): amzn.to/2Xg92wD
Dummit and Foote: amzn.to/2zYOrok
Gallian: amzn.to/2zg4YEo
Artin: amzn.to/2LQ8l7C
Differential Forms:
Bachman: amzn.to/2z9wljH
Number Theory:
Crisman(online): math.gordon.edu/ntic/
Strayer: amzn.to/3bXwLah
Andrews: amzn.to/2zWlOZ0
Analysis:
Abbot: amzn.to/3cwYtuF
How to think about Analysis: amzn.to/2AIhwVm
Calculus:
OpenStax(online): openstax.org/subjects/math
OpenStax Vol 1: amzn.to/2zlreN8
OpenStax Vol 2: amzn.to/2TtwoxH
OpenStax Vol 3: amzn.to/3bPJ3Bn
My Filming Equipment:
Camera: amzn.to/3kx2JzE
Lense: amzn.to/2PFxPXA
Audio Recorder: amzn.to/2XLzkaZ
Microphones: amzn.to/3fJED0T
Lights: amzn.to/2XHxRT0
White Chalk: amzn.to/3ipu3Oh
Color Chalk: amzn.to/2XL6eIJ

Пікірлер: 102

@mauithedog10 3 жыл бұрын

Ah yes, a classic from the 965 Lithuania Regional

@Kalmakka 3 жыл бұрын

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.

@goodplacetostop2973 3 жыл бұрын

19:59 Good Place To-

@user-to3kp2ls7n 3 жыл бұрын

Stop :)

@arindamkashyap9420 3 жыл бұрын

@@user-to3kp2ls7n you cannot order me

@antonryzhov 3 жыл бұрын

2018 is -3 (mod 2021), therefore 3^965 + 2018^965 = 0 (mod 2021), everything cancels except 1^965 + 2^965

@aleksmich8928 3 жыл бұрын

This is actually the way students did it in the contest!

@shivansh668 3 жыл бұрын

@@aleksmich8928I think you are right 👍

@aleksmich8928 3 жыл бұрын

Since, I'm the author of this problem and I graded it, I know exactly, that's how they did it. :D

@goodplacetostop2973 3 жыл бұрын

@@aleksmich8928 Oh, really? That’s awesome!

@aleksmich8928 3 жыл бұрын

@@user-ds6jv5jf5o Prof. J Matulionio konkursas.

@wjx8439 3 жыл бұрын

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).

@disguisedhell 3 жыл бұрын

Same that's what I did

@tretyakov3112 3 жыл бұрын

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?

@disguisedhell 3 жыл бұрын

@@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

@bahkimi 3 жыл бұрын

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

@andreben6224 2 жыл бұрын

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 ^_^

@siulibasak3804 3 жыл бұрын

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).

@aadfg0 3 жыл бұрын

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.

@karangupta1825 3 жыл бұрын

Sir, please make some videos on continued fractions, infinite series and telescopic series.

@Tehom1 3 жыл бұрын

"Maybe even a math contest from 965" :)

@crazy4hitman755 3 жыл бұрын

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

@CoderboyPB 3 жыл бұрын

I make the start, calculatung 1 ^ 965 = 1. Who continues, calculating 2 ^965?

@goodplacetostop2973 3 жыл бұрын

2^965 = 311850048364799970571308236412006025948039259443040240859773006630814358104525635278899682108224328295209757319405077381870693435686499009490495593482004909425000886398607136955865268975681716747289586991334988123957939133612635998263883635695006899610487641699336881506618514879741251551232 Who's up for 3^965 ? 😂

@Tiessie 3 жыл бұрын

3^965 = 26424744965696434674099773974032308092224573978040981257705289527267515760247906169164940953548135938843058101748405157163998359546478733932427934900204067659560449046569731146203500924987307254381570731322381698195357292126803075083822714110800246875776396709235176980353102012918790335125467548185110827828641207186699042986158369594578865223081557017824157853629901637871411153715235235503494661961510311461221222065488082922187004767870921451332157114681843

@goodplacetostop2973 3 жыл бұрын

@@nzf-kx2qol1g12 Everything is easier with Python, right? I was surprised it computed big numbers like pow(2018,965) so fast

@shivansh668 3 жыл бұрын

@@Tiessie OK , How much time did you take to write it 😅

@TJStellmach 3 жыл бұрын

@@goodplacetostop2973 Well, a half decent algorithm will compute powers using only as many multiplications as twice the base 2 logarithm of the exponent.

@thephysicistcuber175 3 жыл бұрын

It's definitely a problem from 965.

@d4slaimless 3 жыл бұрын

3:07 Took me 5 min to understand that that "Fermaztltzeoreem" is Fermat's little theorem.

@jakobovergaard6302 3 жыл бұрын

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

@kamaljain5228 3 жыл бұрын

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.

@easymathematik Ай бұрын

I can remember this problem in 965. This was in my final exam. Time is passing so fast…. 😂

@shivansh668 3 жыл бұрын

Even in 965 A. D. there were math contests 😅in Lithuania

@writerightmathnation9481 3 ай бұрын

Ah, the math contest from 965…. Bathed in nostalgia am I…

@deidara_8598 3 жыл бұрын

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)

@romajimamulo 3 жыл бұрын

Shouldn't M1 be -12 and M2 be 11? Then you wouldn't have to do a final modulo

@davidgerber9317 3 жыл бұрын

1:30 "I do not claim that this is the fastest method....."

@nemo.refert 3 жыл бұрын

imo this was the most satisfying "good place to stop" so far

@mcwulf25 3 жыл бұрын

I stopped before then. I think pretty well every mod/remainder technique is in there somewhere

@hassanalihusseini1717 3 жыл бұрын

Hating these modular arithmetics :-) but loving your videos explaining it so well!

@lucashoffses9019 3 жыл бұрын

Tiny nitpick that doesn’t effect the final result: The last block should actually start at 1979, because 46*43+1=1979

@momeme2925 3 жыл бұрын

made a video about it using another approach :)

@_judge_me_not 3 жыл бұрын

1975 USAMO problem :- Prove that : [5x]+[5y] >= [3x+y]+[3y+x] where x,y>=0 and [u] denotes the greatest integer

@liyi-hua2111 3 жыл бұрын

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

@suramanujan 3 жыл бұрын

Large but simple! 😁

@jesusalej1 3 жыл бұрын

What if I tell you that remainder is 9?

@prithujsarkar2010 3 жыл бұрын

Amazing video but i think you should check upon the color correction since the video looks a bit dull

@MichaelPennMath 3 жыл бұрын

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.

@typha 3 жыл бұрын

@@MichaelPennMath I can do that, sure :) And do you know what you typically use for your camera's white balance and exposure settings?

@MichaelPennMath 3 жыл бұрын

@Seth Harwood Thank you so much!! I'll send you all of the settings in the email.

@gen3360 2 жыл бұрын

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 :)

@gervasiociampin2062 3 жыл бұрын

2:07 what is the symbol for and called??

@klucha789 3 жыл бұрын

I think it's just a quick way of writing & (or ampersand)

@mikeschieffer2644 3 жыл бұрын

Ampersand

@Bodyknock 3 жыл бұрын

6:35 I think the last 40 terms are supposed to be 1979^965 + ... + 2018^965 . (In the video it has 1977, not 1979)

@MrGreyprof 3 жыл бұрын

Yes. But not important for the argument as they are reduced mods starting from 1, which is = to 1979

@Bodyknock 3 жыл бұрын

@@MrGreyprof Sure, I didn't say it affected the solution.

@DrPhipster 3 жыл бұрын

+1 Like for doing exactly 20 minutes.

@nuto1981 3 жыл бұрын

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)

@MrKA1961 3 жыл бұрын

python dumb here again: print(sum([i**965 for i in range(1,2019)]) % 2021)

@pim4138 3 жыл бұрын

The pow-function has a remainder optional parameter. Replacing i**965 with pow(i, 965, 2021) will probably make the code run faster.

@MrKA1961 3 жыл бұрын

@@pim4138 Thanks for your comment, I didn't know about this. This makes cryptography things easier. It's really a useful piece of info.

@mcwulf25 3 жыл бұрын

Too much for me! 🤪

@jayska5802 3 жыл бұрын

Hello

@happyrogue7146 3 жыл бұрын

viewer suggestion

@tarnaskarnas9233 3 жыл бұрын

Metais

@md2perpe 3 жыл бұрын

Python one-liner: sum([n**965 for n in range(1, 2019)]) % 2021

@shivansh668 3 жыл бұрын

Looks like you are a Programmer

@md2perpe 3 жыл бұрын

@@shivansh668 Yes, I work as programmer. But I've always also been interested in mathematics and physics and have studied those topics too.

@shivansh668 3 жыл бұрын

@@md2perpe Ohh , that's great

@shivansh668 3 жыл бұрын

@@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?

@goodplacetostop2973 3 жыл бұрын

Python is 👍

@hauntedmasc 3 жыл бұрын

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.

@agfd5659 3 жыл бұрын

Look up fermat's little theorem

@thekingadomas1656 3 жыл бұрын

Lithuanian brothers unite!!

@skwbusaidi 3 жыл бұрын

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

@MrGreyprof 3 жыл бұрын

Which bprp video are you referring to??

@skwbusaidi 3 жыл бұрын

@@MrGreyprof long time. You have to search

@MrGreyprof 3 жыл бұрын

@@skwbusaidi Ok. Thanks

@skwbusaidi 3 жыл бұрын

@@MrGreyprof Here is the link kzfaq.info/get/bejne/gq-egcqIstqqdac.html

@user-ft9ps5pt2t 3 жыл бұрын

אם אתם דוברי עברית, אתם כנראה תהנו מהערוץ שלי 'דף אחד על מתמטיקה'. בואו לבדוק :)

@vinc17fr 3 жыл бұрын

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.

@riadsouissi 3 жыл бұрын

Though there is a faster solution (canceling terms), I like your approach of using 1/a as a bijection in z/nz*