### kazama460's blog

By kazama460, 7 months ago,

Hello codeforces community

course updated : 28 October 2020

I have working on Number Theory course which is beginner/Intermediate friendly.The course emphasizes on learning by doing methodology.
After teaching an algorithm/technique and showing how it is implemented we take example practice problems from judges like Codeforces , Codechef , Spoj etc and teach how this algorithm is used in different scenario and how it can be used to solve the problem.
Here is the list of lecture from the course (I will be uploading more lectures soon)

## Number Theory Lectures

Any suggestion or criticism is welcome.
Thank you for your valuable time.

PS : Ignore any grammatical mistake as we ignore compiler warnings (My English is not very good)

• +114

 » 6 months ago, # |   0 Thanks a ton! I was being looking for that...are there any more topics left?
•  » » 6 months ago, # ^ |   0 yes there are many topics I will add , like Chinese remainder theorem
 » 6 months ago, # |   +2 Please add the Chinese remainder theorem too. Really appreciate your work!!
 » 6 months ago, # |   0 I have watched graph theory course of yours. It's wonderful. Thanks buddy!!
 » 6 months ago, # |   0 WOW!!! UPVOTED. I was looking for this. Many many thanks from me.
 » 6 months ago, # | ← Rev. 2 →   0 Chinese remiander theorm3.A) Derivation of number a which satisfies given crt properties. Suppose we have set of numbers relatively prime with each other eg 3 4 5 and there is a number a: a mod 3 = 2 mod 3 a mod 4 = 2 mod 4 a mod 5 = 1 mod 5 3 4 5a = 4*5 3*5 3*44*5 and 3, 3*5 and 4, 3*4 and 5 are co-prime with each otherRecalling 2 Algorithms: 1) fermats little theorm for inverrse modulo,a and p are co-prime and p is also a prime a^(p-1) == 1 mod p : taking 1/p both sides => a^(p-2) == 1/a mod p which means a^(p-2)%p is the inverse of a wrtx m2) Extended euclidean algonow 4*5%3 = 2 hence as the given condition (a mod 3 = 2 mod 3) also satisfies , now action is to be taken now 3*5%4 = 3 hence , as the given condition says it has to be (a mod 4 = 2 mod 4), we first find the modulo inverse of 3*5%4 wrtx 4 i.e invserse of 3 wrtx mod 4, as 3 and 4 are co prime , but 4 is not a prime , hence using extended euclidean algo , we get 3 as modular inverse of 3 wrtx 4. hence 3*5 is multiplied by 3 firstly and then by 2 such that 3*5 * (3 which is mod inverse) *2 ==2 mod 4 now 3*4 mod 5 = 2 mod 5 , using fermat theorm , we get 2^(3)%5 = 3 as mod inverse of 2 wrtx 5, hence multiply 3*4 by 3 for == 1 mod 5hence the final answer is 3 4 5 a = 4*5 3*5*3*2 3*4*3hence a is 4*5 + 3*5*3*2 + 3*4*3 = 146 or 146+n*(3*4*5) = 146+n*60
 » 5 weeks ago, # |   +4 Thank u bro, I took your graph course..That was really nice.
•  » » 5 weeks ago, # ^ |   +1 you're welcome