Number Theory for Competitive Programming | Topic Stream 9

Tutorial on number theory, including most of the basic stuff and a few more advanced things. Note the rather unusual stream time. Sorry that this has (repeatedly) been delayed - for whatever reason, I had a huge aversion to actually recording this, and I'm not sure why.
Links:
Mashup (practice problems): codeforces.com/contestInvitat...
Problem difficulties (and sources): pastebin.com/Tt26QKbM
Stream time (actually 1.5 days since upload, not 2.5 days): www.timeanddate.com/worldcloc...
docs.google.com/presentation/... (slides)
cp-algorithms.com/algebra/phi... (totient function)
discuss.codechef.com/t/guide-... (proof of Fermat’s little theorem, and some more stuff on modulo)
cp-algorithms.com/algebra/fac... (some more prime factorization methods)
github.com/maksim1744/program... (super fast prime factorization)
brilliant.org/wiki/extended-e... (explains the extended GCD algorithm)
codeforces.com/blog/entry/53925 (information on the Mobius inversion)
codeforces.com/contest/803/pr... (problem related to Mobius inversion)
[Related to the above problem, my modified version is problem J in the mashup.]
discuss.codechef.com/t/more-i... (why sum of i from 1 to n of n/i is O(n * log n))
AnandOza has also done a similar stream (I’m just doing this because it was voted on), see codeforces.com/blog/entry/85475
Timestamps:
Intro + tip 00:00
Floor/ceil 01:30
Divisors 01:58
Prime factorization 03:40
Divisor finding 05:43
Modulo 07:00
Binary exponentiation 10:54
Modular "division" 13:11
GCD 17:21
Extended Euclidean (kinda) 21:06
LCM 23:21
Chinese remainder theorem 24:30
Instance of mobius 32:12
Conclusion 36:45

[@Selbstzensur]

I love all the content creator out there. I pick the ones who help me to get rid of my flaws, who help me to grow and this is so awesome. Thank you for beeing one of these creators.

[@harrisondong5405]

Thanks Colin, your lecture videos are very helpful for learning competitive programming, really appreciate.

[@aries3690]

Thanks for all the amazing videos, Im learning a lot!

[@gdthegreat]

Hey Colin, thanks for putting this video, really appreciate.

[@user-to8uo3ir2r]

Thanks for all the amazing Videos. Big fan of you .

[@MyPlanetIsPluto]

This one helps a lot. Not enough concise breakdowns of this topic out there

[@shivanshsahu3781]

Thank you so much for this video, i was actually looking for a good source on Number theory and i find this. ❤

[@AlgorithmsConquered]

Looking forward to it!

[@jaidmmx_3290]

Thanks, you're really awesome!

[@salambience12]

thanks, colin...love from Bangladesh

[@sammkk8700]

Long waiting but worth it❤️❤️

[@shanewalsch]

Thanks alot for a lecture!

[@MiketheCoder]

How do you do division for mod in number theory? It seems to work only for + and *

[@AmanSharma-or5vh]

multiplicative modular inverse

[@user-fb7hw1el1c]

Thank you so much

[@Aditya-cw7rd]

Thanks dude ❣️

[@coefficient1359]

Thank you 👍

[@LinuxKernel-lf8ov]

Hello, i have a question
when you say "lets subtract a from both sides" in the equation (cx+a)%y = b
the equation become (cx+a)%y - a = b-a so what are the math steps to simplify it to be cx%y = (b-a)%y
and second question is how the %y got to be a part for the right hand side ?

[@nirajandata]

thanks colin .

[@solaris413]

thank u so much

[@kxb6098]

Please correct me if I'm wrong:
gcd(a, b) = gcd(a - b, b)
gcd(a, b) = gcd(a + b, b)
right?

[@maxbro8880]

yes, that is how Euclid's algo works
gcd(a, b) = gcd(a + kb, b) for any integer k

[@VIVEKMMMUT-ECE2027]

more efficent would be a%b,b since a-b is same as a%b if done multiple times

[@hloboy8811]

Thanks

[@shivamkushwah3542]

hey galen....i dont think if this is a popular opinion.....but i like your freestyle teaching more than making slides like this.......when we see someone writing or typing it keeps us engaged.......although the content is still awesome....your freestyle teaching is the thing that makes you different and better than others and obviously the content too....

[@powerofpavan7710]

thanks

[@ziedbrahmi4812]

in more modulo: any one can tell me why we need to do b^c%totient(m)? ! any links to this ?

[@tanvirhasan4912]

32:20 it's Möbin time!!

[@wrathcyber]

hey colin, much love from north korea

[@gabbar1867]

Colin I m coming

[@akshayas349]

❤

[@mohimenul1570]

The pastebin link isn't working !

[@mahmoudbassem1434]

7:05 what is that?